5. Zadatak

Marko ima $2n$ kartica ( $n\in\mathbb N$ ), po dvije kartice sa svakim od brojeva $1,2,\ldots,n$ . Kada ih je promiješao i složio jednu do druge u niz, primijetio je da se za svaki $k$ iz skupa $\{1,2,\ldots,n\}$ između dviju kartica s brojem $k$ nalazi točno $k$ drugih kartica. Dokaži da je broj $n^2+n$ djeljiv s $4$ .

Rješenje

Prvo rješenje.

Neka je $i_k$ pozicija prvog pojavljivanja kartice s brojem $k$ . Kartice s brojem $k$ tada se nalaze na pozicijama $i_k$ i $i_k+k+1$ .

Zbrojimo li sve pozicije, dobivamo

\sum_{k=1}^n(i_k+i_k+k+1)=1+2+\cdots+2n.

Stoga je

2\sum_{k=1}^n i_k+\frac{n(n+3)}2=\frac{2n(2n+1)}2,

odnosno

2\sum_{k=1}^n i_k=\frac{3n^2-n}{2}.

Slijedi da je broj $\frac{3n^2-n}{2}$ paran, tj. da je $3n^2-n$ djeljiv s $4$ . Tada je i

4n^2-(3n^2-n)=n^2+n

djeljiv s $4$ .

Drugo rješenje.

Kažimo da je par $(r,s)$ , $r,s\in\{1,2,\ldots,2n\}$ , poseban ako se na poziciji $r$ nalazi kartica s brojem $k$ , na poziciji $s$ kartica s brojem $l$ , a kartica na poziciji $s$ nalazi se između dviju kartica s brojem $k$ .

Za proizvoljne brojeve $k$ i $l$ iz skupa $\{1,\ldots,n\}$ promotrimo koliko ima posebnih parova $(r,s)$ takvih da se na pozicijama $r$ i $s$ nalaze kartice s brojevima $k$ i $l$ (u bilo kojem poretku). Neka se kartice s brojem $k$ nalaze na pozicijama $i_1$ i $i_2$ , a kartice s brojem $l$ na pozicijama $j_1$ i $j_2$ . Razlikujemo tri slučaja.

Ako se obje kartice s brojem $l$ nalaze između kartica s brojem $k$ , tj. $i_1<j_1<j_2<i_2$ , onda imamo 4 posebna para $(i_1,j_1)$ , $(i_1,j_2)$ , $(i_2,j_1)$ i $(i_2,j_2)$ . Analogno, ako se obje kartice s brojem $k$ nalaze između dvije kartice s brojem $l$ , opet imamo 4 posebna para.
Ako se točno jedna kartica s brojem $l$ nalazi između kartica s brojem $k$ , tj. bez smanjenja općenitosti $i_1<j_1<i_2<j_2$ , onda također imamo 4 posebna para $(i_1,j_1)$ , $(i_2,j_1)$ , $(j_1,i_2)$ i $(j_2,i_2)$ .
Ako se nijedna kartica s brojem $l$ ne nalazi između kartica s brojem $k$ , te nijedna kartica s brojem $k$ nije između kartica s brojem $l$ , onda nema posebnih parova.

Zaključujemo da je ukupan broj posebnih parova višekratnik broja $4$ . S druge strane, taj je broj jednak

2\sum_{k=1}^n k=n^2+n,

jer za svaki broj $k$ imamo dvije pozicije $r$ na kojima se nalazi kartica s tim brojem te $k$ pozicija između njih koje možemo odabrati za $s$ . Dakle, $4$ dijeli $n^2+n$ .