Азиатско-Тихоокеанская математическая олимпиада, 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$

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