Задачка

[the cool]

Нека к е естествено число и нека имаме неограничен брой правоъгълници от вида 2 на к.
Дадено е естествено число n. Нека b(n) e броят начини правоъгълник 2 на n да се покрие с правоъгълници от вида 2 на к.
Ясно е, че b(1)=1, b(2)=3, b(3)=6. Изчислете b(7).

[Реклама]

[Titu_Andrescu]

Мисла, че задачата не е зададена коректно

[the cool]

Кое по-точно?

[the cool]

Може би така ще е по-ясно:

Нека к е естествено число и имаме неограничен брой правоъгълници с размери 2 х к.
Дадено е естествено число n. Нека b(n) e броят начини по който правоъгълник 2 х n може да се покрие с правоъгълници от вида 2 х к.
Знаем че b(1)=1, b(2)=3, b(3)=6. Изчислете b(7).

[Titu_Andrescu]

В задачата не е казано как един или повече правоъгълника покриват друг. Това може да стане по безброино много начина, някак се губи идеята

[the cool]

При n = 1 правоъгълник с размери 2 х 1 може да се покрие единствено с правоъгълник 2 х 1, защото дадените ни правоъгълници с размер 2 х к са: 2 х 1, 2 х 2, 2 х 3...От всички такива имаме безброй много, но само 2 х 1 покрива 2 х 1 точно без да излиза от очертанието т.е при покриване на правоъгълник с размери 2 х n от правоъгълници с размери 2 х к, не трябва да имаме препокриване на участващите правоъгълници и освен това всеки от покриващите го правоъгълници не трябва да излиза от рамката на покривания.
Затова получаваме че при n=2 имаме 3 начина за покриване:
1. Да го покрием с един правоъгълник 2 х 2.
2. Да го покрием с 2 хоризонтално разположени правоъгълници с размери 2 х 1.
3. Да го покрием с 2 вертикално разположени правоъгълници с размери 2 х 1.
т.е. b(2) = 3 и търсим b(7).

По-добре не мога да го обясня.