5. Zadatak

Nikola je zamislio deveteroznamenkasti broj $\overline{a_1a_2a_3\ldots a_9}$ u čijem se dekadskom prikazu svaka od znamenaka od $1$ do $9$ pojavljuje točno jednom. Zatim je izračunao $6$ zbrojeva

\overline{a_1a_2a_3}+\overline{a_2a_3a_4},\quad \overline{a_2a_3a_4}+\overline{a_3a_4a_5},\quad \overline{a_3a_4a_5}+\overline{a_4a_5a_6},

\overline{a_4a_5a_6}+\overline{a_5a_6a_7},\quad \overline{a_5a_6a_7}+\overline{a_6a_7a_8},\quad \overline{a_6a_7a_8}+\overline{a_7a_8a_9}

i napisao na papir najveći od njih. Koji je najmanji broj koji je mogao zapisati na papir?

Najmanji takav broj je $882$ , i postiže se za $716253489$ .

Prvo dokažimo da broj koji se nalazi na papiru mora biti barem $800$ . U suprotnom, svi zbrojevi stotica troznamenkastih brojeva $a_1+a_2,\ldots,a_6+a_7$ manji su ili jednaki $7$ . Dakle, vrijedi

a_1+2a_2+\cdots+2a_6+a_7\leq6\cdot7=42.

S druge strane,

\begin{aligned} a_1+2a_2+\cdots+2a_6+a_7 &=2(a_2+a_3+\cdots+a_6)+a_1+a_7\\ &\geq2(1+2+3+4+5)+6+7=43, \end{aligned}

čime dobivamo kontradikciju.

Nađimo sve deveteroznamenkaste brojeve $n=\overline{a_1a_2a_3\ldots a_9}$ za koje će rezultat na papiru biti manji od $900$ .

Ako je neka od znamenki $a_1,\ldots,a_7$ jednaka $8$ ili $9$ , onda će barem jedan od zbrojeva $a_1+a_2,\ldots,a_6+a_7$ biti veći ili jednak $9$ , pa broj na papiru neće biti manji od $900$ . Dakle, znamenke $8$ i $9$ moraju se naći na nekom od zadnja dva mjesta, dok se na prvih sedam mjesta nalaze znamenke $1,2,\ldots,7$ .

Promotrimo zbroj $\overline{a_6a_7a_8}+\overline{a_7a_8a_9}$ . Za njega vrijedi

\begin{aligned} 100(a_6+a_7)+10a_7+11a_8+a_9 &\geq100(a_6+a_7)+10+11\cdot8+9\\ &=100(a_6+a_7)+107. \end{aligned}

Zato kako bi broj na papiru bio manji od $900$ , nužno je $a_6+a_7\leq7$ .

Pogledajmo gdje se u broju $n$ nalazi znamenka $7$ . Jedina znamenka koja s njom daje sumu manju od $9$ je znamenka $1$ . Zato se znamenka $7$ ne može nalaziti na mjestima $a_2,a_3,a_4,a_5,a_6$ . Također, ne smije biti ni $a_7=7$ jer tada ne bismo imali $a_6+a_7\leq7$ . Dakle, $a_1=7$ .

Kako bi zadovoljili uvjet $a_1+a_2\leq8$ , nužno je $a_2=1$ .

Pogledajmo gdje se u broju $n$ nalazi znamenka $6$ . Uz znamenku $1$ , jedina znamenka koja s njom daje sumu manju od $9$ je znamenka $2$ . Zato se znamenka $6$ ne može nalaziti na mjestima $a_4,a_5,a_6$ (jer bi barem jedan od njenih susjeda bio prevelik). Također, ne smije biti ni $a_7=6$ jer tada ne bismo imali $a_6+a_7\leq7$ . Dakle, $a_3=6$ .

Analogno zaključujemo da je $a_4=2$ , a zatim istim načinom redom $a_5=5$ , $a_6=3$ i $a_7=4$ .

Zaključujemo da samo dva deveteroznamenkasta broja mogu rezultirati konačnim brojem na papiru koji bi bio manji od $900$ : to su $716253489$ i $716253498$ . Direktnom provjerom uvjeravamo se da je prvom od njih broj na papiru jednak $882$ , a drugom $883$ , pa dolazimo do zaključka s početka rješenja.