5. Zadatak

Prvo rješenje.

Reći ćemo da je prirodan broj prikaziv ako se može zapisati kao zbroj nekih, ne nužno različitih, elemenata skupa $\{135,136,137,\ldots,144\}$. Označimo skup sa $S$ skup dozvoljenih pribrojnika $\{135,136,137,\ldots,144\}$ sa $S$ i definirajmo skupove

$$S_k=\{135k,135k+1,\ldots,144k\}.$$

Dokažimo da je broj $n$ prikaziv kao zbroj $k$ pribrojnika iz $S$ ako i samo ako je $n\in S_k$.

Ako se broj $n$ može prikazati kao suma $k$ elemenata skupa $S$, tada je očito broj $n$ u skupu $S_k$ (jer je $k$ pribrojnika iz njegove sume između $135$ i $144$).

Dokažimo sada obrat: svaki broj iz $S_k$ prikaziv kao zbroj $k$ pribrojnika iz $S$. Pretpostavimo suprotno, postoje neki brojevi iz $S_k$ koji nisu prikazivi i neka je $n_0$ najmanji među njima. Sigurno $n_0\neq135k$, budući da se taj broj može prikazati kao zbroj $k$ ponavljanja pribrojnika $135$. Zato je $n_0>135k$, pa je broj $n_0-1$ prikaziv. Broj $n_0-1$ je manji od $144k$, pa je jedan pribrojnik u njegovom zapisu manji od $144$. Uvećavanjem tog pribrojnika za $1$ (dok sve ostale pribrojnike ostavimo iste) dobivamo zbroj $k$ elemenata iz $S$ koji iznosi $n_0$, što je kontradikcija s neprikazivosti broja $n_0$. Dakle, svi brojevi između $135k$ i $144k$ su prikazivi.

Nađimo sada najveći broj koji nije prikaziv. Ako neki prirodan broj $m$ nije prikaziv, tada se ne nalazi ni u jednom skupu $S_k$. Posebno, nalazi se između dva uzastopna skupa $S_k$ i $S_{k+1}$, tj. $144k<m<135(k+1)$, a to je moguće ako i samo ako je

$$144k+2\leq135(k+1),$$

odakle je $k\leq14$. Dakle, za $k\geq15$ nema brojeva koji se nalaze između $S_k$ i $S_{k+1}$, pa su najveći neprikazivi brojevi između $S_{14}$ i $S_{15}$.

Najveći broj između $S_{14}=\{1890,\ldots,2016\}$ i $S_{15}=\{2025,\ldots,2160\}$ je $2024$, pa je to ujedno i najveći neprikaziv broj.

Drugo rješenje.

Koristeći oznake iz prvog rješenja, dokažimo drugačije da je svaki broj iz $S_k$ prikaziv.

Broj $n$ je prikaziv kao suma $k$ pribrojnika iz $S$ ako i samo ako je $\widetilde n:=n-135k$ prikaziv kao suma $k$ pribrojnika iz skupa $\{0,1,\ldots,9\}$ (svakom od $k$ pribrojnika možemo pribrojiti/oduzeti broj $135$). Zato je potrebno dokazati da se svi brojevi $\widetilde n\in\{0,1,\ldots,9k\}$ mogu prikazati kao suma $k$ pribrojnika iz skupa $\{0,1,\ldots,9\}$.

Ako je $\widetilde n=9k$, broj je prikaziv kao zbroj $k$ devetki. Inače broj $\widetilde n$ cjelobrojno podijelimo s $9$: dobivamo $\widetilde n=9p+r$ za $p\in[0,\ldots,k-1]$ i $r\in[0,\ldots,8]$. Sada vidimo da je $\widetilde n$ prikaziv kao suma $p$ devetki, jednog broja $r$, te $k-p-1$ nula, čime je tvrdnja dokazana.

Ostatak dokaza provodi se kao u prošlom rješenju.