|
|
 |
Условие
В некоторых клетках доски 100×100 стоит по фишке. Назовём клетку красивой, если в соседних с ней по стороне клетках стоит чётное число фишек.
Может ли ровно одна клетка доски быть красивой?
Решение
Лемма. Для любой клетки доски X существует такое множество S, состоящее из чётного количества клеток и содержащее X, что у каждой клетки доски чётное число соседей лежит в S.
Доказательство. Раскрасим клетки доски в шахматном порядке так, чтобы X стала чёрной. Рассмотрим одну из диагоналей, проходящих через X; пусть A и B – центры двух крайних клеток этой диагонали, а C и D – точки, симметричные им относительно центра доски. Обозначим через S множество всех чёрных клеток, центры которых лежат внутри или на границе прямоугольника ABCD. На рисунке показаны возможные виды множества S на доске 8×8 (прямоугольники ABCD обозначены пунктиром).
Предположим, что существует ровно одна красивая клетка X. Рассмотрим для этой клетки множество S из леммы. Для каждой клетки этого множества посчитаем количество фишек в соседних с ней клетках; пусть g – сумма всех этих количеств. С одной стороны, в S чётное число клеток, из которых ровно одна красива, а все остальные – нет; поэтому сумма g нечётна. С другой стороны, каждая клетка с фишкой имеет чётное число соседей в S, поэтому она была сосчитана чётное число раз. Значит, сумма g чётна. Противоречие.
Ответ
Не может.
