Эйлер атындағы олимпиада, 2014-2015 оқу жылы, аймақтық кезеңнің 2 туры

Өлшемі $20 \times 20$ болатын шахмат тақтасына, барлық бос шаршылар ұрылатындай, 220 ат фигурасы қойылған. Бұрынғы шаршылармен қоса алғанда, пайда болған бос шаршылар да ұрылатындай, тақтадан 20 ат фигурасын алып тастауға болатынын дәлелдеңдер. Ат фигурасы «Г» әріпімен ұратынын естеріңізге саламыз (суретті қара).

( С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Будем убирать коней с доски по одному следующим образом. Если на очередном шаге можно убрать какого-то коня так, что оставшиеся будут бить все свободные поля, сделаем это. Если после некоторого шага останется 200 коней, мы получим требуемое. Предположим, что в некоторый момент ни одного коня с сохранением нужного условия убрать нельзя. Разобьём клетки доски на пары, соединённые ходом коня (это можно сделать, например, как на рисунке справа). Назовём пару полной, если в ней стоят два коня, и пустой, если в ней нет коней; пусть на доске $f$ полных и $e$ пустых пар. Рассмотрим любого коня $R$, стоящего в полной паре. Если его убрать, его клетка окажется побитой парным к нему; значит, останется непобитой некоторая другая клетка $C$. Ясно, что она находится в пустой паре и бьётся только конём $R$; сопоставим клетку $C$ коню $R$. Ясно, что разным коням сопоставлены разные клетки; поэтому общее количество сопоставленных клеток (оно не больше $2e$) равно $2f$, то есть $e \geq f$. Но общее количество коней равно $2f+(200-e-f) = 200+(f-e) \leq 200$. Значит, в момент, когда ни одного коня убрать нельзя, мы уже добились требуемого.