Maths Olympiad Prep

Library / /31 of 57

Combinatorics Difficulty 6.9 National olympiad Prove it Russia

Some cells of a 100×100100 \times 100 desk contain a token. We call a cell beautiful if the total number of tokens in its neighbors is even (two cells are neighbors if they share a common side). Can it appear that there exists exactly one beautiful cell? (K. Knop)

В некоторых клетках доски 100 × 100 стоит по фишке. Назовём клетку красивой, если в соседних с ней по стороне клетках стоит чётное число фишек. Может ли ровно одна клетка доски быть красивой? (К. Кноп)

Solution

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

Доказательство. Раскрасим клетки доски в шахматном порядке; можно считать, что XX — чёрная. Для начала рассмотрим одну из диагоналей, проходящих через XX; пусть AA и BB — центры двух крайних клеток этой диагонали, а CC и DD — точки, симметричные им относительно центра доски. Тогда обозначим через SS множество всех чёрных клеток, центры которых лежат внутри или на границе прямоугольника ABCDABCD. На рис. 15 показаны возможные виды множества SS на доске 8×88 \times 8 (прямоугольники ABCDABCD обозначены пунктиром).

Figure 1

Множество SS состоит из чётного числа клеток, поскольку количества центров клеток на сторонах ABAB и ADAD имеют разную чётность. Далее, чёрные клетки не имеют соседей в SS, каждая белая клетка внутри ABCDABCD граничит с четырьмя клетками из SS, а каждая белая клетка вне него — либо с нулём, либо с двумя клетками из SS. Итак, множество SS удовлетворяет всем условиям.

Перейдём к решению задачи. Предположим, что существует ровно одна красивая клетка XX. Рассмотрим для этой клетки множество SS из леммы. Для каждой клетки этого множества посчитаем количество фишек в соседних с ней клетках; пусть gg — сумма всех этих количеств. С одной стороны, в SS чётное число клеток, из которых ровно одна красива, а все остальные — нет; поэтому сумма gg нечётна. С другой стороны, каждая клетка с фишкой имеет чётное число соседей в SS, поэтому она даёт чётный вклад в gg; значит, и gg должна быть чётной. Противоречие.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.