Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

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