Областная олимпиада по математике, 2026 год, 10 класс

Дана бесконечная клетчатая бумага, раскрашенная в два цвета (черный и белый) в шахматном порядке. Из этой бумаги вырезается клетчатая фигура, состоящая из 25 белых и 25 чёрных клеток такая, что от любой клетки фигуры можно добраться до любой другой клетки этой же фигуры, переходя только по клеткам фигуры и только через общую сторону (не по диагонали). Какое наибольшее количество доминошек из фигуры можно заведомо вырезать? (Доминошка эта фигурка размера $1\times 2$ или $2 \times 1$.) ( П. Кожевников )

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

Рассмотрим клетки фигуры как вершины связного графа, где соседние по стороне клетки соединены рёбрами. Степень каждой вершины не превышает 4. Возьмём остовное дерево этого графа. В нём всегда есть висячие вершины. У любой невисячей вершины A к ней присоединена хотя бы одна висячая вершина B, и клетки A и B образуют домино.Удаляя такое домино, мы удаляем не более 4 вершин, при этом связность сохраняется. Всего вершин 50, значит, так можно вырезать 12 домино, после чего останутся ещё две соседние клетки, образующие 13-е домино.Следовательно, из фигуры можно вырезать не менее 13 домино.