Една пермутациянна числата от 1 до 8 ще наречем печатна...

[Гост]

задача 1.

Един шеф пише всеки ден по 8 писма и ги номерира в среда 1, 2, 3, 4, 5, 6, 7, 8. Когато напише писмо, той го поставя най отгоре в една кутия. Когато секретарката му е свободна, тя взима най горното писмо от кутията и го печати. Понякога секретарката успява да отпечати писмото преди шефът да постави следващото, а понякога той успява да постави едно или повече писма през това време. Секретарката винаги успява да отпечата всички писма до края на работния си ден.
Една пермутациянна числата от 1 до 8 ще наречем печатна ако е възможно писмата да бъдат отпечатани в този ред. Колко са всички печатни пермутации.


задача 2.

Дадена е таблица 2 x 2015.
Всяко поле на таблица трябва да се оцвети в син, зелен или жълт цвят така, че всеки две съседни (с обща страна) полето да са разноцветни. По колко начина може да се оцвети таблицата?


Предварително благодаря за решенията! :) :) :)

[drago]

В 6-ти клас не е ли малко рано такива задачи да бъдат давани за домашно?

[drago]

По втора: Ако имаш таблица [tex]2\times n[/tex] може да докажеш по индукция, че броя на начините е [tex]2\cdot 3^n[/tex].

За първа: Сложи [tex]n[/tex] вместо 8. Нека нареждаме [tex]n[/tex] "[tex]+[/tex]"-са и [tex]n[/tex] "[tex]-[/tex]" са в редичка. На всяко слагане на писмо от шефа слагаме [tex]+[/tex], а на всяко махане на писмо от секретарката - [tex]-[/tex]. Условието е във всеки начален сегмент(от началото на редицата до някъде) броя на плюсовете да е не по-малък от броя на минусите. Броя на тези подредби е точно броя на "печатните" пермутации. От своя страна, това е точно n-тото число на Каталан: [tex]\frac{1}{n+1} \binom{2n}{n}[/tex].