Adott  $n$  lefordított pohár sorban az asztalon, ezek alatt golyók lehetnek. Meg akarjuk állapítani, hogy van-e két szomszédos pohár alatt golyó. Ehhez egyesével fordíthatunk fel poharakat. Ezt a feladatot nehéznek nevezzük, ha bármilyen jó stratégiát is választunk, lehetséges, hogy minden poharat fel kell fordítanunk, hogy megtudjuk a választ. Az  $n=1,2,\dots 2013$  értékek közül hánynál nehéz a feladat?

Végeredmény: 1342

Az  $n\equiv 1\pmod 3$  számokra nem nehéz a feladat. Valóban,  $n=1$  -re nem nehéz, nem is kell kérdeznünk, és innen teljes indukcióval megyünk. Ha  $n=3k+1$  (  $k>0$  ), akkor fordítsuk fel a balról harmadik poharat. Ha nincs alatta golyó, akkor tőle jobbra  $(3(k-1)+1$  pohár maradt, amely nem nehéz feladat, így az egész sem az. Ha van alatta golyó, akkor a bal oldali szomszédját nézzük és ha ott van golyó, akkor máris találtunk kettőt, ha nincs, akkor a bal szélső poharat már nem is kell néznünk, nem nehéz a feladat. Igazoljuk, hogy  $n\not\equiv 1\pmod 3$  esetén nehéz a feladat. Ezt teljes indukcióval igazoljuk.  $n=2$  -re és  $n=3$  -ra tényleg nehéz a feladat. Általában, ha először olyan poharat nézünk meg, amelytől balra és jobbra is külön-külön önmagában nehéz a feladat, akkor ha az először megnézett pohár alatt nincs golyó, akkor nem tudunk ügyesek lenni, mindent meg kell nézni. Két eset marad (  $ 1$  jelöli az első körben megnézett poharat: a)  $ 3a, 1, 3b+1$  ;\qquad b)  $ 3c+1, 1, 3d+1$  . Ha most az elsőre megnézett pohár alatt van golyó és a mellette levőkön (amelyeket valamikor úgyis meg kell nézni) nincs, akkor nehéz csupa nehéz feladathoz jutunk, tehát az eredeti is nehéz.  

2. Megoldás

Legyen először  $n\equiv 1\pmod{3}$  . Fedjük fel minden  $i$  -adik poharat, ahol  $i \not\equiv 1 \pmod 3$  . Ha két szomszédos felfedett pohár alatt volt golyó, akkor nyertünk. Ha nem, akkor rajzoljuk föléjük legfeljebb egy nyilat: az üres pohár felől a golyó felé, ha van golyó, ill. semmit nem rajzolunk, ha nincs. Pl. ha a golyók száma a poharak alatt  $*~0~1~*~0~0~*~1~0~*$  (ahol  $*$  a felfedetlen poharakat jelöli), akkor az ábra  $*\rightarrow*~~~~*\leftarrow*$  . Csak azokat a poharakat kell felfordítanunk, amikre nyíl mutat; mivel  $i+1$  db.  $*$  van és legfeljebb  $i$  nyíl, nem kell mindet felfordítani.  $n\not\equiv 1\pmod 3$  esetén viszont nehéz a feladat. A ,,gonosz manó'' nyerő stratégiáját írjuk le. Az egyszerűség kedvéért gondoljunk a sor két szélére 1-1 már felfordított poharat, amik alatt nem volt golyó. Akármelyik poharat fordítjuk fel, a gonosz manó a következő módon dönti el, hogy legyen-e alatta golyó. Azt az állapotot akarja fenntartani, hogy minden két felfedett pohár közötti egybefüggő felfedetlen (  $j$  hosszú) sorozatra (ahol  $j$  lehet  $ 0$  is):

1. Ha mindkét szélén üres felfedett pohár van (  $ 0**\dots*0$  ):  $j\not\equiv 1\pmod 3$  ,
2. Ha az egyik vége üres, a másik vége teli (  $ 1**\dots*0$  ):  $j\not\equiv 2\pmod 3$  ,
3. Ha a sor mindkét végén van golyó (  $ 1**\dots*1$  ):  $j\not\equiv 0\pmod 3$  . \

Indukcióval és könnyű esetszétválasztással látható, hogy akármelyik poharat fordítja is fel a játékos, a gonosz manó elérheti, hogy ez az állapot fennmaradjon. Márpedig amíg az állapot fennáll, és van felfordítatlan pohár, addig nem lehet biztosra megmondani a választ, tehát a feladat nehéz.

(Természetesen ha a manó játék közben nem tudja megváltoztatni a golyókat, akkor kidolgozható olyan véletlen stratégia, hogy nagyon nagy valószínűséggel ne kelljen mindent felfordítani -- de ez a valószínűség nem lehet 1.)