Научно-методически статии
СЕДЕМНАДЕСЕТА ЖАУТИКОВСКА ОЛИМПИАДА ПО МАТЕМАТИКА, ИНФОРМАТИКА И ФИЗИКА АЛМАТИ, 7-12 ЯНУАРИ 2021
Резюме. Статията съдържа обзор на състезателните теми по математика от двата дни на 17-тата Международна Жаутиковска олимпиада с виртуален домакин Казахстан и българското участие в нея. Включени са условията на задачите и решенията на първите трима автори на статията, в някои случаи с повече от един подход за дадена задача.
Ключови думи: Математически състезания за гимназисти; ученически решения
От 7 до 12 януари 2021 г. се състоя дистанционното издание на международна Жаутиковска олимпиада с виртуален домакин Казах Олимпиадата се провежда всяка година от 2005 г. насам и е едно о престижните състезания, които съчетават трите области – матема информатика и физи ка. Поради онлайн изданието на събитието тази го дина в него имаше рекорден брой участници (близо 1000), почти по-голям от миналогодишния. Четиристотин и двадесет от тях се сърев новаваха в областта на математиката. България бе представена от 36 ученици от 8 гимназии. Нашите математици завоюваха 13 медала – златни, 2 сребърни и 5 бронзови, сред които 5 златни и 1 сребърен шестимата ученици от Софийската математическа гимназия. Форма на олимпиадата е същият като този на Международната олимпиада математика, тоест два дена, в които участниците разполагат с по часа и половина за три задачи. Предлагаме на вниманието на чита условията на задачите и нашите решения. Авторовите решения могат бъдат намерени на официалния сайт на състезанието izho.kz
Първи ден
Задача 1. Да се докаже, че съществува естествено число n, за което остатъкът от делението на \(3^{\mathrm{n}}\) с \(2^{\mathrm{n}}\) е по-голям от \(10^{2021}\).
Задача 2. Даден е изпъкнал вписан шестоъгълник \(A B C D E F\), в който \(B C=\) \(E F\) и \(C D=A F\). Диагоналите \(A C\) и \(B F\) се пресичат в точка \(Q\), а диагоналите \(E C\) и \(D F\)– в точка \(P\). Върху отсечките \(D F\) и \(B F\) са взети съответно точки \(R\) и \(S\) така, че \(F R=P D\) и \(B Q=F S\). Отсечките \(R Q\) и \(P S\) се пресичат в точка \(T\). Да се докаже, че правата \(T C\) разполовява диагонала \(B D\).
Задача 3. Дадено е естествено число \(\mathrm{n} \geq 2\). Елвин има таблица \(\mathrm{n} \times \mathrm{n}\), по-пълнена с реални числа (всяка клетка от таблицата съдържа точно едно число). Ще наричаме топ множество множество от n клетки на таблицата, разположени както в \(n\) различни реда, така и в \(n\) различни стълба. Нека за всяко топ множество сумата от n-те числа, записани в клетките, които образуват множеството, е неотрицателна.
На всеки ход Елвин избира ред, стълб и реално число a, след което към всяко число от избрания ред прибавя a, а от всяко число в избрания стълб изважда a (по този начин числото в пресечната клетка на избраните ред и стълб не се променя). Да се докаже, че Елвин може да направи последователност от ходове така, че всички числа в таблицата да станат неотрицателни.
Втори ден
Задача 4. В триъгълник \(A B C\) е вписана окръжност с радиус \(r\). Окръжности с радиуси \(r_{1}, r_{2}, r_{3}\) (където \(r_{1}, r_{2}, r_{3} \lt r\) ) са вписани съответно в ъглите \(A, B, \mathrm{C}\) така, че всяка от тях се допира външно до вписаната в триъгълника окръжност. Да се докаже, че \(r_{1}+r_{2}+r_{3} \geq r\).
Задача 5. На парти с 99 гости домакините Ан и Боб играят следната игра (домакините не влизат в броя на гостите). В кръг са разположени 99 стола и първоначално всички гости обикалят около столовете. Домакините правят ходове последователно, като се редуват. На един ход домакинът, който е наред, заповядва на някого от правостоящите гости да седне на незает стол c; ако някой от столовете, съседни на c, е вече зает, то същият домакин заповядва гостът, седящ на съседния на c стол, да стане (ако и двата стола, съседни на c, са вече заети, домакинът избира единия от двамата и му нарежда да стане). Всички нареждания се изпълняват незабавно. Ан започва първа; нейната цел е след краен брой ходове да бъдат заети поне \(k\) стола. Определете най-голямото \(k\), за което Ан може да постигне целта си, независимо от играта на Боб.
Задача 6. Нека \(P(x)\) е неконстантен полином от степен n с рационални коефициенти, който не може да бъде представен като произведение на два неконстантни полинома с рационални коефициенти. Докажете, че броят на полиномите \(Q(x)\) от степен по-малка от n с рационални коефициенти, такива че \(P(x)\) дели \(P(Q(x))\) :
а) е краен
б) не надвишава \(n\).
Решения
Задача 1. Ще разгледаме два подхода за решаване на задачата, с приложение съответно на теорията на числата и алгебрата.
Първо решение (теория на числата): нека с \(\nu_{2}(x)\) означаваме степента на 2 в каноничното разлагане на \(x\). Ще докажем по индукция, че \(\nu_{2}\left(3^{2^{m}}-1\right)=m+2\) за всяко \(m \in \mathbb{N}\). Базата на индукцията при \(m=1\) e ясна. Нека за \(m=k\) имаме, че \(\nu_{2}\left(3^{2^{k}}-1\right)=k+2\). Като използваме, че \(3^{2^{k+1}}-1=\left(3^{2^{k}}-1\right)\left(3^{2^{k}}+1\right)\) и \(3^{2^{k}}+1 \equiv 2(\bmod 4)\), получаваме \(\nu_{2}\left(3^{2^{k+1}}-1\right)=\nu_{2}\left(3^{2^{k}}-1\right)+\nu_{2}\left(3^{2^{k}}+1\right)=k+3\), с което индукцията е завършена.
Да вземем \(n\) от вида \(2^{m}\) за някое \(m \in \mathbb{N}: 2^{m+2} \gt 10^{2021}\), и нека \(3^{2^{m}}=\)
\(q 2^{2^{m}}+r\), където \(q, r \in \mathbb{N}\) и \(r\) е остатъкът. Ще разгледаме уравнението по \(\bmod 2^{m+2}\). Вече доказахме, че \(3^{2^{m}} \equiv 1\left(\bmod 2^{m+2}\right)\), а \(2^{m+2}\) дели \(2^{2^{m}}\) от \(m+2 \lt 2^{m}\), откъдето следва \(r \equiv 1\left(\bmod 2^{m+2}\right)\). Ако допуснем, че \(r=1 \Rightarrow 3^{2^{m}} \equiv 1\left(\bmod 2^{2^{m}}\right)\), което е противоречие с \(\nu_{2}\left(3^{2^{m}}-1\right)=m+2\).
Следователно \(r \geq 2^{m+2}+1\) и от избора на \(m\left(2^{m+2} \gt 10^{2021}\right)\) сме готови.
Второ решение (алгебра): Нека \(3^{n}=a_{n} 2^{n}+b_{n}\) за всяко \(n \in \mathbb{N}\) и \(a_{n}, b_{n} \in \mathbb{N}\). Да допуснем, че редицата от остатъци \(\left\{b_{n}\right\}\) е ограничена отгоре от някое \(M \in \mathbb{N}\), т.е. \(b_{n} \leq M\) за всяко \(n\). Избираме \(n: 2^{n} \gt 3 M\). Имаме, че
\[ 3^{n+1}=3 \cdot 2^{n} a_{n}+3 b_{n}=2^{n+1} \cdot \tfrac{3 a_{n}}{2}+3 b_{n}=2^{n+1} \cdot\left\lfloor\tfrac{3 a_{n}}{2}\right\rfloor+3 b_{n}+2^{n+1} \cdot\left\{\tfrac{3 a_{n}}{2}\right\} \] Остатъкът \(3 b_{n}+2^{n+1} \cdot\left\{\tfrac{3 a_{n}}{2}\right\}\) е по-малък от \(2^{n+1}\), защото \(3 b_{n} \leq 3 M \lt 2^{n}\) от избора на \(n\) и \(2^{n+1} \cdot\left\{\tfrac{3 a_{n}}{2}\right\} \leq 2^{n+1} \cdot \tfrac{1}{2}=2^{n}\) Оттук следва, че този остатък е всъщност \(b_{n+1} \Rightarrow b_{n+1}=3 b_{n}+2^{n+1} \cdot\left\{\tfrac{3 a_{n}}{2}\right\} \geq 3 b_{n}\). Като приложим полученото \(k\) пъти, достигаме до \(b_{n+k} \geq 3^{k} b_{n}\). Достатъчно е да изберем \(k\) : \(3^{k} \gt M\) и ще достигнeм достигнем до противоречие от \(M \geq b_{n+k}\), т.е. допускането, че редицата от остатъци е ограничена, е грешно и задачата е решена.
Задача 2.
Първо да отбележим, че от \(A F=C D\) и \(B C=E F \Rightarrow A C \| D F\) и \(B F \| C E\), тъй като \(A B C D E F\) е вписан шестоъгълник. Оттук достигаме до \(F Q C P\) – успоредник. Като използваме условията \(F S=B Q\) и \(F R=D P\), получаваме и че \(S B C P\) и \(R Q C D\) са успоредници. Сега нека изберем точка \(M\) такава, че \(B M D C\) да бъде успоредник. Мотивацията за този избор е, че \(M C\) разполовява \(B D\), и следователно е достатъчно само да докажем \(T \in M C\).
Имаме \(R Q C D\) и \(M B C D\)– успоредници \(\Rightarrow R Q B M\) също е успоредник. Значи \(F S \| R M\), но \(F S=B Q=R M\), т.е. и \(F S M R\) е успоредник. Оттук най-лесният начин да покажем, че \(T \in M C\), е чрез теоремата на Менелай, затова построяваме \(L=M S \cap P C\). От обратната теорема на Менелай за \(\triangle P S L\) и правата \(T C\) е достатъчно да докажем \(\tfrac{P C}{C L} \cdot \tfrac{L M}{M S} \cdot \tfrac{S T}{T P}=1\). Като вземем предвид, че \(F S M R\) и \(F Q C P\) са успоредници, имаме \(\tfrac{P C}{C L}=\) \(\tfrac{F Q}{Q S}\) и \(\tfrac{L M}{M S}=\tfrac{P R}{R F}\), с което търсеното твърдение става еквивалентно на \(\tfrac{F Q}{Q S} \cdot \tfrac{P R}{R F} \cdot \tfrac{S T}{T P}=1\). Последното е вярно от Менелай за \(\triangle P S F\) и правата \(R Q\) и сме готови.
Друг начин да се довърши задачата е да използваме теоремата на Дезарг за \(\triangle Q S M\) и \(\triangle R P C . T=Q R \cap S P \Rightarrow T \in M C\) е еквивалентно на \(Q S \cap\) \(R P=F, S M \cap P C=L\) и \(Q M \cap R C\) да лежат на една права, т.е. искаме \(Q M, R C\) и \(F L\) да се пресичат в една точка. Нека \(K=Q M \cap F L\) и ще докажем, че \(K \in R C\). От теорема на Менелай за \(\triangle F S L\) и права \(K Q\) получаваме \(\tfrac{F Q}{Q S} \cdot \tfrac{S M}{M L} \cdot \tfrac{L K}{K F}=1\), а от успоредниците \(F Q C P\) и \(F S M R\) имаме \(\tfrac{F Q}{Q S}=\tfrac{P C}{C L}\) и \(\tfrac{S M}{M L}=\tfrac{F R}{R P} \Rightarrow \tfrac{P C}{C L} \cdot \tfrac{L K}{K F} \cdot \tfrac{F R}{R P}=1\). От обратната теорема на Менелай за \(\triangle F P L\) и точки \(R, K\) и \(C\) получаваме \(K \in R C\) и сме готови.
Задача 3. Да отбележим, че след всеки ход сборът на числата във всяко топ множество се запазва, и че размяната на редове или колони не променя условието. Ще докажем задачата по индукция:
1) \(n=2\)
От условието имаме \(a+d \geq 0\) и \(b+c \geq 0\).
Като прибавим \(c\) към горния ред и извадим от лявата колона, на мястото на \(b\) и \(c\) получаваме съответно неотрицателното \(b+c\) и 0. Аналогично прибавяме \(d\) към горния ред и вадим от дясната колона, с което четирите числа на таблицата стават неотрицателни.
2) \(n=k\)
Да допуснем, че за всяка таблица \(k \times k\), изпълняваща условието, съществува поредица от ходове, с която можем да направим всички числа в таблицата неотрицателни.
3) \(n=k+1\)
Разгеждаме топ множество с най-малък сбор (нека той е \(S\) ) на числата в него измежду тези на таблицата \((k+1) \times(k+1)\). Можем да изберем една клетка от това множество и да направим числото вътре равно на \(S\). Това се постига, като за всяка от другите клетки в топ множеството изваждаме числото в нея от нейната колона и го прибавяме в реда, в който се съдържа избраната клетка. Тъй като можем да разместваме колоните и редовете, без ограничение на общността считаме, че избраната клетка е в долния десен ъгъл на таблицата.
Сега да разгледаме \(k \times k\) таблицата, която не включва най-долния ред и най-дясната колона. Всяко от топ множествата в нея образува заедно с долния десен ъгъл топ множество в голямата таблица \((k+1) \times(k+1)\)
⇒ сборовете на числата във всяко топ множество на \(k \times k\) таблицата са неотрицателен (и поне един от тях е равен на 0), в противен случай съществува топ множество със сбор по-малък от \(S\) в таблицата \((k+1) \times(k+1)\), което е противоречие с минималността на \(S\). Следователно можем да използваме индукционното предположение за \(k \times k\) таблицата и да направим всички числа в нея неотрицателни (това не променя най-дясната долна клетка от голямата таблица). Имаме топ множество със сбор на числата 0 в \(k \times k\) таблицата ⇒ всички числа в него трябва да станат равни на 0.
Отново с разместване на редовете и колоните можем да позиционираме тези нули по главния диагонал, спускащ се от горе ляво до долу дясно.
Нека сега числата на най-долния ред на \((k+1) \times(k+1)\) таблицата да са съответно \(a_{1}, a_{2}, \ldots, a_{k}, S\) отляво надясно. Таблицата изглежда по следния начин (с + бележим неотрицателно число):
Сега за всяко \(i \in 1,2, \ldots, k\) правим следната последователност от операции:
Намаляваме числата от последния ред с \(b_{i}\) и увеличаваме тези от \(i\)-тата колона отляво надясно. После изваждаме от \(i\)-тата колона \(b_{i}\) и прибавяме в най-горния ред съответно. Накрая намаляваме най-горния ред с \(b_{i}\) и увеличаваме най-дясната колона.
Вследствие на тези операции числата в \(k \times k\) таблицата и това в долния десен ъгъл на основната се запазват, а всички числа от \(a_{1}, a_{2}, \ldots, a_{k}\) освен \(a_{i}\) намаляват с \(b_{i}\). Остава да подберем \(b_{1}, b_{2}, \ldots, b_{k}\) така, че \(a_{1}, a_{2}, \ldots, a_{k}\) да станат нули. За целта трябва за всяко \(i\) да е изпълнено:
\[ \begin{gathered} a_{i}=\sum_{j=1}^{k} b_{j}-b_{i} \\ \Rightarrow \sum_{j=1}^{k} a_{j}=(k-1) \sum_{j=1}^{k} b_{j} \\ \Rightarrow b_{i}=\tfrac{\sum_{j=1}^{k} a_{j}}{k-1}-a_{i} \end{gathered} \] При такъв избор на \(b_{i} a_{i}\) стават нули. Сега остава да забележим, че можем да образуваме следното топ множество с всяко едно число от най-дясната колона: взимаме него, симетричното му спрямо главния диагонал от най-долния ред (което ще е нула) и \(k-1\) нули от диагонала (без тази, която е на реда на избраната клетка и на колоната на срещуположната ?). Понеже сборът на числата в това топ множество е неотрицателен, а всички освен избраното са нули, то числата в дясната колона трябва да са неотрицателни и индукцията е завършена.
Задача 4. Ще изразим отношенията \(\tfrac{r_{i}}{r}, i=1,2,3\), и ще докажем, че сумата им е поне 1. Ще покажем две решения на задачата, като използваме означенията от чертежите.
Първо решение
Нека \(S\) е допирната точка на двете окръжности и \(S K\) е общата им вътрешна допирателна \((K \in A B) . K F\) и \(K S\) са допирателни към вписаната в \(\triangle A B C\) окръжност, значи \(K F=K S\). Аналогично и \(K S=K T \Rightarrow K\) е среда на \(F T\). Нека \(\angle A B C=\beta\). Сега имаме
\[ \begin{aligned} & \angle T K I_{2}=\tfrac{\angle T K S}{2}=\tfrac{90^{\circ}-\tfrac{\beta}{2}}{2}=45^{\circ}-\tfrac{\beta}{4} \\ & \angle F I K=\tfrac{\angle F I S}{2}=\tfrac{90^{\circ}-\tfrac{\beta}{2}}{2}=45^{\circ}-\tfrac{\beta}{4} \end{aligned} \] Оттук следва, че \(\triangle F I K \sim T K I_{2}\), и от подобието получаваме \(r \cdot r_{2}=\) \(F K \cdot K T=F K^{2}\). Намираме отношенито между радиусите: \[ \tfrac{r_{2}}{r}=\tfrac{\tfrac{F K^{2}}{r}}{r}=\left(\tfrac{F K}{r}\right)^{2}=\tan ^{2} \angle F I K=\tan ^{2}\left(45^{\circ}-\tfrac{\beta}{4}\right) \]
Аналогично извеждаме отношенията \(\tfrac{r_{1}}{r}\) и \(\tfrac{r_{3}}{r}\), откъдето е достатъчно да докажем, че
\[ \tan ^{2}\left(45^{\circ}-\tfrac{\alpha}{4}\right)+\tan ^{2}\left(45^{\circ}-\tfrac{\beta}{4}\right)+\tan ^{2}\left(45^{\circ}-\tfrac{\gamma}{4}\right) \geq 1 \] Имаме \(\tfrac{\mathrm{d}^{2}}{\mathrm{~d} x^{2}} \tan ^{2} x=\tfrac{2\left(1+2 \sin ^{2} x\right)}{\cos ^{4} x} \gt 0\) за \(x \in\left(0, \tfrac{\pi}{4}\right)\), т.е. \(\tan ^{2} x\) е изпъкнала функция в дадения интервал. Като имаме предвид това, можем да приложим неравенството на Йенсен:
\(\begin{aligned} & \tfrac{1}{3} \cdot \tan ^{2}\left(45^{\circ}-\tfrac{\alpha}{4}\right)+\tfrac{1}{3} \cdot \tan ^{2}\left(45^{\circ}-\tfrac{\beta}{4}\right)+\tfrac{1}{3} \cdot \tan ^{2}\left(45^{\circ}-\tfrac{\gamma}{4}\right) \stackrel{?}{\geq} \\ & \stackrel{?}{\geq} \tan ^{2}\left(\tfrac{1}{3} \cdot\left(45^{\circ}-\tfrac{\alpha}{4}+45^{\circ}-\tfrac{\beta}{4}+45^{\circ}-\tfrac{\gamma}{4}\right)\right)=\tan ^{2} 30^{\circ}=\left(\tfrac{\sqrt{3}}{3}\right)^{2}=\tfrac{1}{3} \end{aligned}\)
Като умножим по 3 двете страни, достигаме до търсеното неравенство, с което доказателството е завършено.
Второ решение
От \(I_{1} L \| I K\) имаме \(\tfrac{A I_{1}}{A I}=\tfrac{I_{1} L}{I K}\) (Талес). Като заместим с \(r\) и \(r_{1}\) получаваме \(\tfrac{A I_{1}}{A I_{1}+r+r_{1}}=\tfrac{r_{1}}{r}\), откъдето намираме \(A I_{1}=r_{1} \cdot \tfrac{r+r_{1}}{r-r_{1}}\). Сега \(\sin \tfrac{\alpha}{2}=\) \(\tfrac{I_{1} \dot{L}}{A I_{1}}=\tfrac{r-\dot{r}_{1}}{r+r_{1}}\) (след като съкратим на \(r_{1}\) ) и ако означим \(\tfrac{r_{1}}{r}\) 1 с \(a_{1}\), достигаме до \(\sin \tfrac{\alpha}{2}=\tfrac{1-a_{1}}{1+a_{1}}\). Последното е еквивалентно на \(\sin \tfrac{\alpha}{2} \cdot\left(1+a_{1}\right)=2-\) \(\left(1+a_{1}\right)\), или \(1+a_{1}=\tfrac{2}{1+\sin \tfrac{\alpha}{2}}\). По същия начин разсъждаваме за \(a_{2}\) и \(a_{3}\). Искаме да докажем, че \(a_{1}+a_{2}+a_{3} \geq 1\); като заместим с полученото за \(a_{i}\) и разделим на 2, неравенството става еквивалентно на:
\[ \tfrac{1}{1+\sin \tfrac{\alpha}{2}}+\tfrac{1}{1+\sin \tfrac{\beta}{2}}+\tfrac{1}{1+\sin \tfrac{\gamma}{2}} \geq 2 \]
Прилагаме неравенството на Коши-Шварц:
\[ \tfrac{1}{1+\sin \tfrac{\alpha}{2}}+\tfrac{1}{1+\sin \tfrac{\beta}{2}}+\tfrac{1}{1+\sin \tfrac{\gamma}{2}} \geq \tfrac{9}{3+\sin \tfrac{\alpha}{2}+\sin \tfrac{\beta}{2}+\sin \tfrac{\gamma}{2}} \]
⇒ Достатъчно е да докажем, че \(\sin \tfrac{\alpha}{2}+\sin \tfrac{\beta}{2}+\sin \tfrac{\gamma}{2} \leq \tfrac{3}{2}\)
\[ \begin{aligned} \left(\sin \tfrac{\alpha}{2}+\sin \tfrac{\beta}{2}\right) & +\sin \tfrac{\gamma}{2}=2 \sin \tfrac{\alpha+\beta}{4} \cos \tfrac{\alpha-\beta}{4}+\cos \tfrac{\alpha+\beta}{2} \leq \\ & \leq 2 \sin \tfrac{\alpha+\beta}{4}+1-2 \sin ^{2} \tfrac{\alpha+\beta}{4} \end{aligned} \]
Като положим \(\sin \tfrac{\alpha+\beta}{4}=x\), лесно се вижда, че \(2 x+1-2 x^{2} \leq \tfrac{3}{2}\), защото последното е еквивалентно на \((2 x-1)^{2} \geq 0\).
Задача 5. Отговор: 34
Ще наричаме преместване хода, при който един от играчите поставя някой от гостите на стол c и кара някой от седналите на \(\mathrm{c}-1\) или \(\mathrm{c}+1\) (приемаме, че такъв има) да стане. Да отбележим, че ако Ан направи преместване, то Боб може да направи обратното преместване и да вър- не играта в същата позиция.
Нека Боб е разделил столовете в началото на 33 групи по 3 последователни стола. Стратегията му е следната: ако Ан направи преместване, Боб връща позицията; ако Ан добави гост (без да кара друг да става) в крайното поле на някоя група, Боб прави преместване така, че да бъде зает столът в средата на групата; ако Ан добави гост в средата на някоя група, Боб добавя друг в средата на някоя незаета група (ако такава има). Така Боб гарантира, че седналите са в центъра на групите.
Да разгледаме момента, в който са заети средите на всичките 33 групи. Ако Ан е на ход, тя може да направи единствено преместване, при което Боб връща позицията и броят седнали хора ще е 33. Ако Боб е на ход, той трябва да направи преместване в някоя от групите, при което Ан може да сложи 34-ти човек в другия край на групата. Сега Боб прави обратното преместване на миналия си ход и от тази позиция Ан вече може да прави само премествания, които Боб връща. С това Боб ограничава броя на седналите до 34.
Ще докажем, че Ан може да постави 34 гости. Ако вземем разделянето на 33 групи от по 3 стола на Боб, Ан може да гарантира, че във всяка група има седнал човек, като поставя гост в центъра на незаетите групи, с което може да си осигури поне 33 седнали. Да забележим, че броят на седналите гости на всеки ход или остава същият, или се увеличава с 1. Нека сега разгледаме момента, в който Ан не може да добави повече хора. Ако на кръга вече има 34 човека, сме готови. Да допуснем, че седналите са 33 и няма последователност от три незаети стола (иначе Ан поставя 34-тия човек в средата на тази последователност). ⇒ Седналите гости ще са разположени през две празни места. Считаме, че те се намират в центровете на 33-те групи от по 3 стола и ще наричаме тази позиция лоша. Ще видим как трябва да играе Ан, за да избегне лоша позиция. Имаме два варианта за хода на Боб, след който Ан може да попадне в нея.
Вариант 1 Боб е добавил 33-тия човек в средата на оставащата група, тоест на предния си ход Ан е поставила човек в средата на някоя от другите групи. Нека вместо това тя го постави в единия край на групата (\(\mathrm{X}_{1}\) ). Получава се следната конфигурация:
Да отбележим, че има незаета последователност от 5 стола (петорка). Ако Боб добави нов човек, Ан няма да се окаже в лоша позиция. Ако Боб направи преместване, така че зает да стане столът отдясно на \(\mathrm{X}_{1}\), Ан поставя човек в средата на петорката, с което Боб попада в лоша позиция и след хода му Ан може да разполжи 34-тия човек. Ако Боб направи преместване на \(X_{2}\) в лявото поле, се освобождава друга последователност от 3 незаети стола, в чиято среда Ан слага 33-тия човек, и тъй като има петорка, Боб не може да докара Ан до лоша позиция. В случай че Боб не премести \(\mathrm{X}_{1}\) или \(\mathrm{X}_{2}\), Ан слага на хода си в средата на тройката незаети между \(\mathrm{X}_{1}\) и \(\mathrm{X}_{2}\) и има последователност от поне 4 незаети стола от петорката преди следващия ход на Боб, поради което тя няма да се озове в лоша позиция след хода му. Оставяме на читателите да разгледат случая, в който, преди Ан да сложи 32-рия човек, гостите седят през две и има поредица от 8 незаети сто решава аналогично.
Вариант 2 Боб е направил преместване, с което Ан е попаднала в лоша позиция. Тогава след предходния ход на Ан позицията трябва да е била като по-горе, само че без петорка (c O не бележим седнал човек):
Ако на хода си Ан е поставила човек на \(X_{1}\), нека вместо това го постави на дясното поле, при което Боб ще е в лоша позиция. Ако Ан е играла на \(X_{2}\), нека вместо на това място постави човек на \(O\). Ако пък е играла, слагайки някой от другите гости, нека вместо това постави госта така, че да седи през едно, а не през две места от съседния седящ човек. И в двата случая има две двойки хора, седящи през едно, тоест с хода си Боб не може да вкара Ан в лоша позиция. Така Ан си гарантира 34 седящи.
Задача 6. Нека \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{\mathrm{n}}\) са комплексните корени на полинома \(P(x)\). Първо ще докажем следното твърдение: ако \(P(x)\) не може да се представи като произведение на два полинома с рационални коефициенти, той е минимален полином за всеки от корените си. Да допуснем противното, т.е. за някой корен \(\alpha_{\mathrm{j}}\) минималният му полином е \(P_{I}\). Като заместим \(x\) с \(\alpha_{\mathrm{j}}\) в \(P(x)=P_{1}(x) \cdot R(x)+T(x)\), получаваме \(T\left(\alpha_{\mathrm{j}}\right)=0\), и тъй като степента на \(T\) е по-ниска от тази на \(P_{l}\), а \(P_{l}\) е минимален за \(\alpha_{\mathrm{j}}\), то \(T(x)\) трябва да е равен на 0.
Последното обаче няма как да бъде изпълнено, тъй като \(P\) е неразложим, и допускането ни е грешно. Вследствие заключаваме и че всички корени на \(P\) са различни (ако има кратен корен, той трябва да е корен и на производната на \(P\), което е в противоречие с твъдението).
а) Ако \(P(x)\) дели \(P(Q(x))\), трябва \(Q\left(\alpha_{\mathrm{k}}\right)\) също да е корен на \(P(x)\) за всяко \(k=1,2, \ldots n\) (от \(P\left(\alpha_{\mathrm{k}}\right)=0 \Rightarrow P\left(Q\left(\alpha_{\mathrm{k}}\right)\right)=0\) ). Оттук следва, че стойностите на \(Q\) в \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{\mathrm{n}}\) образуват редица \(\alpha_{i 1}, \alpha_{i 2}, \ldots, \alpha_{i n}\), всеки член на която е корен на \(P\) (не задължително различни). Броят на тeзи редици е \(n\) и всяка от тях определя единствен полином \(Q\) (иначе от \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}\)– различни ⇒ съществуват два различни полинома със степен по-малка от \(n\), които минават през n фиксирани точки, а това е невъзможно). Следователно броят на възможните полиноми \(Q(x)\) не надвишава \(n^{n}\).
б) Както отбелязахме в предната подточка, за всеки полином \(Q\), който изпълнява условието, \(Q\left(\alpha_{1}\right)\) трябва да е равно на \(\alpha_{\mathrm{i}}\) за някое \(i\). Същестува обаче най-много един полином \(Q\) със степен, по-малка от n и рационални коефициенти, такъв че \(Q\left(\alpha_{1}\right)=\alpha_{j}\). В противен случай, ако \(Q_{1}\left(\alpha_{1}\right)=Q_{2}\left(\alpha_{1}\right)\) \(=\alpha_{\mathrm{j}}, \alpha_{1}\) ще е корен на ненулевия полином \(Q_{1}-Q_{2}\), който е с рационални коефициенти и степен, по-малка от \(n\), а това е в противоречие с твърдението, че \(P\) е минимален за \(\alpha_{1}\). С това броят на възможните полиноми \(Q(x)\) не надвишава \(n\).