Формула включений-исключений
Ошибка.
Попробуйте повторить позже
Дан клетчатый прямоугольник 
. Сколькими способами можно закрасить 8 клеток этого прямоугольника так, чтобы закрашенное
множество обладало хотя бы одной из следующих симметрий: относительно центра прямоугольника, относительно любой из двух "средних
линий"прямоугольника ("средней линией"прямоутольника назовём отрезок, соединяющий середины двух его противоположных
сторон). Ответ дайте в виде выражения, содержащего не более трёх членов (в них могут входить факториалы, биномиальные
коэффициенты).
Источники:
Подсказка 1
Давайте начнём распутывать клубок симметрий с того, что обозначим за A₁ множество восьмёрок симметричных относительно одной горизонтальной средний линии, за A₂ - вертикальной, за B - относительно центра прямоугольника. Давайте подумаем, сколько нам нужно зафиксировать точек для каждой из симметрий и где, чтобы однозначно восстановить всю восьмёрку?
Подсказка 2
Верно, для A₁ нужны 4 точки не выше (не ниже), чем горизонтальная средняя линия, для A₂ - 4 точки не правее (не левее), чем вертикальная средняя линия, для B - 4 точки в любой одной из указанных ранее областей. Теперь стоит задуматься о том, пересекаются ли данные множества или какая-то комбинация симметрий даёт другую симметрию?
Подсказка 3
Верно, если восьмёрка лежит в любых двух множества A₁, A₂, B, то она лежит во всех трёх, отсюда, вспоминая формулу включений-исключений, мы понимаем, что ответ уже очень близко, осталось только его расписать.
Назовем восьмеркой набор из 
клеток. Пусть 
— множество восьмерок, симметричных относительной 
, 
— относительно 
,
— относительно центра прямоугольника. 
и 
это средние линии прямоугольника.
Если выбрать какие-то 
точки в верхней половине прямоугольника, то остальные точки легко находятся в силу одной из
рассматриваемой симметрий относительно 
и центра прямоугольника. Тогда количество элементов во множествах 
будет
одинаковым. Тогда количество элементов в 
будет равно количеству способов выбрать 
очки в одной половине фигуры
относительно 
Остальные 
точки будут располагаются в другой половине. Тогда количество способов равняется
Если восьмерка лежит сразу в 
из 
множеств 
то она лежит и в третьей. Это значит, что пересечение двух множеств или
пусто, или пересекается с третьим.
Чтобы найти ответ надо найти количество элементов в объединении множеств. Используя формулу включений-исключений, получаем, что
где 
— означает количество элементов во множестве 
— искомое число
Если 
точки, лежащие в одной из четвертей прямоугольника, принадлежат пересечению всех 
множеств, то легко восстановить
исходную восьмерку, удовлетворяющую сразу трем симметриям. Тогда можно посчитать количество элементов в пересечении множеств. Это
будет количество способов выбрать 
точки в одной из четвертей прямоугольника, образованной 
и центром прямоугольника.
Следовательно, количество элементов равняется 
Тогда посчитаем 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
