Азиатско-Тихоокеанская математическая олимпиада, 2021 год

На клетчатом столе $32\times 32$ в левой нижней клетке сидит мышь (и смотрит вперёд на верхнюю от нее клетку), а еще в нескольких других клетках разложены куски сыра. Мышь начинает двигаться. Она двигается вперед до тех пор, пока не попадет в клетку с сыром, далее мышь съедает часть сыра, поворачивает направо и продолжает ползти прямо. Назовем множество клеток, содержащих сыр, хорошим, если в этом процессе мышь попробует каждый кусок сыра ровно по одному разу и после этого свалится со стола. Докажите, что:
   (a) Не существует хорошего множества, состоящего из 888 клеток.
   (b) Существует хорошее множество, состоящее из не менее чем 666 клеток.

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

Оценку в части (a) можно улучшить до $820$, что соответствует плотности сыра $\frac45$ для любой прямоугольной сетки.

Предположим, имеется $C$ кусков сыра. После того, как мышь упадет со стола, дайте ей вернуться в исходное положение вдоль внешней стороны стола, следуя тем же правилам, что и раньше (разрешено только движение вперед и поворот направо), чтобы ее путь назад не пересекался. Легко видеть, что его путь будет иметь $4\left\lfloor\frac{C+5}4\right\rfloor$ углов. При этом все самопересечения пути мыши происходят в ячейке таблицы, в которой нет сыра. С другой стороны, при этом путь мыши пересекает сам себя как минимум $\left\lfloor\frac{C+1}4\right\rfloor$ раз. Отсюда следует, что $C+\left\lfloor\frac{C+1}4\right\rfloor\le1024\ подразумевает C\le819$.

Уважаемый Nebayan ваше утверждение про то что в каждом $2 \times 2$ максимум $3$ сыра ошибочно

Контрпример: ($\blacksquare -$ с сыром, $\square -$ без, $\bigstar -$ изначальная точка)

$\square\square\square\square\square\square \dots$

$\square\square\square\square\square\square \dots$

$\square\square\blacksquare\square\square\blacksquare \dots$

$\blacksquare \square\square\blacksquare\blacksquare\square \dots$

$\square\square\blacksquare\blacksquare\blacksquare\blacksquare \dots$

$\bigstar\square\square\square\square\square \dots$

Сорри не заметил сейчас чуть чуть переделаю