На клетчатой доске размером $%m × n$% клеток некоторые клетки закрашиваются в чёрный цвет. Раскраска называется правильной, если среди закрашенных нетдвух соседних клеток (соседними называются клетки, имеющие общую сторону). Раскраска, в которой ни одна клетка не закрашена, тоже считается правильной.

Пусть $%A{m,n}$% - это количество правильных раскрасок с чётным числом закрашенных клеток, $%B{m,n}$% - количество правильных раскрасок с нечётным числом закрашенных клеток. Найдите все возможные значения $%A{m,n} − B{m,n}$%.

Вот здесь решение авторов для для частного случая $%2 \times N$%.

Сам решал иначе - непосредственным величины $%D{n} = A{n} - B{n}$%. Несложно показать, что $%D{n} = -D{n-1}$%, ну и подсчитать первые значения надо вручную. В общем, интересно, можно ли решить обобщенную задачу, и если да, то как?

задан 1 Июл '15 4:11

изменен 1 Июл '15 15:06

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

Я решил случай $%3 \times N$%. Там получаются уже не два, а четыре разных типа досок, и итоговые соотношения примерно такие вот $%X(n)=X(n-1)-2Y(n-1)-Z(n-1)+T(n-1)$% ($%X$% - это уже разность между $%A$% и $%B$% для соответствующего типа доски). И безусловно, первые значения считаются вручную. Результат, что характерно, тот же: разность принимает либо значение $%1$%, либо значение $%-1$%, причем последовательность разностей периодична с периодом $%8$%.
$$ 1, \ \ -1, \ \ 1, \ \ 1, \ \ -1, \ \ 1, \ \ -1, \ \ -1 $$

ссылка

отвечен 1 Июл '15 13:41

изменен 1 Июл '15 15:10

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

И снова +-1, интересно. Вот попробовал зафиксировать N и сделать индукцию по k для KxN, но как-то не вышло. Наверное так топорно обобщить не выйдет

(1 Июл '15 22:34) sapere aude
1

Так ведь для доски 1xN бывают не только +-1, но и 0. Или я ошибся? Там всех вместе правильных - число Фибоначчи. Каждое третье - чётное. Следовательно, разность уже не может быть нечётной.

(1 Июл '15 23:17) knop

ну, можно же начинать с некоторого k, необязательно с 1. Хотя это все равно не очень разумная затея, а так согласен для 1хN и впрямь будет 0 - даже вручную проверяется

(1 Июл '15 23:24) sapere aude
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,934
×1,545
×1,148
×50

задан
1 Июл '15 4:11

показан
1206 раз

обновлен
1 Июл '15 23:24

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

по почте:

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

по RSS:

Ответы

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

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