Сколько клеток должно быть помечено на доске размером 8х9, чтобы в любых пяти подряд идущих клетках по горизонтали

Zvezdnaya_Galaktika

52

Чтобы решить эту задачу, мы можем использовать метод контрпримеров для определения минимального числа помеченных клеток на доске размером 8x9.

Предположим, что у нас есть доска размером 8x9 и только 13 клеток помечены. Расставим эти помеченные клетки случайным образом по доске.

Теперь давайте рассмотрим горизонтальные, вертикальные и диагональные линии, состоящие из пяти клеток. Верхняя граница доски необходимо рассматривать отдельно.

1. Горизонтальные линии:
a) Верхняя граница: Есть только одна горизонтальная линия на верхней границе. Если все пять клеток на этой линии не помечены, то крайняя слева непомеченная клетка и её правая соседняя клетка образуют группу пяти подряд идущих клеток без помеченной клетки. Поэтому на этой горизонтальной линии должны быть помечены все пять клеток.
б) Остальные горизонтальные линии: В каждой горизонтальной линии, находящейся ниже верхней границы, есть по 9 клеток. Поскольку у нас только 8 помеченных клеток, то хотя бы одна горизонтальная линия будет содержать менее 5 помеченных клеток. Поэтому невозможно обеспечить наличие помеченной клетки в каждой горизонтальной линии, если у нас всего 13 помеченных клеток.

2. Вертикальные линии: Есть 9 вертикальных линий. Если на какой-либо из этих линий не помечена ни одна клетка, то этой вертикальной линии невозможно обеспечить наличие помеченной клетки в любой пяти подряд идущей клетке.

3. Диагональные линии: Существует несколько главных диагоналей с постоянным отношением номера строки и столбца. На главных диагоналях нашей доски размером 8x9 невозможно обеспечить наличие помеченной клетки в каждой пяти подряд идущей клетке, поскольку у нас всего 13 помеченных клеток.

Таким образом, мы доказали, что невозможно разместить 13 помеченных клеток на доске размером 8x9 так, чтобы в любых пяти подряд идущих клетках по горизонтали, вертикали или диагонали обязательно была помеченная клетка.

С учетом этого вывода, для обеспечения наличия помеченной клетки в любых пяти подряд идущих клетках по горизонтали, вертикали или диагонали на доске размером 8x9 необходимо пометить минимум 14 клеток.