2. Zadatak

Prvo rješenje

Primijetimo da Vladimir redom ispisuje članove niza zadanog rekurzijom

$$a_1=1,\qquad a_2=2,\qquad a_k=a_{k-1}^2+a_{k-2}^2\quad\text{za }k\ge3.$$

Prvih nekoliko članova je $a_1=1$, $a_2=2$, $a_3=5$, $a_4=29$, $\ldots$ Promotrimo li ostatke koje ti brojevi daju pri dijeljenju s $3$, uočavamo da svi, osim broja $a_1$, daju ostatak $2$. Matematičkom indukcijom lako se pokaže da to vrijedi za sve članove $a_k$ za $k\ge2$:

$$a_k=a_{k-1}^2+a_{k-2}^2\equiv2^2+2^2=8\equiv2\pmod3.$$

Stoga nijedan član promatranog niza nije djeljiv s $3$.

Promotrimo sada ostatke pri dijeljenju sa $7$:

$$\begin{aligned} a_1&\equiv1\pmod7, & a_2&\equiv2\pmod7,\\ a_3&\equiv1^2+2^2\equiv5\pmod7, & a_4&\equiv2^2+5^2=29\equiv1\pmod7,\\ a_5&\equiv5^2+1^2=26\equiv5\pmod7, & a_6&\equiv1^2+5^2=26\equiv5\pmod7,\\ a_7&\equiv5^2+5^2=50\equiv1\pmod7, & a_8&\equiv5^2+1^2=26\equiv5\pmod7. \end{aligned}$$

Uočavamo da se nakon prva dva člana ponavljaju ostaci $1$ i $5$, točnije

$$a_{3l}\equiv5,\qquad a_{3l+1}\equiv1,\qquad a_{3l+2}\equiv5\pmod7,$$

za $l\in\mathbb N$, što nije teško provjeriti matematičkom indukcijom. Stoga nijedan član promatranog niza nije djeljiv sa $7$.

Drugo rješenje

Na ploči su na početku brojevi $1$ i $2$ koji nisu djeljivi s $3$. Da bismo u nekom trenutku dobili broj djeljiv s $3$, trebala bi suma kvadrata dva broja koja nisu djeljiva s $3$ biti djeljiva s $3$, a to je moguće samo ako jedan od njih pri dijeljenju s $3$ daje ostatak $1$, a drugi ostatak $2$. Uočimo da kvadrat prirodnog broja koji nije djeljiv s $3$ pri dijeljenju s $3$ daje ostatak $1$ (kvadrat prirodnog broja ne može dati ostatak $2$ pri dijeljenju s $3$). Stoga suma kvadrata dvaju prirodnih brojeva koji nisu djeljivi s $3$ daje pri dijeljenju s $3$ ostatak $2$, dakle nije djeljiva s $3$.

Slično možemo zaključivati i pri promatranju djeljivosti sa $7$. Kako je

$$0^2=0,\quad1^2=1,\quad2^2=4,\quad3^2=9=7+2,\quad4^2=16=2\cdot7+2,\quad5^2=25=3\cdot7+4,\quad6^2=36=5\cdot7+1,$$

jedini mogući ostaci pri dijeljenju potpunog kvadrata brojem $7$ su $0$, $1$, $2$ i $4$. Dakle, suma dva kvadrata je djeljiva sa $7$ samo ako su oba djeljiva sa $7$. Kako početni brojevi nisu djeljivi sa $7$, nikad nećemo dobiti broj djeljiv sa $7$.

Napomena. Tvrdnja vrijedi i ako se zbrajaju kvadrati bilo kojih dvaju brojeva na ploči. Dokaz je isti, pa i takvo rješenje treba priznati.