5. Zadatak

Prvo rješenje.

Za prirodan broj $m$ kažemo da je dobar ako postoje prirodni brojevi $a$, $b$ i $c$ takvi da je $m=a^2+b^3+c^6$. U suprotnom kažemo da je $m$ loš. Zadatak je dokazati da postoji beskonačno mnogo loših brojeva.

Za proizvoljan prirodan $N\geq3$ promotrimo skup $S=\{1,2,\ldots,N^6\}$.

Promotrimo bilo koji dobar broj $m$ iz skupa $S$, te neka su $a,b,c\in\mathbb N$ takvi da je $m=a^2+b^3+c^6$. Za te brojeve $a,b,c$ tada vrijedi:

$$N^6\geq m=a^2+b^3+c^6\geq a^2\implies a\leq N^3,$$ $$N^6\geq m=a^2+b^3+c^6\geq b^3\implies b\leq N^2,$$ $$N^6\geq m=a^2+b^3+c^6\geq c^6\implies c\leq N.$$

Označimo s $K$ skup uređenih trojki prirodnih brojeva $(a,b,c)$ takvih da je $1\leq a\leq N^3$, $1\leq b\leq N^2$, $1\leq c\leq N$. Skup $K$ ima $N^3\cdot N^2\cdot N=N^6$ elemenata. Primijetimo da za svaki dobar $m\in S$ postoji $(a,b,c)\in K$ takav da je $m=a^2+b^3+c^6$.

Promotrimo brojeve oblika $n^6+2$, gdje je $n\in\{2,\ldots,N-1\}$. Svi ti brojevi se nalaze u $S$ jer je $n^6+2\leq(N-1)^6+2<N^6$, i takvih brojeva ima $(N-2)$. Također, svi ti brojevi su dobri, i prikazivi su na (barem) tri načina:

$$n^6+2=(n^3)^2+1^3+1^6=1^2+(n^2)^3+1^6=1^2+1^3+n^6,$$

odnosno određeni su s (barem) tri međusobno različite trojke iz $K$:

$$(n^3,1,1),\quad(1,n^2,1),\quad(1,1,n),\qquad n\in\{2,\ldots,N-1\}.$$

Kako su dobri elementi $S$ prikazivi s najviše $N^6$ mogućih trojki prirodnih brojeva $(a,b,c)\in K$, a $(N-2)$ brojeva među njima prikazivo je na barem tri načina, zaključujemo da je najviše $N^6-2(N-2)$ elemenata skupa $S$ dobro. Budući da skup $S$ ima $N^6$ elemenata, zaključujemo da postoji barem $2(N-2)$ loših elemenata.

Ovime smo za neki $N\geq3$ dokazali da postoji barem $2(N-2)$ loših brojeva u skupu $\{1,2,\ldots,N^6\}$. Kako $N$ može biti proizvoljno velik, zaključujemo da je beskonačno mnogo loših brojeva.

Drugo rješenje.

Kao u prošlom rješenju, definirajmo dobre i loše prirodne brojeve, te za proizvoljan $N\geq2$ definirajmo skup $S=\{1,2,\ldots,N^6\}$.

Za neki dobar $m$ i prirodne brojeve $a,b,c$ takve da je $m=a^2+b^3+c^6$ mogu se dobiti i bolje ocjene:

$$N^6\geq m=a^2+b^3+c^6\geq a^2+1+1>a^2\implies a<N^3\implies a\leq N^3-1,$$ $$N^6\geq m=a^2+b^3+c^6\geq1+b^3+1>b^3\implies b<N^2\implies b\leq N^2-1,$$ $$N^6\geq m=a^2+b^3+c^6\geq1+1+c^6>c^6\implies c<N\implies c\leq N-1.$$

Označimo s $K$ skup uređenih trojki prirodnih brojeva $(a,b,c)$ takvih da je $1\leq a\leq N^3-1$, $1\leq b\leq N^2-1$, $1\leq c\leq N-1$. Skup $K$ ima

$$(N^3-1)(N^2-1)(N-1)=N^6-N^5-N^4+N^2+N-1$$

elemenata. Primijetimo da za svaki dobar $m\in S$ postoji $(a,b,c)\in K$ takav da je $m=a^2+b^3+c^6$. Kako skup $S$ ima $N^6$ elemenata, zaključujemo da je barem

$$N^5+N^4-N^2-N+1=(N^3-1)(N+1)N+1\geq1\cdot N(N+1)+1=N^2+N+1$$

elemenata skupa $S$ loše.

Ovime smo za neki $N\geq2$ dokazali da postoji barem $N^2+N+1$ loših brojeva u skupu $\{1,2,\ldots,N^6\}$. Kako $N$ može biti proizvoljno velik, zaključujemo da je beskonačno mnogo loših brojeva.