Državno natjecanje 2018., 1. razred SŠ, A varijanta, 5. Zadatak
Za prirodne brojeve raspoređene ukrug kažemo da su u cik-cak rasporedu ako je svaki broj ili veći ili manji od oba svoja susjeda. Za par susjednih brojeva kažemo da je dobar ako su nakon njegovog uklanjanja preostali brojevi također u cik-cak rasporedu. Brojevi od do raspoređeni su u cik-cak raspored. Koliki je najmanji mogući broj dobrih parova susjednih brojeva?
Rješenje
Neka su četiri uzastopna broja u cik-cak rasporedu. Pretpostavimo da je . Tada je i . Par nije dobar ako i samo ako je . Zato zaključujemo da par nije dobar ako i samo je najveći, a najmanji broj u četvorci .
Ako par nije dobar, onda je par dobar jer nije manji od . Također, par je dobar jer nije veći od .
Time smo pokazali da za svaka dva para koji imaju zajednički element vrijedi da je barem jedan od ta dva para dobar. Dakle, dobrih parova ima barem .
Pretpostavimo da postoji cik-cak raspored u kojem je točno dobrih parova.
Bez smanjenja općenitosti, možemo pretpostaviti da je i da par nije dobar. Tada su parovi dobri, a parovi nisu dobri za sve . Također, par nije dobar par.
Budući da par nije dobar prema navedenom kriteriju zaključujemo da je . Također, budući da nije dobar par, zaključujemo da je . Analogno zaključujemo
Time smo dobili kontradikciju, pa nije moguće da cik-cak raspored ima točno dobrih parova. Dakle, dobrih parova ima barem .
Primjer rasporeda s točno dobrih parova je
U tom rasporedu par i svi parovi za nisu dobri, a svi ostali parovi su dobri.