5. Zadatak

Prirodni broj $a_1a_2\ldots a_m$ (uz $a_1\neq0$ ) je koncizan ako je broj $a_ia_{i+1}\ldots a_{i+k-1}$ djeljiv s $k$ za sve prirodne brojeve $i$ , $k$ takve da je $1\leq k\leq m$ i $1\leq i\leq m-k+1$ .

Na primjer, broj $102$ je koncizan jer su brojevi $1$ , $0$ i $2$ djeljivi s $1$ , brojevi $10$ i $2$ ( $=02$ ) djeljivi s $2$ te broj $102$ djeljiv s $3$ .

Dokaži da postoji najveći koncizni prirodni broj i odredi ga.

Rješenje

Tvrdimo da je najveći koncizan broj $9660000$ . Direktnom provjerom vidimo da je koncizan: brojevi dobiveni nizom od $2$ , $3$ , $4$ , $5$ , $6$ i $7$ uzastopnih znamenaka zaista jesu djeljiv brojem svojih znamenaka.

Pretpostavimo da postoji veći, neka je to $n$ i neka ima $d\geq7$ znamenaka.

Kako je svaki niz od dvije znamenke nužno paran broj, svaka znamenka osim eventualno prve je nužno parna.

Kako je svaki niz od $5$ znamenaka djeljiv s $5$ , to znači da je svaka od zadnjih $d-4$ znamenaka djeljiva s $5$ . Zajedno s parnosti, sve te znamenke su jednake nuli.

Kako je $d\geq7$ , to posebno znači da su zadnje tri znamenke jednake nuli.

Promotrimo djeljivost s $3$ . Zaključili smo da su zadnje tri znamenke jednake nuli. Promatrajući svake tri uzastopne znamenke redom, počevši sa zadnje tri, znajući da im zbroj treba biti djeljiv s $3$ , redom zaključujemo da sve znamenke broja $n$ djeljive s tri.

Zajedno s parnosti, zaključujemo da su sve znamenke osim prve jednake $0$ ili $6$ .

Promotrimo sada djeljivost s $4$ . Niz od prve četiri znamenke čini četveroznamenkast broj djeljiv s $4$ . Iz gornjih zaključaka znamo da su tom broju zadnje dvije znamenke $0$ ili $6$ . Jedini dvoznamenkasti brojevi koje te znamenke tvore, a djeljivi su sa $4$ , su $60$ i $00$ . Zato je četvrta znamenka broja $n$ nužno jednaka nuli.

Sveukupno, zaključujemo: svakom konciznom broju s $d\geq7$ znamenaka sve znamenke osim prve tri su jednake nuli. Druga i treća znamenka mogu biti $0$ ili $6$ , a prva može biti $3$ , $6$ ili $9$ .

Promotrimo djeljivost sa $7$ . Broj stvoren od prvih $7$ znamenaka će biti djeljiv sa $7$ ako mu je broj stvoren od prve tri znamenke djeljiv s $7$ (jer su sve ostale znamenke jednake nuli).

Provjerom svih mogućnosti ( $300$ , $600$ , $900$ , $306$ , $606$ , $906$ , $360$ , $660$ , $960$ , $366$ , $666$ , $966$ ), uočavamo da je samo $966$ djeljiv brojem $7$ .

Dakle, svi koncizni brojevi s $d\geq7$ znamenaka su brojevi oblika $96600\ldots0$ . U slučaju $d=7$ broj jest koncizan, u što smo se uvjerili na početku rješenja. U slučaju $d\geq8$ i broj stvoren od $7$ znamenaka broja $n$ počevši s drugom znamenkom mora biti djeljiv sa $7$ , no to nije moguće jer $66$ nije djeljiv sa $7$ .

Dakle, $9660000$ je uistinu najveći koncizan prirodan broj.