Запълвания с домино

[kucheto]

Дадена е правоъгълна решетка с размери [tex]4*n[/tex]. С [tex]a_n[/tex] означаваме броя запълвания с домино на тази решетка. Да се намери най-голямото [tex]n[/tex], за което [tex]a_n<2500.[/tex]

[ptj]

Запълвания без дупки, нали?

[kucheto]

Запълвания без дупки, нали?

Определено.

[kucheto]

Никой ли няма интерес да решава задачата?

[kucheto]

Решение:

Нека за решетката [tex]4*n[/tex] с [tex]A_{p,q}[/tex] бележим реда и колоната на на клетките: [tex]1\le p\le n,\ 1\le q\le 4[/tex]; с [tex]b_n[/tex] бележим броя запълвания на [tex]A_{p,q}[/tex] без 2 ъглови клетки: [tex]A_{n,1}\ \cup\ A_{n,4}[/tex]; с [tex]c_n[/tex] бележим броя запълвания на [tex]A_{p,q}[/tex] без 2 съседни клетки, като едната е ъглова: [tex]A_{n,1}\ \cup\ A_{n,2}[/tex] или [tex]A_{n,3}\ \cup\ A_{n,4}[/tex].

Началните стойности на [tex]a_n,\ b_n,\ c_n[/tex] са: [tex]a_1=1,\ a_2=5,\ b_1=1,\ b_2=1,\ c_1=1,\ c_2=2[/tex].

Ако последния ред на [tex]b_n[/tex] запълним с вертикално домино получаваме [tex]a_{n-1}[/tex], а с хоризонтално - [tex]b_{n-2}[/tex]. Оттук: [tex]b_n=a_{n-1}+b_{n-2}[/tex].

Ако последния ред на [tex]c_n[/tex] запълним с вертикално домино получаваме [tex]a_{n-1}[/tex], а с хоризонтално - [tex]c_{n-1}[/tex]. Оттук: [tex]c_n=a_{n-1}+c_{n-1}[/tex].

Сега да разгледаме [tex]a_n[/tex]: Ако запълним [tex]A_{n,1}\ \cup\ A_{n,2}[/tex] заедно с [tex]A_{n,3}\ \cup\ A_{n,4}[/tex] получаваме [tex]a_{n-1}[/tex] запълвания. Ако запълним [tex]A_{n,1}\ \cup\ A_{n,2}\ +\ A_{n-1,3}\ \cup\ A_{n,3}\ +\ A_{n-1,4}\ \cup\ A_{n,4}[/tex] получаваме [tex]c_{n-1}[/tex] запълвания, но понеже можем да направим и симетричната операция (да заменим 1 с 3 и 2 с 4) получаваме общо [tex]2c_{n-1}[/tex] запълвания. Последният възможен начин, непресичащ се с другите начини за запълвания, е [tex]a_{n-2}[/tex] (при запълване с 4 хоризонтални домина). Оттук: [tex]a_n=a_{n-1}+b_{n-1}+2c_{n-1}+a_{n-2}[/tex].

Сега имаме достатъчно информация и можем да попълним следната таблица, от която получаваме отговор 8:

[tex]\begin{array}{|c| |c| |c| |c| |c| |c| |c| |c| |c| |c|} n & 1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\\hline a_n & 1 & 5 & 11 & 36 & 95 & 281 & 781 & 2245 & 6336\\b_n & 1 & 1 & 6 & 12 & 42 & 107 & 323 & 888 & 2568\\c_n & 1 & 2 & 7 & 18 & 54 & 149 & 430 & 1211 & 3456\\\end{array}[/tex]


Ако в задачата се иска да се установи рекурентна зависимост на [tex]a_n[/tex] само с членове на същата редица, постъпваме по следния начин:

[tex]2c_{n-1}=a_n-a_{n-1}-b_{n-1}=2c_n-2a_{n-1}\Rightarrow 2c_n=a_n+a_{n-1}-a_{n-2}-b_{n-1}[/tex]

[tex]b_{n-1}=a_n-a_{n-1}-a_{n-2}-2c_{n-1}=a_{n-2}+b_{n-3}\\\Rightarrow b_{n-3}=a_n-a_{n-1}-2a_{n-2}-2c_{n-1}=\\=a_n-a_{n-1}-2a_{n-2}-(2a_{n-2}+2c_{n-2})=\\=a_n-a_{n-1}-2a_{n-2}-(3a_{n-2}+a_{n-3}-a_{n-4}-b_{n-3})=\\=a_n-a_{n-1}-5a_{n-2}-a_{n-3}+a_{n-4}+b_{n-3}\\\Rightarrow a_n=a_{n-1}+5a_{n-2}+a_{n-3}-a_{n-4}[/tex]

[drago]

Добре!
А откъде е задачата?

[kucheto]

Добре!
А откъде е задачата?

Отникъде. Гледах една подобна задача (ЕМТ 2010, 11.4), реших да си я усложня и ми дойде идеята за тази.