4. Zadatak

Tvrdnju zadatka dokazat ćemo matematičkom indukcijom po $n$. Tvrdnja očito vrijedi za $n=1$.

Pretpostavimo da za neki $n$ vrijedi da svaki niz od najviše $n$ realnih brojeva zadovoljava uvjete zadatka. Dokažimo da tvrdnja vrijedi i za $n+1$.

Neka su $x_1,\ldots,x_{n+1}$ ti brojevi u nizu. Neka je $x_i$ prvi označeni broj, te neka je $x_j$ broj u nizu s najmanjim indeksom većim od ili jednakim $i$ takav da je suma

$$x_i+x_{i+1}+\cdots+x_{j-1}+x_j$$

pozitivna.

Dokažimo da su svi brojevi $x_i,x_{i+1},\ldots,x_j$ označeni. Pretpostavimo suprotno, tj. da postoji neki broj $x_k$, $i\le k\le j$, koji nije označen. Očito $k\ne i$ budući da smo $x_i$ odabrali kao prvi označeni broj.

Ako broj $x_k$ nije označen, slijedi da suma svakog niza uzastopnih članova počevši s tim brojem nije pozitivna. Posebno, vrijedi

$$x_k+x_{k+1}+\cdots+x_{j-1}+x_j\le0,$$

pa je zato suma

$$x_i+x_{i+1}+\cdots+x_{k-1}=(x_i+x_{i+1}+\cdots+x_{j-1}+x_j)-(x_k+x_{k+1}+\cdots+x_{j-1}+x_j)$$

pozitivna. Tu dobivamo kontradikciju s odabirom broja $x_j$.

Dakle, u nizu brojeva $x_1,x_2,\ldots,x_j$ brojevi $x_i,x_{i+1},\ldots,x_j$ su jedini označeni te je njihova suma pozitivna. Ako među svih $n+1$ brojeva u nizu više nema označenih brojeva, dokaz je završen.

Ako postoji još označenih brojeva, tada se u nizu $x_{j+1},x_{j+2},\ldots,x_{n+1}$ nalazi najviše $n$ realnih brojeva pa po pretpostavci indukcije vrijedi da je suma označenih brojeva u tom nizu pozitivna.

Zato je i suma svih označenih brojeva u nizu $x_1,x_2,\ldots,x_{n+1}$ pozitivna, čime je dokazan korak indukcije, a time i tvrdnja zadatka.