2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Число способов раскраски доски 3х3
Сообщение10.04.2013, 14:49 
Аватара пользователя
Каждую клетку доски $3\times 3$ нужно покрасить либо в белый, либо в чёрный цвет.
Сколькими способами это можно сделать так, чтобы не нашлось двух соседних по стороне белых клеток?

Кроме длинного бестолкового перебора, дающего ответ 63, не вижу никакой идеи.
Наведите, пожалуйста, на мысль.

 
 
 
 Re: Число способов раскраски доски 3х3
Сообщение10.04.2013, 15:10 
Аватара пользователя
А с чего там должен быть короткий и толковый способ? С того, что получилась степень двойки минус один? Дак это небось совпадение.

 
 
 
 Re: Число способов раскраски доски 3х3
Сообщение10.04.2013, 15:16 
Аватара пользователя
ИСН в сообщении #708151 писал(а):
...Дак это небось совпадение.

Вот в том-то и дело, что совпадение. Так как для доски $4\times 4$ ответ будет равен 1234.

 
 
 
 Re: Число способов раскраски доски 3х3
Сообщение10.04.2013, 15:21 
Тут уже нетрудно найти эту последовательность и в OEIS.

 
 
 
 Re: Число способов раскраски доски 3х3
Сообщение10.04.2013, 15:24 
Аватара пользователя
Sender в сообщении #708158 писал(а):
Тут уже нетрудно найти эту последовательность и в OEIS.

Так последовательность найти не проблема. Мне интересно, как её вычислили.

 
 
 
 Re: Число способов раскраски доски 3х3
Сообщение10.04.2013, 15:41 
Ну не зря же там упомянуты числа Фибоначчи. Наверное, сначала рассмотрели одномерный случай, применив теорему Цекендорфа, а потом как-нибудь тривиально обобщили на двумерный. :-)

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group