5. Zadatak

Prebrojimo sve moguće tražene rasporede analizirajući postupno kako možemo popuniti tablicu krenuvši iz gornjeg lijevog ugla. Kvadrat $2\times2$ u gornjem lijevom uglu možemo popuniti na $4!$ načina.

Odaberimo jedno moguće popunjavanje tog kvadrata i prebrojimo na koliko načina možemo tablicu $n\times n$ popuniti do kraja. Neka su u prvom redu prva dva polja označena s 1 i 2, a u drugom s 3 i 4, tim redom.

1	2
3	4

Brojanje ćemo podijeliti u disjunktne slučajeve, a vrlo korisna će biti sljedeća lema.

Lema. Neka se u nekom stupcu (retku) u tri uzastopna polja $A,B,C$ pojavljuju tri različita broja $a,b,c$. Tada su na jednoznačan način određeni brojevi $a',b',c'$ u tri polja $A',B',C'$ (susjedna poljima $A,B,C$ redom) u stupcu desno (tj. u retku ispod) od promatranog stupca (retka).

Zaista, označimo li s $d$ preostali četvrti broj (različit od $a,b,c$) onda je $a'=c,b'=d,c'=a$.

a	b	c
c	d	a

a	c
b	d
c	a

Uvedimo oznaku $a_k,k=2,\ldots,n$ za broj mogućih popunjavanja tablice uz fiksiranu $k\times k$ podtablicu u gornjem lijevom kutu na način da su u neparnim retcima naizmjence jedinice i dvojke (počevši s 1), a u parnim recima naizmjence trojke i četvorke (počevši s 3). Zovimo takve $k\times k$ podtablice regularnim. Očito je $a_n=1$ (čitava tablica je već ispunjena), a tražimo $a_2$.

Pokažimo da za svaki $k=2,\ldots,n-1$ vrijedi $a_k=2^{n-k}+a_{k+1}$.

Naime, neka je dana regularna $k\times k$ podtablica u gornjem lijevom dijelu $n\times n$ tablice. Slučajevi za $k$ paran ili neparan se pokazuju analogno uz zamjenu $1\longleftrightarrow3$, $2\longleftrightarrow4$, pa bez smanjenja općenitosti pretpostavimo da je $k$ paran.

Promatramo 3 slučaja.

Prvi slučaj. Prva dva polja u $(k+1)$-om retku označimo s 2, 1 u tom redoslijedu. Tada su prema lemi jedinstveno određena sva polja u $(k-1)$-om, $k$-tom i $(k+1)$-om retku. U $(k-1)$-om i $(k+1)$-om retku moraju biti naizmjence jedinice i dvojke, a u $k$-tom retku moraju biti naizmjence trojke i četvorke (Slika 1, lijevo).

1	2	1	2
3	4	3	4
1	2	1	2	1	2	1
3	4	3	4	3	4	3
2	1	2	1	2	1	2

1	2	1	2	1	2	1
3	4	3	4	3	4	3
1	2	1	2	1	2	1
3	4	3	4	3	4	3
2	1	2	1	2	1	2

Slika 1: Primjer za $n=7,k=4$.

Ako se u nekom retku pojavljuju samo dva broja onda se lako vidi da se u svim retcima moraju pojavljivati točno dva broja. Zato zaključujemo da je jedinstveno određena čitava gornja $(k+1)\times n$ podtablica (Slika 1, desno).

Nadalje, u svakom idućem retku moći će se pojaviti samo po dva različita broja. U svakom od preostalih $n-k-1$ redaka prva dva polja možemo označiti na dva načina (u neparnom retku s 1, 2 ili 2, 1, a u parnom s 3, 4 ili 4, 3.), pa je ukupan broj popunjavanja u ovom slučaju $2^{n-k-1}$.

Drugi slučaj. Prva dva polja u $(k+1)$-om stupcu označimo s 3, 1 u tom redoslijedu. Ovaj slučaj tretiramo potpuno analogno kao prvi, te je ukupan broj traženih popunjavanja i u ovom slučaju $2^{n-k-1}$.

1	2	1	2	3
3	4	3	4	1
1	2	1	2	3
3	4	3	4	1
		1	2	3
		3	4	1
		1	2	3

1	2	1	2	3
3	4	3	4	1
1	2	1	2	3
3	4	3	4	1
1	2	1	2	3
3	4	3	4	1
1	2	1	2	3

Slika 2: Primjer za $n=7,k=4$.

Primjetimo da sada $(k+1)$-i redak počinje oznakama 1, 2 u tom redoslijedu te su prvi i drugi slučaj disjunktni.

Treći slučaj. Preostala nam je samo mogućnost da su prva dva polja u $(k+1)$-om retku označena s 1, 2 u tom redoslijedu, a prva dva polja u $(k+1)$-om stupcu označena s 1, 3. Polja u $(k+1)$-om retku i $(k+1)$-om stupcu koja se nalaze unutar $(k+1)\times(k+1)$ podtablice u gornjem lijevom dijelu tablice su jedinstveno određena. Vidimo da smo dobili $(k+1)\times(k+1)$ regularnu podtablicu, pa se ostatak tablice dalje može popuniti na $a_{k+1}$ načina.

1	2	1	2	1
3	4	3	4	3
1	2	1	2	1
3	4	3	4	3
1	2	1	2	1

Slika 3: Primjer za $n=7,k=4$.

Zbog disjunktnosti slučajeva zaista vrijedi $a_k=2^{n-k-1}+2^{n-k-1}+a_{k+1}=2^{n-k}+a_{k+1}$.

Na kraju zaključujemo da je $$a_2=2\cdot2^{n-3}+a_3=2\cdot2^{n-3}+2\cdot2^{n-4}+a_4=\cdots=2\cdot2^{n-3}+2\cdot2^{n-4}+\cdots+2\cdot2+a_n=2(2^{n-2}-1)+1=2^{n-1}-1$$ jer je $a_n=1$.

Dakle, traženi broj je $4!\cdot(2^{n-1}-1)$.

Drugi način.

Analognim načinom zaključivanja dokazujemo sljedeću karakterizaciju ispravnih popunjenja tablice:

Karakterizacija.

Da bi tablica bila ispravno popunjena, nužno je i dovoljno da je ispunjen barem jedan od uvjeta:

(a) Svaki redak tablice naizmjence sadrži točno dva broja, pri čemu se jedan par brojeva javlja u parnim, a drugi par brojeva u neparnim retcima.

(b) Svaki stupac tablice naizmjence sadrži točno dva broja, pri čemu se jedan par brojeva javlja u parnim, a drugi par brojeva u neparnim stupcima.

Prebrojimo sva moguća ispravna popunjenja tablice.

Radi jednostavnosti prebrojavanja, fiksirajmo brojeve u kvadratu u gornjem lijevom kutu tablice. Te brojeve možemo permutirati na $4!=24$ načina, pa ćemo s tim brojem pomnožiti na kraju sva moguća ispravna popunjenja tablice koja slijede iz ovakvog početka. Prebrojimo koliko ispravnih popunjenja imamo s ovako fiksiranim početkom, i to onih koja zadovoljavaju uvjet $(a)$ ili uvjet $(b)$ iz karakterizacije.

Uz fiksirani početak, popunjenja koja zadovoljavaju uvjet $(a)$ ima $2^{n-2}$, jer za prvo polje u svakom od redaka, od trećeg do $n$-tog, imamo dva moguća izbora. Na isti način, uz fiksirani početak, popunjenja koja zadovoljavaju uvjet $(b)$ ima $2^{n-2}$.

Moramo pogledati i koliko ima popunjenja koja, uz fiksiran početak, zadovoljavaju oba uvjeta. No, takvo je jedno jedino; to je ono popunjenje kod kojeg su svaki drugi redak (i stupac) identični.

Konačno, zaključujemo da je broj ispravnih popunjenja $24\cdot(2\cdot2^{n-2}-1)=24\cdot(2^{n-1}-1)$.