Сколько клеток нужно отметить на клетчатой доске 8 на 8 так, чтобы каждая клетка доски, включая отмеченные, была соседней по стороне с некоторой отмеченной клеткой? Найдите все возможные ответы. Считаем, что клетка не является соседней сама с собой.
Сначала соберёмся с силами и отметим на доске 8 на 8 двадцать клеток, как того требует условие. Например, так, как это показано на рисунке. При этом доска естественным образом разбивается на 10 частей, как это показано жирными линиями на рисунке. Каждая часть состоит из клеток, соседних с данной парой отмеченных.
Теперь, используя построенный пример, докажем, что единственным ответом задачи являются именно 20 клеток. Рассмотрим разбиение доски на 10 частей, указанных в примере. Дальше везде будем называть фигурами именно эти части данного примера. Назовём центральными клетками каждой фигуры те, что отмечены в примере на рисунке. Вспомним, что шахматная доска имеет естественную раскраску клеток в шахматном порядке и рассмотрим в каждой фигуре её чёрную и белую части, состоящие из чёрных и белых клеток этой фигуры соответственно. Заметим, что белая центральная клетка фигуры соседствует только с чёрными клетками только этой фигуры, причём со всеми, и чёрная центральная клетка фигуры соседствует только с белыми клетками только этой фигуры, причём со всеми.
Рассмотрим теперь произвольную разметку клеток на доске, удовлетворяющую условию задачи, и докажем, что каждая фигура содержит ровно две отмеченные клетки, откуда будет следовать ответ задачи. Действительно, если некоторая фигура содержит не меньше трёx отмеченных клеток, то она содержит не меньше двух белых отмеченных, либо не меньше двух чёрных отмеченных, тогда центральная клетка противоположного цвета этой фигуры будет соседней не менее, чем с двумя отмеченными, что противоречит условию. А если некоторая фигура содержит не больше одной отмеченной клетки, то в ней либо не будет белых отмеченных клеток, либо не будет чёрных отмеченных клеток, тогда центральная клетка противоположного цвета этой фигуры вообще не будет соседней ни с какой отмеченной клеткой, что тоже противоречит условию. Следовательно, каждая фигура содержит по две отмеченных клетки, поэтому любой пример содержит ровно 20 отмеченных клеток.
Заметим, что построенный в данном решении пример не единственный, и мы доказывали совсем не то, что отмеченные клетки любого примера совпадают с отмеченными нами. Можно повернуть доску на 90 градусов и получится новый пример, отличный от рассмотренного, но всё равно, любая фигура содержит по две отмеченных клетки из нового примера.
Ответ: 20.
Замечание.
Оценку для 20 можно делать и по-другому, доказав сначала, что число крайних отмеченных клеток не меньше 9 и т. д. Это длинный и опасный путь с перебором частных случаев. При оценивании заявленных решений такого типа нужно очень тщательно оценивать в них каждый шаг, и, если такое решение содержит нерассмотренные случаи или проколы в подсчётах, то оценочная часть решения оценивается не выше, чем в 1 балл.