Клетки шахматной доски раскрашиваются в три цвета - белый, серый и черный - таким образом, чтобы соседние клетки, имеющие общую сторону, отличались цветом, однако резкая смена цвета (то есть соседство белой и черной клеток) запрещена. Найдите число таких раскрасок шахматной доски (раскраски, совпадающие при поворое доски на 90 и 180 градусов, считаются различными).

задан 21 Июн '14 13:40

Эта задача, на первый взгляд, выглядит довольно сложной. Не исключено, что у неё есть какое-то "хитрое" решение, но оно сразу не придумывается. Но если это задача не по математике, а по программированию, то нужно представить подходящий вычислительный алгоритм. Даже он не столь прост, так как перебирать все варианты здесь нельзя (их слишком много), и надо придумать некий "обходной" путь.

(21 Июн '14 16:58) falcao
10|600 символов нужно символов осталось
2

Тут можно рассуждать так: закрасим клетки серым цветом "по диагонали" (т.е. через 1, если смотреть по горизонтали или вертикали.) Это можно сделать двумя способами (в левом нижнем серая или нет, а остальное автоматически.)

На остальных позициях (их 32)- черные или белые клетки. Их можно раскрасить $%2^{32}$% способами.

Итого $%2^{33}$%.

ссылка

отвечен 21 Июн '14 17:20

изменен 21 Июн '14 17:29

@cartesius: а почему рассматриваются только такие "регулярные" раскраски? Ведь серые клетки могут быть расположены "хаотично".

(21 Июн '14 17:33) falcao

@falcao, Не так уж и хаотично. По правилам раскраски черную или белую клетки могут окружать только серые. Отсюда и возникает такая расстановка серых.

(21 Июн '14 17:52) cartesius

@cartesius: по условию запрещается только соседство белой и чёрной клетки. Поэтому рядом с белой могут стоять и белые, и серые.

(21 Июн '14 17:56) falcao

@falcao, По условию соседние клетки отличаются цветом

(21 Июн '14 17:59) cartesius

@cartesius: да, Вы правы. Я упустил это условие, сосредоточившись только на отсутствии "резких" переходов. То-то мне показалось, что задача в таком виде выглядела очень сложной.

Интересно было бы подсчитать на компьютере число вариантов для "искажённой" версии.

(21 Июн '14 18:07) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×851

задан
21 Июн '14 13:40

показан
432 раза

обновлен
21 Июн '14 18:07

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

по почте:

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

по RSS:

Ответы

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

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