ВСОШ 2026, региональный этап, 10 класс, задача 2
( баллов) У Даши и у Саши есть по доске . Даша укладывает на свою доску не перекрывающихся плиток (так, что плитки занимают клеток, а одна клетка остаётся не покрытой). Пусть у неё есть способов сделать это. Саша красит на своей доске единичных отрезков-границ между соседними клетками так, чтобы для каждой клетки доски хотя бы одна её сторона была покрашена. Пусть у Саши способов сделать это. Докажите, что .
Ответ
Решение. Рассмотрим одну из Сашиных покрасок. В ней каждый из покрашенных отрезков принадлежит двум клеткам. Поскольку на доске всего клеток, видим, что у всех клеток, кроме некоторой одной клетки , покрашена ровно одна сторона, а у клетки покрашены две стороны. Пусть в клетке покрашены стороны и , где — граница между клетками и , а — граница между клетками и .
Сопоставим этой Сашиной покраске две Дашиных укладки следующим образом. Первая укладка такая: забудем про отрезок и положим доминошек , у которых средними линиями служат все покрашенные Сашей отрезки, кроме . (Понятно, что доминошки не перекрываются, так как иначе, если две доминошки имели бы общую клетку, то у этой клетки нашлись бы две покрашенные стороны.) Аналогично забудем про отрезок и получим вторую Дашину укладку.
С другой стороны, при указанном сопоставлении конкретная Дашина укладка сопоставлена не более чем четырем Сашиным покраскам, так как в такой Сашиной покраске обязательно покрашены единичных отрезков — средних линий Дашиных доминошек, а кроме того, покрашена одна из сторон клетки, не покрытой Дашиными доминошками (а таких сторон — , или ).
Итак, каждой из Сашиных покрасок поставлено в соответствие ровно две из Дашиных укладок, а каждая из укладок соответствует не более чем четырем Сашиным покраскам. Отсюда , и мы получили , что и требовалось.