Контролно за определяне отбора на България за IMO 2007

[drago]

Означаваме с [tex]\mathcal{P}(S)[/tex] фамилията от всички подможества на крайното множество [tex]S[/tex], която включва празното множество и самото [tex]S[/tex].
Функцията [tex]f: \mathcal{P}(S) \to \mathbb{R}[/tex] има свойството:
[tex]f(X \cap Y) = \min \{ f(X), f(Y)\}, \,\, \forall X,Y \in \mathcal{P}(S)[/tex].
Намерете максималния брой различни стойности, които [tex]f[/tex] може да приема.

[drago]

И малко геометрия пак от там
4.зад, първи тест. Даден е [tex]\triangle ABC[/tex] и точка [tex]P \in AB[/tex]. Разглеждаме всички двойки точки [tex]X, \, Y; \, X \in BC, \, Y \in AC[/tex], такива че [tex]\angle PXB = \angle PYA[/tex].
Докажете, че средите на всевъзможните такива отсечки [tex]XY[/tex] лежат на една права.

[ptj]

Малко анализ по задача 2:

Средите (т.[tex]M[/tex])на отсечката [tex]XY[/tex]лежат на една права ([tex]CP[/tex]) тогава и само тогава, когато векторите [tex]\vec{CM}[/tex] и [tex]\vec{CP}[/tex] са колинеарни. Последното е еквиваленто на [tex]CX:CY=CB:CA[/tex].

[ganka simeonova]

Малко анализ по задача 2:

Средите (т.[tex]M[/tex])на отсечката [tex]XY[/tex]лежат на една права ([tex]CD[/tex], т.[tex]D[/tex]среда на [tex]AB[/tex]) тогава и само тогава, когато векторите [tex]\vec{CM}[/tex] и [tex]\vec{CD}[/tex] са колинеарни. Последното е еквиваленто на [tex]CX:CY=CB:CA[/tex].

Задачата няма нищо общо със средата на АВ!

[ptj]

Да, там трябваше да е [tex]CP[/tex] (, а не [tex]CD[/tex]).

П.П. Престани да се обаждаш, като черна станция и да мислиш, че цялата математика се свежда до обичаната от теб планиметрия. Червения химикал го запази за учениците си...

[ganka simeonova]

Дам но пак Р не е среда!

[ptj]

Айде стига празни приказки, довърши по-добре решението. Нали там ти е силата.

[ganka simeonova]

Малко анализ по задача 2:

Средите (т.[tex]M[/tex])на отсечката [tex]XY[/tex]лежат на една права ([tex]CP[/tex]) тогава и само тогава, когато векторите [tex]\vec{CM}[/tex] и [tex]\vec{CP}[/tex] са колинеарни. Последното е еквиваленто на [tex]CX:CY=CB:CA[/tex].

Не знам, дали ще мога да я реша, но твоето твърдение не е вярно! СМ И СР не са колинеарни!

[ptj]

Права си, но това не променя особено задачата.

За да се намери ГМ на търсената права (определена от средите на XY) се използва метод на непрекъснатост. Т.е. да се намерят двете точки когато [tex]\angle XPB[/tex] клони към [tex]min=0^\circ[/tex] или [tex]max[/tex].

[tex]max[/tex] е по-малкия от ъглите [tex]BPC[/tex] и [tex]APC[/tex].

Нека [tex]max=\angle BPC[/tex], а т.[tex]N\in AC[/tex] като [tex]\angle APN=\angle BPC[/tex].

Когато [tex]\angle BPX=\angle APY[/tex] клони към [tex]max[/tex], то т.[tex]X[/tex] клони към т. [tex]C[/tex], а т.[tex]Y[/tex] клони към т.[tex]N[/tex]. Тогава средата на [tex]XY[/tex] клони към т.[tex]M[/tex] - среда на [tex]CN[/tex].

Когато [tex]\angle BPX=\angle APY[/tex] клони към [tex]0^\circ[/tex], средата на [tex]XY[/tex] клони към т.[tex]D[/tex]- среда на [tex]AB[/tex].

Окончателно средата на [tex]XY[/tex] лежи на [tex]DM[/tex].

П.П. Пиша за това, защото на състезание анализа е половината от решението на задачата, останалото -техника.

[ganka simeonova]

Права си, но това не променя особено задачата.

За да се намери ГМ на търсената права се използва метод на непрекъснатост. Т.е. да се намерят двете точки когато [tex]\angle XPB[/tex] клони към [tex]min=0^\circ[/tex] или [tex]max[/tex].

? Наистина не те разбрах.

[ptj]

1. Зад.
Различните стойности на [tex]f[/tex] отговарят на непресичащи се подмножества на [tex]S[/tex], затова решаваме еквивалентна задача:

Максималния брой взаимно непресичащи се класове от подмножества на [tex]S[/tex] е точно [tex]\parallel S \parallel[/tex]+1 . Всеки един от тях съдържа поне (*) по едно от множества с точно един елемент от [tex]S[/tex] + празното множество.


П.П. С други думи максимума е не по-голям от броя на различните елементи в [tex]S[/tex]+1. Може да се поясни по-разбираемо посредством множеството на първите [tex]n[/tex] естествени числа, което да е изоморфно на [tex]S[/tex].

(*) "поне" - заради възможността за съвпадащи елементи. Например S={1;2;2;3;4}, то има само 5 различни класа непресичащи се подмножества (4 "истински" +празното множество).

[mkmarinov]

По 1, НГС на f се достига в S, а НМС - в празното множество. Може д апомогне, както и да се обобщи .

[drago]

Да дам една идея за геометричната задача. Не знам дали това е оригиналното решение, но почти съм сигурен, че така ще стане задачата.
Да решим първо случая, когато [tex]P[/tex] съвпада със средата на [tex]AB[/tex]. Tова опростява нещата по редица причини.
Да предположим, че този случай е вече доказан. Тогава, ако [tex]P[/tex] има общо положение, то можем така да построим [tex]A_1[/tex] oт правата [tex]AC[/tex] и [tex]B_1[/tex] oт правата [tex]BC[/tex], така че [tex]P[/tex] e среда на [tex]A_1B_1[/tex].
Oт тук нататък вече сме в познатия случай.
Друг вариант е да докажем задачата, когато триъгълника е равнобедрен([tex]\angle A = \angle B[/tex] ) и после по горната схема да сведем общия случай към този.

[ptj]

По 1, НГС на f се достига в S, а НМС - в празното множество. Може д апомогне, както и да се обобщи .

Според мен максимума е: (броя на елементите на S)+1.

Пример:
[tex]S=[/tex]{[tex]1;2;3;...;n[/tex]},
[tex]\for P \subset S[/tex] ([tex]P\ne \empty[/tex]): [tex]f(P)=[/tex]минималния елемент в [tex]P[/tex];
[tex]f( \empty )=0[/tex];

[drago]

@ptj: Интуицията ти е вярна: [tex]|S|+1[/tex], обаче за да се докажат нещата трябва, както знаеш, 2 стъпки.
1. Трябва да се докаже, че не може да има функция с повече от [tex]|S|+1[/tex] различни стойности.
2. Да се построи пример с функция с точно [tex]|S|+1[/tex] различни стойности.

Примера с минималния елемент, с който се опитваш да конструираш 2) не става, може да да се убедиш и сам.
Да кажем, че 2) е по-лесно.
Една идеята за 1) е да допуснем противното, че ф-ята има поне [tex]N+2[/tex] [tex]( N= |S|)[/tex] различни стойности: [tex]u_1, u_2, \dots , u_{N+2}[/tex]. Oт тук някак си да конструираме множества: [tex]S_1 \subset S_2 \subset \dots \subset S_{N+2}[/tex]. така че:
[tex]f(S_1) < f(S_2) < \dots < f(S_{N+2})[/tex]. Това вече ще доведе до противоречие.

[ptj]

Аз вече по-горе писах за класовете от подмножества на [tex]S[/tex], но не виждам какво има да се доказва (по 1.) ) след като може да се използва принципа на Дирихле. Според него не може да образуваме [tex]n+1[/tex] множества (не празни) с елементи от S, без поне 2 от тях да имат сечение. От тук, съобразявайки вида на [tex]f[/tex], непосредствено следва исканото.

[drago]

@Ptj: или напиши грамотно решение или недей вкарвай шум в хубавата задача !

[drago]

Моето решение на 1-вата задача.
1) Нека допуснем, че [tex]f[/tex] приема [tex]n[/tex] различни стойности [tex]u_1<u_2<\,,\dots,\,< u_n[/tex]. Означаваме [tex]\mathcal{U}_i = f^{-1}(u_i)[/tex]. Това e фамилия от множества.
От дефиницията на [tex]f[/tex] се проверява, че ако [tex]X,Y \, \in \,\mathcal{U}_i \, \Rightarrow \, X \cap Y \in \,\mathcal{U}_i[/tex]. Toва означава, че: [tex]\bigcap \mathcal{U}_i \in \mathcal{U}_i[/tex]. Да означим: [tex]V_i = \bigcap \mathcal{U}_i[/tex]. Ще докажем, че [tex]V_i \subset V_{i+1}.[/tex].
Имаме: [tex]f(V_i) = u_i, \, f(V_{i+1}) = u_{i+1}\, \Rightarrow \, f(V_i \cap V_{i+1}) = min\{u_i, u_{i+1}\} = u_i \, \Rightarrow \, V_i \cap V_{i+1} \in \mathcal{U}_i \, \Rightarrow \, V_i \cap V_{i+1} = V_i \, \Rightarrow \, V_i \,\subset\neq\, V_{i+1}[/tex].
И така картинката е следната:
[tex]V_1 \subset\neq V_2 \subset\neq \, \dots \, \subset\neq V_n[/tex]
От горното следва [tex]n \le |S| + 1[/tex] , тъй като иначе няма как да се вложат едно в друго без равенство толкова много подмножества на [tex]S[/tex].

2)Да конструираме функция [tex]f[/tex] с [tex]|S|+1[/tex] различни стойности. Индукция по [tex]|S|[/tex].
За множество с един елемент: [tex]S= \{1\}[/tex], функцията:
[tex]f(\empty)=0;\, f(\{1\}) = 1[/tex] удовлетворява изискванията.
Нека вече имаме конструирана функция [tex]f^'[/tex] за [tex]S^'=\{1,2,...,n-1\}[/tex]. Нека [tex]S=\{1,2,...,n-1,n\}[/tex]. Дефинираме функцията [tex]f: \mathcal{P}(S) \to \mathbb{R}[/tex] по следния начин:
Ако [tex]X \subset S^',\, f(X)=f^'(X)[/tex], ako [tex]X=\{n\}\cup X^',\, X^' \subset S^',\, X^' \neq S^',\,\, f(X)=f^'(X^')[/tex] , и накрая [tex]f(S)=n[/tex].
Проверява се, че [tex]f[/tex] удовлетворява изискванията.

[kucheto]

И малко геометрия пак от там
4.зад, първи тест. Даден е [tex]\triangle ABC[/tex] и точка [tex]P \in AB[/tex]. Разглеждаме всички двойки точки [tex]X, \, Y; \, X \in BC, \, Y \in AC[/tex], такива че [tex]\angle PXB = \angle PYA[/tex].
Докажете, че средите на всевъзможните такива отсечки [tex]XY[/tex] лежат на една права.

Достатъчно е да докажем, че твърдението е изпълнено за 3 произволни точки от AB.

Нека: [tex]X_k\in AC;\ Y_k\in BC;\ M_k\in X_kY_k[/tex]

[tex]\angle PX_1A=\angle PY_1B;\ \angle PX_2A=\angle PY_2B;\ \angle PX_3A=\angle PY_3B[/tex]

Тогава: [tex]\triangle PX_1X_2\approx \triangle PY_1Y_2\Rightarrow \frac{X_1X_2}{X_2P}=\frac{Y_1Y_2}{Y_2P}[/tex]

Аналогично: [tex]\frac{X_2X_3}{X_2P}=\frac{Y_2Y_3}{Y_2P}[/tex]

От последните 2 равенства: [tex]\frac{X_1X_2}{X_2X3}=\frac{Y_1Y_2}{Y_2Y3}[/tex]


Сега обаче няма да доказвам частния случай при [tex]X_lM_l=Y_lM_1[/tex], а общия случай: [tex]\frac{X_lM_l}{Y_lM_l}=const[/tex]

Още повече ще докажа, че е изпълнено [tex]\frac{X_mX_n}{X_pX_q}=\frac{Y_mY_n}{Y_pY_q}=\frac{M_mM_n}{M_pM_q}[/tex] по индукция.


Ориентираме векторите: [tex]\vec{X_1X_2}=a_1;\ \vec{X_2X_3}=b_1;\ \vec{Y_1Y_2}=a_2;\ \vec{Y_2Y_3}=b_2;\ \vec{M_1Y_1}=c_1;\ \vec{M_2Y_2}=c_2;\ \vec{M_3Y_3}=c_3;\\\vec{A_1M_1}=d_1;\ \vec{A_2M_2}=d_2;\ \vec{A_2M_2}=d_1;\ \vec{M_1M_2}=x;\ \vec{M_2M_3}=y[/tex]

Следователно: [tex]\frac{a_1}{b_1}=\frac{a_2}{b_2}=r;\ \frac{c_1}{d_1}=\frac{c_2}{d_2}=\frac{c_3}{d_3}=s[/tex]

Трябва да докажем: [tex]\frac{x}{y}=r[/tex]

[tex]x=a_2+c_1-c_2=a_1+d_2-d_1\\y=b_2+c_2-c_3=b_1+d_3-d_2\\\Rightarrow \frac{a_2+c_1-c_2}{b_2+c_2-c_3}=\frac{a_1+d_2-d_1}{b_1+d_3-d_2}[/tex]

Първо ще докажем, че:
[tex]\frac{c_1-c_2}{c_2-c_3}=\frac{d_2-d_1}{d_3-d_2}\\\Rightarrow -c_1d_2-c_2d_3+c_1d_3+c_2d_2=-d_2d_1-c_3d_2+c_2d_2+c_3d_1\\\Rightarrow (c_2d_2-c_2d_2)-(c_1d_2-c_2d_1)-(c_1d_3-c_3d_1)-(c_3d_2-c_2d_3)\\\Rightarrow 0=0[/tex]

Можем да положим:
[tex]\frac{c_1-c_2}{c_2-c_3}=\frac{d_2-d_1}{d_3-d_2}=\frac{u}{v}[/tex]
[tex]\Rightarrow \frac{u+a_1}{v+b_1}=\frac{u+a_2}{v+b_2}\\\Rightarrow (uv+a_1b_2)+b_2u+a_1v=(uv+a_2b_1)+b_1u+a_2v\\\Rightarrow (a_1-a_2)v=(b_1-b_2)u\\\Rightarrow \frac{u}{v}=\frac{a_1-a_2}{b_1-b_2}=r\\\Rightarrow \frac{x}{y}=\frac{u+a_1}{v+b_1}=\frac{rv+rb_1}{v+b_1}=r[/tex]

С това доказателството е завършено.

[kucheto]

Ето и чертеж:

[drago]

@kucheto: Има рационално зърно в това разсъждение, но в този вид не е вярно:

...
Първо ще докажем, че:
[tex]\frac{c_1-c_2}{c_2-c_3}=\frac{d_2-d_1}{d_3-d_2}\\\Rightarrow -c_1d_2-c_2d_3+c_1d_3+c_2d_2=-d_2d_1-c_3d_2+c_2d_2+c_3d_1\\\Rightarrow (c_2d_2-c_2d_2)-(c_1d_2-c_2d_1)-(c_1d_3-c_3d_1)-(c_3d_2-c_2d_3)\\\Rightarrow 0=0[/tex]
...

Това го доказваш като отношение на дължини, а не на вектори. Друг е въпросът, че то е вярно и като вектори: [tex]c_1-c_2[/tex] е колинеарен на [tex]c_2-c_3[/tex] и същото и с d-тата.

Благодаря за идеята, ако разрешиш може да се доразвие така:
Нали [tex]\frac{X_1X_2}{X_2X_3} = \frac{Y_1Y_2}{Y_2Y_3}[/tex]. От тук ако [tex]X_1Y_1[/tex] беше успоредно на [tex]X_2Y_2[/tex] то и всяко друго [tex]XY[/tex] щеше да е успоредно на тях и ГМТ [tex]M[/tex] щеше да е права през върха [tex]C[/tex] и средата на [tex]X_1Y_1[/tex].
Обаче в общия случай не е!! Но ние можем да го направим да е! Като приложим транслация, само на точките от правата [tex]CB[/tex], на вектор колинеарен на тази права(така че да останат пак в/у тази права) с някаква дължина,така че [tex]X_1Y^'_1[/tex] вече да е успоредно на [tex]X_2Y^'_2[/tex]. При това преобразувание точките M се транслират с половината от вектора на транслация. И тъй като вече е ясно какво е ГМТ на [tex]M^'[/tex], то точките [tex]M[/tex] се полчават като транслираме обратно, което пак ще е права.

[kucheto]

Благодаря за идеята, ако разрешиш може да се доразвие така:
Нали [tex]\frac{X_1X_2}{X_2X_3} = \frac{Y_1Y_2}{Y_2Y_3}[/tex]. От тук ако [tex]X_1Y_1[/tex] беше успоредно на [tex]X_2Y_2[/tex] то и всяко друго [tex]XY[/tex] щеше да е успоредно на тях и ГМТ [tex]M[/tex] щеше да е права през върха [tex]C[/tex] и средата на [tex]X_1Y_1[/tex].
Обаче в общия случай не е!! Но ние можем да го направим да е! Като приложим транслация, само на точките от правата [tex]CB[/tex], на вектор колинеарен на тази права(така че да останат пак в/у тази права) с някаква дължина,така че [tex]X_1Y^'_1[/tex] вече да е успоредно на [tex]X_2Y^'_2[/tex]. При това преобразувание точките M се транслират с половината от вектора на транслация. И тъй като вече е ясно какво е ГМТ на [tex]M^'[/tex], то точките [tex]M[/tex] се полчават като транслираме обратно, което пак ще е права.

Естествено, че "разрешавам" да ми се доразвие идеята. Даже е по-добре да има повече и по-елегантни решения, тъй като аз след няколко дена мислене как да продължа от [tex]\frac{X_1X_2}{X_2X_3} = \frac{Y_1Y_2}{Y_2Y_3}[/tex], не намерих нищо геометрично, но забелязах векторните равенства и си поиграх с пропорциите (наистина пропорциите се отнасят за числа, а не за вектори, но в тези пропорции векторите са от един и същ вид), с което реших задачата. Но все пак не изпитах пълно удовлетворение от това, че реших задачата, тъй като решението ми е твърде силово и няма красота в него, докато твоето решение е много хубаво и е чисто геометрично.

[drago]

@kucheto: Важното е, че си я решил! Но решението ти ще стане издържано, ако навсякъде думата вектори я замениш с "комплексни числа", тъй като вектори не можеш да делиш, освен ако не са колинеарни, а отнапред това не е известно. Накрая получаваш, че отношението на 2 комплексни числа е реално, т..е. те са колинеарни. И по-добре махни думата "индукция".