Математикадан Эйлер олимпиадасы, 2014-2015 оқу жылы, Дистанциялық кезеңнің 3-ші туры


Екі ойыншы келесі ойын ойнайды. Бір жүрісте $1001 \times 1001$ тақтаның қандай-да бір шаршысына бір тас қоюға болады (басында тақта бос болған; бір шаршыда кез келген мөлшерде тас жата алады). Ойыншылар кезектесіп жүреді. Егер қандай-да бір ойыншының жүрісінен кейін қандай-да бір бағанда немесе қандай-да бір қатарда тас саны 5-тен асып кетсе, онда сол ойыншы ұтылған болып саналады. Дұрыс ойында қарсыласының ойнағанына қарамастан, қай ойыншы ұтады: бірінші жүрісті жүрген ойыншы ма, әлде екінші ма?
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. Первый.
Решение 1. До того, как на доску выложен 5005-ый камешек, первый находит строку и столбец, в которых находится менее пяти камешков (такие обязательно найдутся), и кладёт камешек в клетку на их пересечении. Если второй не ошибся раньше, после того, как на доску будет положен 5005-ый камешек (а его, как и все нечётные, положит первый), мы приходим к ситуации, в которой в каждой строке и каждом столбце лежит ровно по 5 камешков. В ней второй проигрывает, какой бы ход он ни сделал.

Комментарии от администратора Комментарии от администратора №2.     Ответ. Первый.
Решение 2. Пусть первым ходом первый положит камешек в цен-тральную клетку доски, а затем кладет каждый свой камешек симметрично относительно центра доски последнему камешку соперника. Тогда если первый делает ход в строку или столбец, содержащий центральную клетку, там после этого хода будет нечетное числу камешков, а если камешек первого оказался в строке или столбце, не содержащем центральную клетку, там после его хода станет столько же камешков, сколько в симметричной относительно центра доски строке (столбце). Таким образом, если после хода первого в какой-то строке или каком-то столбце оказалось больше 5 камешков, то и до его хода были строка или столбец, где находилось больше 5 камешков. Значит, первый при такой игре не может проиграть, а так как игра конечна, то второй рано или поздно проиграет.