A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Mutatunk egy olyan algoritmust, amely összehasonlítással biztosan eldönti a kérdést, és mutatunk egy olyan kitöltést is, amikor összehasonlítás biztosan nem elég. Hasonlítsuk össze az számot a tábázat jobb felső sarkában álló elemmel. Ha ez az elem éppen , akkor a kérdés máris eldőlt. Ha az elem nagyobb, mint , akkor a monotonitás miatt az első sorban mindegyik elem nagyobb, mint ; ha a jobb felső sarokban álló elem kisebb -nál, akkor pedig az utolsó oszlop mindegyik eleme kisebb -nál. Hagyjuk el a táblázatból az előbbi esetben az első sort, az utóbbi esetben az utolsó oszlopot (amelyben biztosan nem szerepel), és vizsgáljuk a maradék táblázatot. Ezt az eljárast ismételgetve, azaz -t mindig a megmaradt táblázat első sorának utolsó elemével össehasonlítva, legfeljebb lépés után vagy megtaláljuk -t a táblázatban, vagy pedig elhagyjuk az összes oszlopot vagy az összes sort. Ez a módszer tehát legfeljebb lépésben biztosan célra vezet. Most töltsük ki a táblázatot a következőképpen: a bal alsó és a jobb felső sarkot összekötő átlóba írjunk mindenhova -at, a közvetlenül ezek alatt levő mezőkbe -et. Az átló fölötti mezőkbe írjunk mindenhova -et, a megmaradt mezőkbe pedig -t. Végül válasszuk -t -nek.
Tegyük fel, hogy valaki összehasonlította az a=2 számot a táblázat 2n-2 elemével. Az összesen 2n-1 darab 3-as és 1-es között van legalább egy, amelyet nem hasonlított össze a 2-vel. Ha ezt az elemet 2-nek választottuk volna, akkor az összehasonlítások eredménye mind ugyanaz lett volna. A 2n-2 összehasonlításból tehát nem derülhet ki egyértelműen, hogy a 2 nem szerepel a táblázatban.
|