Физтех 2024, 11 класс, задача 5
( баллов) Дан клетчатый прямоугольник . Сколькими способами можно закрасить клеток этого прямоугольника так, чтобы закрашенное множество обладало хотя бы одной из следующих симметрий: относительно центра прямоугольника, относительно любой из двух «средних линий» прямоугольника («средней линией» прямоугольника назовём отрезок, соединяющий середины двух его противоположных сторон). Ответ дайте в виде выражения, содержащего не более трёх членов (в них могут входить факториалы, биномиальные коэффициенты).
Ответ. .
Решение. Пусть - центр прямоугольника, а отрезки и - его средние линии. Обозначим множество раскрасок, обладающих симметрией относительно , через , относительно - через , относительно - через .
Согласно формуле включений и исключений
Чтобы получить любую раскраску, входящую в , достаточно выбрать четыре произвольные клетки в верхней половине прямоугольника, после чего клетки в нижней половине получаются симметрией четырёх выбранных клеток относительно . Так как в верхней половине прямоугольника всего клеток, . Любую раскраску из или можно получить, выбрав клетки из в левой половине прямоугольника. Отсюда .
Заметим, что из наличия любых двух симметрий следует третья. Это означает, что .
Чтобы получить любую раскраску, обладающую всеми тремя симметриями, нужно выбрать две точки в одной из четвертей прямоугольника. В этой четверти клеток, поэтому . Следовательно,