5. Zadatak

Neka su $a,p,q,b$ četiri uzastopna broja u cik-cak rasporedu. Pretpostavimo da je $p>q$. Tada je $a<p$ i $q<b$. Par $(p,q)$ nije dobar ako i samo ako je $a>b$, odnosno ako i samo ako je $p$ najveći, a $q$ najmanji od brojeva $a,p,q,b$.

Ako par $(p,q)$ nije dobar, par $(a,p)$ je dobar jer $a$ nije manji od $q$, a par $(q,b)$ je dobar jer $b$ nije veći od $p$. Dakle, od svaka dva para koji imaju zajednički broj barem je jedan dobar. Zato je broj dobrih parova barem $150$.

Pretpostavimo da je raspored $a_1,a_2,\ldots,a_{300}$ i da ima točno $150$ dobrih parova. Bez smanjenja općenitosti neka je $a_1>a_2$ i neka par $(a_1,a_2)$ nije dobar. Tada su parovi $(a_{2k},a_{2k+1})$ dobri, a parovi $(a_{2k-1},a_{2k})$ nisu dobri za $k=1,\ldots,149$; također par $(a_{299},a_{300})$ nije dobar.

Prema prethodnom kriteriju dobivamo

$$a_1>a_3>a_5>\cdots>a_{299}>a_1,$$

što je proturječje. Zato je broj dobrih parova barem $151$.

Ta se granica može postići rasporedom

$$3,2,5,4,7,6,\ldots,299,298,300,1.$$

U tom rasporedu par $(300,1)$ i svi parovi $(2k,2k+3)$ za $k=1,\ldots,148$ nisu dobri, a svi ostali parovi jesu dobri. Ukupno je, dakle, $151$ dobrih parova.