Školjka

Neka $b_i$ i $c_i$ redom označavaju bijele i crne kuglice označene brojem $i$ gdje je $ i \in \{1 , 2, \ldots ,n\}$ Posmatrajmo za svaki $i$ kružni luk $L_i$ (skup), gledajući u smjeru kazaljke na satu, koji počinje "neposredno poslije $b_i$" i završava "neposredno prije $c_i$". \textit{Ako osjetite da nemate kontrolu nad elementima zadatka, pored raznih načina sistematizacije (kao što je u ovom slučaju skup $L_k$), dosta je korisno prizvati upomoć princip ekstrema. To jest posmatrati određeni skup koji je maksimalan ili minimalan po određenom kriteriju, jer će takav skup vrlo često davati dodatna ograničenja koja se mogu pokazati korisnim. U ovom slučaju iz odabira minimalanog skupa $L_k$ će proizaći dva niza , jedan bijeli , jedan crni čiji su skupovi indeksa disjunktni. Ajmo vidit zašto je takvo nešto korisno...} Pretpostavimo da je najmanji od kružnih lukova $L_k$ (dakle onaj koji sadrži najmanje elemenata). Sve kuglice u skupu $L_k$ moraju biti iste boje, u protivnom bi i $b_{k+1}$, i $c_{k+1}$ bili elementi skupa $L_k$ odnosno $L_{k+1}$ bi bio sadržan u skupu $L_k$ što bi se se suprotstavljalo minimalnom odabiru skupa $L_k$. Neka je boja elemenata u odabranom luku bez smanjenja općenitosti bijela. Ukoliko sada uzmemo kružni luk duljine $n$ koji počinje neposredno poslije kuglice $b_k$, on će sadržati bijele kuglice poredane po rastućim oznakama počevši od $b_{k+1}$ dok će crne kuglice sadržati po padajućim oznakama počevši od $c_k$. Dakle ukoliko ima $m$ bijelih kuglica u disku, to će biti kuglice $b_{k+1},\ldots,b_{k+m}$ dok će crnih biti $n-m$ a to su $c_{k}, c_{k-1}, \ldots ,c_{k-n+m+1}$ gdje sve indekse gledamo modulo $2n$. \textit{Može izgledati smješno, kako se zadatak samo "raspao". Ako malo razmislite činjenica da je najmanji $L_k$ isključivo u jednoj boji (npr. bijeloj) ne dozvoljava da se $c_{k+1}$ pojavi poslije $b_k$, tj. ne dozvoljava ponavljanje indeksa $k+1$, $b_{k+1}$ i $c_{k+1}$ u ovom slučaju. Bez posmatranja ekstrema ne bismo mogli dobiti dva disjunkta niza indeksa koji nam trebaju da bismo upotpunili skup $\{1,2,...,n\}$. }