|
На клетчатой доске размером $%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 
sapere aude |
|
Я решил случай $%3 \times N$%. Там получаются уже не два, а четыре разных типа досок, и итоговые соотношения примерно такие вот $%X(n)=X(n-1)-2Y(n-1)-Z(n-1)+T(n-1)$% ($%X$% - это уже разность между $%A$% и $%B$% для соответствующего типа доски). И безусловно, первые значения считаются вручную. Результат, что характерно, тот же: разность принимает либо значение $%1$%, либо значение $%-1$%, причем последовательность разностей периодична с периодом $%8$%. отвечен 1 Июл '15 13:41 
knop И снова +-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
|