Национален кръг, 2010 - задачи

[Николай Каракехайов]

Задачите от 3 кръг на националната олимпиада по математика - 2010 година

[b1ck0]

Сериозни задачи ...

[mousehack]

А решения ?

[naitsirk]

А класирането може ли да се намери някъде? В сайта на мон е публикувано класирането само на първите 12.

[Станислав]

Ще кажа схематично моите решения.
За първата - таблицата се разделя на 502 правоъгълници 2x4 и един квадрат 2x2 и се показва, че във всеки един от правоъгълниците Иван може да сложи домино, но едно домино на Иван му "запазва" квадратче 2x2. Поради факта, че е първи, то той ще постави и в 2x2 квадрата, откъдето той ще постави поне с едно домино повече, защото в правоъгълник 4x2 той поставя поне 2 доминота, т.е слага поне [tex]502*2+1=1005[/tex] доминота, но лесно се проверява, че максималният брой доминота, които могат да се поставят е 2009, откъдето следва, че Иван бие!
За втората - ясно е, че 2 от върховете ще са инфлексните точки на [tex]f(x)[/tex]. Можем б.о.о да предполагаме c=0. Нека да означим четириъгълника с ABCD като B и D са инфлексните точки на [tex]f(x)[/tex]. [tex]x_b,x_d[/tex] са корените на у-нието f'(x)=0. Нека правите [tex]AB[/tex] и [tex]CD[/tex] да са с ординати [tex]m[/tex] и [tex]n[/tex] съответно. Ясно е, че [tex]x_{a}[/tex] и [tex]x_c[/tex] са корени съответно на [tex]f(x)=m[/tex] и [tex]f(x)=n[/tex]. От формулите на Виет - [tex]2x_b+x_a=-a[/tex] и [tex]2x_d+x_c=-a[/tex], защото [tex]x_b,x_d[/tex] са двукратни корени съответно на [tex]f(x)=m[/tex] и [tex]f(x)=n[/tex]. Лесно се проверява, че [tex]|x_a-x_b|=|x_c-x_d|[/tex] и от факта, че [tex]AB||CD[/tex], то [tex]ABCD[/tex]- успоредник. Отново от формулите на Виет имаме [tex]x_b^2.x_a=m[/tex] и [tex]x_c^2.x_d=n[/tex].
[tex](->)[/tex] Ако ABCD-ромб, то [tex]AB=AD[/tex] и от формулата за разстояние между точки в равнината изразяваме по втори начин [tex](m-n)^2[/tex] като функция на [tex]D=a^2-3b[/tex], което е дискриминантата на [tex]f'(x)=0[/tex] и приравнявайки получаваме [tex]2D^2=81[/tex]. Намираме дължините на диагоналите на ромба и от формулата за лица [tex]S_{ABCD}=\frac{AC.BD}{2}[/tex] получаваме [tex]S=6[/tex].
[tex](<-)[/tex] Ако пък S=6, то достигаме до [tex]2D^2=81[/tex], което е еквивалентно с [tex]AB=AD[/tex].
Третата не съм я мисли - нямах време.
Четвърта -понеже [tex]2^21[/tex] e 7-цифрено, то [tex]k\le20[/tex]. Условието се преобразува до 7.11.13A+4=n^k, където A е числото, образувано от 1вите 3цифри. По модул 7 отхвърляме случаите 3|k, по модул 11- 5|k, по модул 13 - 4|k. Останалите е проверяват непосредствено.
Пета - 3 часа мислене по нея и единственото, което забелязах е, че до около 25-я член на редицата(до там проверявах) е в сила [tex]f(8k+s)=5k+f(s), s=\{1,...,8\}[/tex]. Естествено, това не е в сила в общия случай. Така е като през целия си живот не съм решавал нито 1 функционално! За заинтересованите [tex]f(n)=\lfloor \frac{\sqrt{5}-1}{2}.(n+1) \rfloor[/tex] - nice, a? (Красимир от Разград го намери гнидата!).
Шеста - най-сложната от всички задачи. Никой не я е решил напълно,(включително руснаците!). Достатъчен е фактът, че Панчев за няколко часа е получил само 2 точки. Евалата на Макелов - има 6 точки. Авторското решение е типично Боев-style - чисто синтетично и такова, за което никога не бих се сетил.
ПС Дори не знам как не ме домързя да го изпиша всичкото това. Ще компенсирам като не отговарям на въпроси

[Baronov]

Готини задачи. Аз ги решавах вкъщи, където разбира се е доста по-различно отколкото на истинското състезание. 1,2 и 4-та ми се видяха лесни. 5-та е гадна, но след час-два гледане се сещаш да търсиш f като [an] и се решава. 3-та ми казаха, че е лесна (което ме съмнява) и не съм я решавал. 6-та изглежда супер гадна а и явно е, щом никой не я е решил, а българският отбор е силен по геометрия. Има много факти за тази конструкция (правата през допирните точки минава през центъра на вписаната окръжност, правата през центровете май също от някъде минаваше), нито един от които мога да докажа и които сигурно се иползват.

[Станислав]

А, да. Беше забранено и да се ползва Теоремата на Виктор - Тебо без доказателство. Тя гласи, че центърът на вписаната окръжност лежи на правата [tex]IJ[/tex]. И, между другото, [tex]f(n)[/tex] не е във вида [tex]\lfloor an \rfloor[/tex], ами [tex]\lfloor a(n+1)\rfloor[/tex] и с ирационално [tex]a[/tex]..

[Baronov]

Прав си, разбира се за 5-та. Може би е добре да напишем как се сеща човек за това [tex]\frac{-1 +\sqrt{5}}{2}[/tex]. Търсим f във вида [an]. Заместваме в условието разделяме на n и пускаме n да клони към безкрайност. Важният факт, който се използва е, че [tex]lim_{n \to \infty} \frac{[an]}{n} = a[/tex]. После, понеже така намереното а е по-малко от 1, а f(1) = 1, то трябва да се вземе f(n) = [a(n+1)].

[Станислав]

Аз говорих с Краси от Разград и той каза, че е забелязал закономерност с редицата на Фибоначи, а където има Фибоначи там има и златно сечение...(в случая [tex]a=(\varphi)^{-1}[/tex])

[Karamata]

Емо, от къде ти хрумва, че трябва да търсиш функции f(n)=[an]? Не е ли по-логично и по-лесно да докажеш, че f(n) е ненамаляваща и после да използваш някои други разсъждения как нараства?

Имам предвид :

Ако сме доказали, че f(n) ? f(n-1) ? ... ? f(1), то е ясно, че f(s) - f(s-1) = 1 + f(f(s-2)) - f(f(s-1)) ? 1 поради f(f(s-1)) ? f(f(s-2)) за всяко s ? n+1. Следователно, ако имахме f(n) > f(n+1), то 1 < f(f(n))-f(f(n-1)) ? f(n) - f(n-1) ? 1 - противоречие. Така по индукция следва, че f(n) е ненамаляваща + това, че или f(n) = f(n-1), или f(n) = f(n-1) + 1.

При f(n) = f(n-1) [tex]\Leftrightarrow[/tex] 1 + f(f(n-2)) = f(f(n-1)) [tex]\Rightarrow[/tex] f(n-1) = f(n-2) + 1 (тъй като не може да са равни), както и това, че f(n+1) = n+1 - f(f(n)) = f(n)+1. Тоест, имаме ситуацията f(n-2) + 1 = f(n-1) = f(n) = f(n+1) - 1. (1)

Също така ако имаме 3 последователни нараствания - f(n-1) + 1 = f(n) = f(n+1) - 1 = f(n+2) - 2, то f(f(n-2)) = f(f(n-1)) = f(f(n)) = f(f(n+1)) или полагайки v = f(n-1), все едно f(v) = f(v+1) = f(v+2) - противоречие с (1). Следователно, имаме най-много 2 последователни скока (+1). (2) (Toва не ни е нужно, но все пак е интересно да се отбележи.)

Сега остава да приложим индукция:
f( n + f(n) ) = n + f(n) - f( f( n-1 + f(n) ) ).
* Aко f(n) = f(n-1), f( n + f(n) ) = n + f(n) - f( f( n-1 + f(n-1) ) ) = n + f(n) - f(n-1) = n - поради индукционното предположение f( n-1 + f(n-1) ) = n-1.
* Aко f(n) = f(n-1) + 1, то f( n + f(n) ) = n + f(n) - f( f( n + f(n-1) ) ). Сега имаме две възможности - или f( n + f(n-1) ) = f( n-1 + f(n-1) ) = n-1, или f( n + f(n-1) ) = f( n-1 + f(n-1) ) + 1 = n. Вторият вариант очевидно ни дава f( n + f(n) ) = n.
Ако f( n + f(n-1) ) = n - 1 = f( n-1 + f(n-1) ) , то oт (1) следва, че f( n + f(n-1) + 1 ) = (n-1) + 1 = n = f( n + f(n) ) от една страна и от друга - f( n + f(n) ) = n + f(n) - f( f( n + f(n-1) ) ) = n + f(n) - f( n-1 ) = n+1 - невъзможно, тъй като f(n) e функция (обратната ? релация е инекция).

Тоест от f( n-1 + f(n-1) ) = n-1 [tex]\Rightarrow[/tex] f( n + f(n) ) = n за всяко естествено n.

[allier]

Аз лично бих направил решението на karamata, далеч по-логично е ... Въпреки че задачата като цяло е известна, 2001-2002 беше давана на националната олимпиада на Иран, само че с функцията f(x-1) ...

[pitboss]

Добре де, тая 5та е дори по-лесна от това което Karamata е предложил макар че и то е достатъчно лесно. Не виждам смисъл да търсим затворен вид на f попринцип. Първото разсъждение на Karamata направо си го копирам

Ако сме доказали, че f(n) ? f(n-1) ? ... ? f(1), то е ясно, че f(s) - f(s-1) = 1 + f(f(s-2)) - f(f(s-1)) ? 1 поради f(f(s-1)) ? f(f(s-2)) за всяко s ? n+1. Следователно, ако имахме f(n) > f(n+1), то 1 < f(f(n))-f(f(n-1)) ? f(n) - f(n-1) ? 1 - противоречие. Така по индукция следва, че f(n) е ненамаляваща + това, че или f(n) = f(n-1), или f(n) = f(n-1) + 1.

Сега задачата е на два реда.

1 сл. Нека [tex]f(f(n-1) + 1) = f(f(n-1)) = n - f(n)[/tex]. Тогава [tex]f(n - f(n)) = f(f(f(n-1))) = f(n-1) + 1 - f(f(n-1) + 1) = f(n-1) + 1 - (n - f(n))[/tex] или [tex]f(n - f(n)) + n - f(n) = f(n-1) + 1[/tex]. [tex]f[/tex]-ваме и става [tex]f(f(n - f(n)) + n - f(n)) = f(f(n-1) + 1) = f(f(n-1)) = n - f(n)[/tex].

2сл. Нека [tex]f(f(n-1) + 1) = f(f(n-1)) + 1[/tex]. Аналогично на по-горе имаме [tex]f(f(n - f(n)) + n - f(n)) = f(f(n-1)) = n - f(n)[/tex].

Понеже [tex]f[/tex] приема всяка естествена стойност, [tex]f(f(\cdot))[/tex] също приема всяка стойност и следователно [tex]n - f(n)[/tex] също приема всяка естествена стойност.