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

от **Makelov** » Пон Юли 18, 2011 10:24 am

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

2011_bul.pdf: (310.23 KiB) 293 пъти

от **Mechkov** » Сря Юли 20, 2011 12:36 pm

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

1. Ако всичките 6 двойки делят сумата, то всички числа са равни - противоречие, ако са 5, то имаме поне две равенства на двойки от типа $a_1 + a_2 = a_3 + a_4$ и $a_2 + a_3 = a_1 + a_4$ . Като ги съберем почленно, получаваме $a_2 = a_4$ - противоречие. Ще покажем множествата с 4 двойки, делящи сумата. Нека за определеност $a_1 < a_2 < a_3 < a_4$ . За да са 4, трябва да имаме едно равенство. Тоест сумата е равна на 2d, за някое естествено d и имаме $a_i + a_j = a_k + a_l = d$ за някои $i, j, k, l \in \{1, 2, 3, 4\}$ . Нека $a_1 = a$ и $a_2 = b$ , тогава $a_3$ и $a_4$ са съответно $d-b$ и $d-a$ . Тоест $a_1 + a_4 = a_2 + a_3$ . За да имаме четири двойки със сума деляща $s_A$ , то трябва да имаме още две двойки, които делят сумата, тогава понеже имаме, че $a_1 + a_2 < a_3 + a_4$ и $a_1 + a_3 < a_2 + a_4$ и факта, че ако примерно $a_3 + a_4 | s_A$ , то следва, че $a_3 + a_4 | a_1 + a_2$ (което е противоречие) имаме, че $a_1 + a_2$ и $a_1 + a_3$ делят $s_A$ => $a_1 + a_2 | a_3 + a_4$ и $a_1 + a_3 | a_2 + a_4$ . Тоест $a + b | 2d - a - b$ => $a + b | 2d$ и $d + a - b | d + b - a$ = > $d + a - b | 2(b - a)$ => $d + a - b \le 2(b-a)$ => $d \le 3(b-a)$ => $a_3 \le 2b - 3a$ и $a_4 \le 3b - 4a$ . Като съберем почленно получаваме $a_3 + a_4 \le 5b - 7a$ . $a + b | a_3 + a_4$ и нека $a_3 + a_4 = k(a+b)$ . От полученото неравенство имаме, че $2 \le k \le 4$ . Нека разгледаме 3 случая:
1) $k = 2$ => $2d = 3(a + b)$ , тогава $a_3 = \frac{3}{2}a + \frac{1}{2}b$ . $b < a_3$ => $b < 3a$ . От друга страна, тъй като получихме, че $d \le 3(b - a)$ => $3(a + b) \le 6(b - a)$ , от където следва, че $b \ge 3a$ - противоречие.
2) $k = 3$ => $d = 2(a + b)$ => $a_3 = 2a+b$ и $a_4 = 2b + a$ . От $a_1 + a_3 | a_2 + a_4$ имаме $3a + b | 3b + a$ . Частното $\frac{3b + a}{3a + b}$ не може да е 1 или по - голямо или равно на 3, значи е 2 => $3b + a = 6a + 2b => b = 5a => a_3 = 7a$ и $a_4 = 11a$ . Всяко множество от вида (a, 5a, 7a, 11a) е решение.
3) $k = 4$ => $2d = 5(a + b)$ . Аналогично на предния случай получаваме, че $7a + 3b | 7b + 3a$ и отново частното може да е само 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)) => $(1)f(x) \le \frac{f(f(0))}{1 - f(0)}$ => функцията е ограничена отгоре. Нека f(c) = sup(f) и c е максимално. Като положим x = c в (1) получаваме $f(c) \le \frac{f(f(0))}{1 - f(0)} \le \frac{f(c)}{1 - f(0)}$ => 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** » Сря Юли 20, 2011 3:05 pm

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

от **Mechkov** » Чет Юли 21, 2011 4:02 am

Фейл... Поне може лесно да се излекува. 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** » Чет Юли 21, 2011 7:12 am

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

от **Mechkov** » Чет Юли 21, 2011 8:58 am

"Сега допускаме, че 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)).

Mechkov написа: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)) => $(1)f(x) \le \frac{f(f(0))}{1 - f(0)}$ => функцията е ограничена отгоре.

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

от **allier** » Чет Юли 21, 2011 9:45 am

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

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

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

от **Mechkov** » Чет Юли 21, 2011 10:13 am

Това с 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), то тогава имаме, че съществуват $x_1, x_2, x_3, ..., x_n, ...$ , за които $sup(f) - f(x_i) < \epsilon$ , тогава ако дефинираме $y_i = f(x_i)$ , то от f(x) ≤ f(f(x)) отново имаме $sup(f) - f(y_i) < \epsilon$ , а на всичкото отгоре игреците са едни такива хубави и ограничени. И харесваме произволно близко до sup(f) от тях за c и от там нататък задачата продължава аналогично.

от **drago** » Нед Сеп 11, 2011 5:35 am

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

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

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

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

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

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

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

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

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

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

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

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

Кой е на линия