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

Әр ұяшық үшін, егер сол ұяшықтың түсі қандай болса, оның сондай түсті дәл екі көршісі болатындай, $99\times 99$ тақтасының барлық ұяшықтарын екі түске бояп шығуға бола ма? Егер екі ұяшықтың ортақ қабырғасы болса, ондай ұяшықтарды көрші ұяшықтар деп атаймыз.

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

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