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