14-я Международная Жаутыковская олимпиада, 2018 год

Крокодил загадал четыре клетки таблицы $2018\times 2018$, образующие прямоугольник со сторонами 1 и 4. Медведь может выбрать в таблице любой квадрат, образованный 9 клетками, и спросить, есть ли в нём хотя бы одна из загаданных клеток. За какое наименьшее количество таких вопросов Медведь наверняка сможет получить утвердительный ответ? ( А. Голованов )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ: ${673^2-1\over 2}=226464$.
Решение. Квадрат, о котором Медведь задаёт вопрос, и все его клетки будем называть {\it проверенными}. Положение клетки в таблице будем задавать номерами строки и столбца, в которых она стоит: клетка $(x, y)$ стоит на пересечении $x$-й строки и $y$-го столбца.
Докажем, что за $673^2-1\over 2$ вопросов можно попасть в задуманный прямоугольник даже на доске $2019\times 2019$. Разрежем эту доску на квадраты $3\times 3$ и раскрасим эти квадраты в шахматном порядке так, чтобы угловые квадраты были белыми. Тогда достаточно проверить все чёрные квадраты $3\times 3$: ни в какой строке и ни в каком столбце нет четырёх белых клеток подряд.
Чтобы доказать, что это количество вопросов необходимо, отметим все клетки вида $(3m+1, 3n+1)$, где $0\leq m, n\leq 672$. Очевидно, никакие две отмеченных клетки не лежат в одном квадрате $3\times 3$. С другой стороны, если две отмеченных клетки находятся в одном ряду на расстоянии 3 (то есть одна из них $(x, y)$, а другая $(x, y+3)$ или $(x+3, y)$), то хотя бы одна из них должна быть проверена (потому что если они обе не проверены, то не проверены и две клетки между ними, и на непроверенных клетках можно разместить прямоугольник $1\times 4$).
Поэтому достаточно указать $673^2-1\over 2$ пар отмеченных клеток на расстоянии 3. В качестве таких пар можно взять пары $(6k+1, 3n+1)$, $(6k+4, 3n+1)$, $0\leq k\leq 335$, $0\leq n\leq 672$, и пары $(2017, 6n+1)$, $(2017, 6n+4)$, $0\leq n\leq 335$.