МОМ, Първи ден

[Makelov]

Ето задачите от първия ден на 52. Международна олимпиада по математика.

2011_bul.pdf

(310.23 KiB) 472 пъти

2 ден на МОМ

[Mechkov]

Хах, първият, който даде +1 на сайта в Google+ съм. Спамът настрана, ето ми решенията. Вчера направих първа, а днес трета и (уж) втора. Решенията ми горе-долу са следните:

1. Ако всичките 6 двойки делят сумата, то всички числа са равни - противоречие, ако са 5, то имаме поне две равенства на двойки от типа [tex]a_1 + a_2 = a_3 + a_4[/tex] и [tex]a_2 + a_3 = a_1 + a_4[/tex]. Като ги съберем почленно, получаваме [tex]a_2 = a_4[/tex] - противоречие. Ще покажем множествата с 4 двойки, делящи сумата. Нека за определеност [tex]a_1 < a_2 < a_3 < a_4[/tex]. За да са 4, трябва да имаме едно равенство. Тоест сумата е равна на 2d, за някое естествено d и имаме [tex]a_i + a_j = a_k + a_l = d[/tex] за някои [tex]i, j, k, l \in \{1, 2, 3, 4\}[/tex]. Нека [tex]a_1 = a[/tex] и [tex]a_2 = b[/tex], тогава [tex]a_3[/tex] и [tex]a_4[/tex] са съответно [tex]d-b[/tex] и [tex]d-a[/tex]. Тоест [tex]a_1 + a_4 = a_2 + a_3[/tex]. За да имаме четири двойки със сума деляща [tex]s_A[/tex], то трябва да имаме още две двойки, които делят сумата, тогава понеже имаме, че [tex]a_1 + a_2 < a_3 + a_4[/tex] и [tex]a_1 + a_3 < a_2 + a_4[/tex] и факта, че ако примерно [tex]a_3 + a_4 | s_A[/tex], то следва, че [tex]a_3 + a_4 | a_1 + a_2[/tex] (което е противоречие) имаме, че [tex]a_1 + a_2[/tex] и [tex]a_1 + a_3[/tex] делят [tex]s_A[/tex] => [tex]a_1 + a_2 | a_3 + a_4[/tex] и [tex]a_1 + a_3 | a_2 + a_4[/tex]. Тоест [tex]a + b | 2d - a - b[/tex] => [tex]a + b | 2d[/tex] и [tex]d + a - b | d + b - a[/tex] = > [tex]d + a - b | 2(b - a)[/tex] => [tex]d + a - b \le 2(b-a)[/tex] => [tex]d \le 3(b-a)[/tex] => [tex]a_3 \le 2b - 3a[/tex] и [tex]a_4 \le 3b - 4a[/tex]. Като съберем почленно получаваме [tex]a_3 + a_4 \le 5b - 7a[/tex]. [tex]a + b | a_3 + a_4[/tex] и нека [tex]a_3 + a_4 = k(a+b)[/tex]. От полученото неравенство имаме, че [tex]2 \le k \le 4[/tex]. Нека разгледаме 3 случая:
1) [tex]k = 2[/tex] => [tex]2d = 3(a + b)[/tex], тогава [tex]a_3 = \frac{3}{2}a + \frac{1}{2}b[/tex].[tex]b < a_3[/tex] => [tex]b < 3a[/tex]. От друга страна, тъй като получихме, че [tex]d \le 3(b - a)[/tex] => [tex]3(a + b) \le 6(b - a)[/tex], от където следва, че [tex]b \ge 3a[/tex] - противоречие.
2) [tex]k = 3[/tex] => [tex]d = 2(a + b)[/tex] => [tex]a_3 = 2a+b[/tex] и [tex]a_4 = 2b + a[/tex]. От [tex]a_1 + a_3 | a_2 + a_4[/tex] имаме [tex]3a + b | 3b + a[/tex]. Частното [tex]\frac{3b + a}{3a + b}[/tex] не може да е 1 или по - голямо или равно на 3, значи е 2 => [tex]3b + a = 6a + 2b => b = 5a => a_3 = 7a[/tex] и [tex]a_4 = 11a[/tex]. Всяко множество от вида (a, 5a, 7a, 11a) е решение.
3) [tex]k = 4[/tex] => [tex]2d = 5(a + b)[/tex]. Аналогично на предния случай получаваме, че [tex]7a + 3b | 7b + 3a[/tex] и отново частното може да е само 2 => получаваме решението (a, 11a, 19a, 29a).

3. Като положим y = 0, имаме f(x) ≤ f(f(x)). Като положим x = 0, получаваме f(y) ≤ y.f(0) + f(f(0)). В този израз нека положим y = f(x) => f(f(x)) ≤ f(x).f(0) + f(f(0)) => f(x) ≤ f(x).f(0) + f(f(0)) => [tex](1)f(x) \le \frac{f(f(0))}{1 - f(0)}[/tex] => функцията е ограничена отгоре. Нека f(c) = sup(f) и c е максимално. Като положим x = c в (1) получаваме [tex]f(c) \le \frac{f(f(0))}{1 - f(0)} \le \frac{f(c)}{1 - f(0)}[/tex] => 0 ≤ f(0) => 0 ≤ f(c). Нека в първоначалното неравенство заместим x = c + k, y = -k, получаваме f(c) ≤ (-k)f(c - k) + f(f(c - k)) ≤ (-k)f(c-k) + f(c) => k.f(c-k) ≤ 0. Тоест за x > c, f(x) ≤ 0, a за x < c, 0 ≤ f(x). Сега, нека в първоначалното неравенство заместим x = c, y = -k => f(c - k) ≤ -k.f(c) + f(f(c)) = -k.f(c) + f(c) = (1 - k)f(c). Тъй като 0 ≤ f(c) имаме, че за x ≤ c - 1 f(x) ≤ 0. Но преди малко получихме, че за x < c, 0 ≤ f(x) => за x ≤ c - 1, f(x) = 0. Сега нека разгледаме 2 случая:
1) c ≤ 0 => f(0) = 0 => от (1) => f(x) ≤ 0 за всяко x => c = 0
2) c > 0. Нека в първоначалното неравенство заместим x = c = f(c + y) ≤ y.f(c) + f(f(c)) = (y + 1)f(c). Като положим y = -5, получаваме f(c - 5) ≤ -4.f(c) < 0, но преди малко получихме, че f(x) при x ≤ c - 1 е строго равно на нула - противоречие
=> c = 0. Тъй като за x < c, 0 ≤ f(x), но максимумът на f(x) e 0, то за всяко x ≤ 0, f(x) = 0.

Ще напиша 2-ра довечера

[allier]

На третата имаш грешка. В неравенството, където определяш, че функцията е ограничена, знакът може да е и в обратната посока. Освен това, не знаеш дали въпросния супремум или инфимум се достига в крайна стойност или в безкрайност.

[Mechkov]

Фейл... Поне може лесно да се излекува. f(x + y) ≤ yf(x) + f(f(x)). Сега допускаме, че 1 ≤ f(0) (тогава се прецаква ограничението). Полагаме x = 0 => f(y) ≤ f(0)y + f(f(0)) => f(y) < y => f(0) < 0 => противоречие. Тогава ограничението е от горе и си е крайно и можем да вземем sup.

[allier]

Пак не ми стана ясно откъде излиза противоречието от неравенството, което си написал. Но няма значение, да допуснем, че е вярно. Откъде следва, че супремумът се достига във вътрешна точка (особено, че функцията не е задължително непрекъсната) т.е. самото полагане не може да се направи за c (може да е безкрайност).

[Mechkov]

"Сега допускаме, че 1 ≤ f(0)" и от допускането съм написал как следва, че f(0) < 0, т.е. допускането е грешно. Щом f(0) < 1, можем да делим на 1 - f(0) без да променяме посоката на неравенството. Тоест (1) си е вярно и f(x) е ограничена отгоре, защото f(f(0))/(1 - f(0)) е константа. Тоест sup(f) може да е най - много f(f(0))/(1 - f(0)).

3. Като положим y = 0, имаме f(x) ≤ f(f(x)). Като положим x = 0, получаваме f(y) ≤ y.f(0) + f(f(0)). В този израз нека положим y = f(x) => f(f(x)) ≤ f(x).f(0) + f(f(0)) => f(x) ≤ f(x).f(0) + f(f(0)) => [tex](1)f(x) \le \frac{f(f(0))}{1 - f(0)}[/tex] => функцията е ограничена отгоре.

Супремум ще се достигне (или ще се доближи произволно много) в крайна точка, защото f(f(x)) > f(x). Тоест, ако за дадено x, f(x) достига супремума, то той ще се достига и при f(f(x)), а f(x) е крайно (по - малко или равно на f(f(0))/(1 - f(0)))

[allier]

Не съм съгласен - нищо не пречи на супремума да се достигне и в безкрайност - като добавим, че функцията не е задължително непрекъсната, не можеш да използваш, че ако [tex]x_{n}->x[/tex], то [tex]f(x_{n})->f(x)[/tex].

Освен това, допускайки, че [tex]f(0)\ge 1[/tex], не виждам как от [tex]f(y)\le f(0)y + f(f(0))[/tex] следва, че [tex]f(y)\le y[/tex]. Така че разясни малко - може и да следва, ако се използва, че f(f(0))>f(0)>1, само че от това, което е написано, не става ясно.

Иначе, поправимо е решението, да. Може да се покаже, че функцията е минус безкрайност при много голямо или много малко x.

[Mechkov]

Това с f(y) < y е голяма идиотщина, дето съм го писал. Таа може да се оправи така: Ако f(0) ≥ 1 => f е ограничена отдолу. Като заместим с x = 0 в първоначалното, получаваме f(y) ≤ f(0)y + f(f(0)) => за y -> -oo f(y) -> -oo тъй като f(0) > 0 => противоречие с ограничението. Иначе нямамe ли, че sup(f) ≤ f(sup(f)), заради f(x) ≤ f(f(x)) (това в случай, че sup(f) се достига)? Ако f(x) може само да заема произволни стойности до sup(f), то тогава имаме, че съществуват [tex]x_1, x_2, x_3, ..., x_n, ...[/tex], за които [tex]sup(f) - f(x_i) < \epsilon[/tex], тогава ако дефинираме [tex]y_i = f(x_i)[/tex], то от f(x) ≤ f(f(x)) отново имаме [tex]sup(f) - f(y_i) < \epsilon[/tex], а на всичкото отгоре игреците са едни такива хубави и ограничени. И харесваме произволно близко до sup(f) от тях за c и от там нататък задачата продължава аналогично.

[drago]

Може би малко късно, но ми прави впечатление, че липсват коментари по 2-ра.
Задачата наистина е нестандартна и позволява много подходи, а идеята, която я решава е единствена. Поне аз не знам друго решение, а съм гледал много форуми и коментари, още в първия ден на IMO. Може би поради това представянето на нея е лошо.
Има едно ключово наблюдение, което я решава, като си мисля, че който е стигнал до него е решил и задачата.

При въртенето около точките, на всяка стъпка има един инвариант- разликата между броя на точките отляво и отдясно.