7-я олимпиада им. Шалтая Смагулова, 7 класс, 3 тур

Можно ли покрасить все клетки доски $99\times 99$ в два цвета так, чтобы для каждой клетки имелись ровно две соседние по стороне клетки, покрашенные в тот же цвет, что и сама клетка? (Соседними считаются клетки, имеющие общую сторону.)

Комментарий/решение

Будем называть клетки "соседями", если они имеют общую сторону. Давайте красить доску в чёрно-белые цвета. Тогда рассмотрим для начала черный цвет( для белого цвета аналогично). Пусть клетка это вершина, а общая сторона у клеток покрашенных в один цвет - ребро. Тогда получается у каждой черной клетки степень вершины 2, т.е наш граф поделиться на несколько замкнутых циклов, в которых количество ребер очевидно четное( т.к мы должны с этой вершины начать пути, в той и закончить). Тогда получается вершин черных четное количество. Аналогично для белых, тогда всего клеток четное количество, но $99*99$ очевидно нечётное.