Сколькими способами прямоугольник $%3\times20$% можно разрезать на квадратики $%2\times2$% и полоски $%1\times4$%?

задан 25 Янв '18 21:59

изменен 25 Янв '18 22:42

falcao's gravatar image


254k23650

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

Из соображений площади, если прямоугольник $%3\times n$% можно покрыть фигурками из условия, то $%n$% кратно 4. Обозначим через $%a_n$% ответ на вопрос задачи для случая $%3\times(4n)$%. Требуется найти $%a_5$% Удобно также положить $%a_0=1$%.

Введём ещё одну вспомогательную величину $%b_n$% при $%n\ge2$%. Это будет число способов покрыть квадратиками и полосками прямоугольник $%3\times(4n)$%, к которому добавили квадратик $%2\times2$% слева сверху. Ясно, что $%b_0=1$%.

Пусть $%n\ge1$%. Рассмотрим левую верхнюю клетку прямоугольника $%3\times(4n)$%. Допустим, что она покрыта квадратиком $%2\times2$%. Тогда снизу от него расположена плитка $%1\times4$%. Оставшуюся часть можно покрыть $%b_{n-1}$% способами. Аналогичная ситуация получается, если квадратик покрывает левую нижнюю клетку. Остаётся случай, когда левая верхняя и левая нижняя клетки покрыты плитками $%1\times4$%. Тогда между ними лежит такая же плитка, а оставшаяся часть покрывается $%a_{n-1}$% способом. Отсюда имеем рекуррентную формулу $%a_n=a_{n-1}+2b_{n-1}$%.

Теперь выведем рекуррентную формулу для $%b_n$%. Если крайние левые столбцы покрыты квадратиком, то оставшуюся часть можно покрыть $%a_n$% способами. Если это не так, то в двух верхних строках лежат параллельные плитки $%1\times4$%. Две клетки слева в самой нижней строке также заняты такой плиткой. Всё остальное покрывается $%b_{n-1}$% способом. Отсюда $%b_n=a_n+b_{n-1}$% при $%n\ge1$%.

По этим формулам можно всё последовательно рассчитать. Можно чуть упростить вычисления, заметив, что $%a_1=3$% и $%a_n=4a_{n-1}-a_{n-2}$% при $%n\ge2$%. Тогда $%a_0,...,a_5$% принимает вид $%1,3,11,41,153,571$%. При желании, можно также указать общую формулу для нахождения $%a_n$%.

ссылка

отвечен 26 Янв '18 2:39

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

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

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

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

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

отмечен:

×29

задан
25 Янв '18 21:59

показан
1672 раза

обновлен
26 Янв '18 2:39

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

по почте:

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

по RSS:

Ответы

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

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