Олимпиадная задача Кнопа: Красивая клетка на доске 100×100 по математике для 8–10 классов

  Лемма. Для любой клетки доски X существует такое множество S, состоящее из чётного количества клеток и содержащее X, что у каждой клетки доски чётное число соседей лежит в S.

  Доказательство. Раскрасим клетки доски в шахматном порядке так, чтобы X стала чёрной. Рассмотрим одну из диагоналей, проходящих через X; пусть A и B – центры двух крайних клеток этой диагонали, а C и D – точки, симметричные им относительно центра доски. Обозначим через S множество всех чёрных клеток, центры которых лежат внутри или на границе прямоугольника ABCD. На рисунке показаны возможные виды множества S на доске 8×8 (прямоугольники ABCD обозначены пунктиром).

  МножествоSсостоит из чётного числа клеток, поскольку количества центров клеток на сторонахABиADимеют разную чётность. Чёрные клетки не имеют соседей вS, каждая белая клетка внутриABCDграничит с четырьмя клетками изS, а каждая белая клетка внеABCD– либо с нулём, либо с двумя клетками изS. Итак, множествоSудовлетворяет всем условиям.   Предположим, что существует ровно одна красивая клетка X. Рассмотрим для этой клетки множество S из леммы. Для каждой клетки этого множества посчитаем количество фишек в соседних с ней клетках; пусть g – сумма всех этих количеств. С одной стороны, в S чётное число клеток, из которых ровно одна красива, а все остальные – нет; поэтому сумма g нечётна. С другой стороны, каждая клетка с фишкой имеет чётное число соседей в S, поэтому она была сосчитана чётное число раз. Значит, сумма g чётна. Противоречие.