Бесконечные конструкции (игры, клетки, множества)

Подсказка 1

Следить за тем, что конь обойдет все оставшиеся клетки бесконечной доски довольно трудно. Каким способом можно избавиться от рассмотрения бесконечности в данной задаче?

Подсказка 2

Будет следить за некоторым квадратом N на N исходной доски, назовем его здравым. Предположив, что конь может побывать в каждой клетке исходной доски, получим, что он должен был оказаться в каждой клетке здравого квадрата. Как можно оценить количество клеток, выкинутых из здравого квадрата и какой цвет они имеют?

Подсказка 3

Ясно, что все выкинутые клетки одного цвета (пусть чёрного). Также понятно, что внутри здравого квадрата не меньше, чем [N/100]² выкинутых клеток, ведь вдоль каждой стороны точно поместится [N/100] клеток. Теперь необходимо с другой стороны оценить разность количества пройденных соответственно черных и белых клеток. Как будет выглядеть траектории движения коня внутри здравой доски?

Подсказка 4

Ясно, что все выкинутые клетки одного цвета (пусть чёрного). Также понятно, что внутри здравого квадрата не меньше, чем [N/100]² выкинутых клеток, ведь вдоль каждой стороны точно поместится [N/100] клеток. Теперь необходимо с другой стороны оценить разность количества пройденных соответственно черных и белых клеток. Как будет выглядеть траектории движения коня внутри здравой доски?

Подсказка 5

Ясно, что конь может несколько раз уходить и заново заходить на здравый квадрат. Назовём цепочкой следующий набор последовательных ходов: конь входит в квадрат, делает несколько ходов и выходит из него. Разберите все возможные случаи цветов соответственно первой и последней клетки каждой цепочки? Чему равна разность пройденных белых и черных клеток в цепочки, в каждом случае?

Подсказка 6

Если цепочка начинается с чёрной клетки, то тогда суммарно в цепочке чёрных клеток не меньше, чем белых. Если цепочка начинается с белой клетки и заканчивается чёрной, то в неё поровну чёрных и белых клеток. Рассмотрим теперь цепочки, которые начинаются и заканчиваются белой клеткой, в них на одну белую клетку больше. Таким образом, белых клеток в пройденной доске превышает количество черных не больше, чем на количество цепочек, которые начинаются и заканчиваются в белой клетке. Как можно оценить количество таких цепочек?

Подсказка 7

Заметим, что количество искомых цепочек не больше, чем количество пар черных клеток из двухклеточной каёмки квадрата, которое равно 4N+8. Осталось показать, что неравенство 4N+8≥[N/100]² неверно при достаточно больших N.