Сколько способов покрасить доску 8*8 в чёрный и белый цвет, если способы получаемые друг из друга поворотом, считаются одинаковыми?

задан 15 Окт 17:22

10|600 символов нужно символов осталось
0

Такого рода задачи, если они имеют достаточно общий вид, решаются при помощи так называемой леммы Бернсайда. О ней можно прочитать в учебниках алгебры (у Кострикина, например). На форуме также бывали примеры.

Здесь случай более простой, поэтому можно обойтись без специальной теории. Нужно рассмотреть несколько типов раскраски доски.

1) Совсем не симметричная: ни при каком повороте доска не переходит в себя (если это не поворот на 0 градусов).

2) Полусимметричная: доска переходит в себя при центральной симметрии, но не при повороте на 90 градусов.

3) Совсем симметричная: доска переходит в себя при повороте на 90 градусов.

Общее число раскрасок доски равно 2^{64}. В пункте 3) раскрашивается только четверть доски, остальное однозначно. Это даёт 2^{16}. Доски из 2) и 3) центрально симметричны, их вместе 2^{32}. Досок из 1) будет 2^{64}-2^{32}. Досок из 2), соответственно, 2^{32}-2^{16}.

Расстановки первого типа при поворотах дают 4 различных варианта, поэтому первое слагаемое надо разделить на 4, и получится 2^{62}-2^{30}. Во втором случае количество делим на 2, что даёт 2^{31}-2^{15}. Третье 2^{16} берём как есть.

Складывая и упрощая, имеем 2^{62}+2^{30}+2^{15}, что особенно просто выражается в двоичной системе. В десятичной это будет 4611686019501162496.

ссылка

отвечен 15 Окт 17:46

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,320

задан
15 Окт 17:22

показан
51 раз

обновлен
15 Окт 17:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru