Školjka

Neka je $n$ prirodan broj. Nizić i Nikolac igraju sljedeću igru: Najprije Nizić na stolu poreda $2n$ čaša okrenutih otvorom prema dolje u niz. Potom ispod jedne čaše napravi rupu, a ispod neke druge postavi lopticu. Tada Nikolac zadaje konačan niz naredbi Niziću, pri čemu se svaka naredba sastoji od zamjene nekih dviju susjednih čaša u nizu. Nikolčev je cilj da loptica tijekom igre upadne u rupu. Uz pretpostavku da Nikolac nema nikakvih informacija o poziciji rupe ni o poziciji loptice niti u jednom trenutku, koliko najmanje naredbi mora zadati kako bi sa sigurnošću ostvario svoj cilj? \begin{flushright}\emph{(Adrian Beker)}\end{flushright}