Oplossing

Hieronder de opgave. De inzendingstermijn is verstreken, en elders staat een bespreking van de ontvangen oplossingen.

Het afbreken van trappen

Het spel "trapafbreken" gaat als volgt.

Een spelsituatie is een dalende trap, bijvoorbeeld

XX
XXXX
XXXXXXX
XXXXXXXXXXX
0XXXXXXXXXXXXXXX

Een zet bestaat uit het aanwijzen van een steen (kruisje, vierkantje, hokje) in de trap, en die steen verwijderen, samen met alle stenen die daar rechts of boven of rechtsboven van liggen.

Dus, als bijvoorbeeld de steen gemerkt + wordt aangewezen:

XX
XXXX
XXXXXXX
XXX+XXXXXXX
0XXXXXXXXXXXXXXX

dan wordt de nieuwe situatie

XX
XXX
XXX
XXX
0XXXXXXXXXXXXXXX

een nieuwe dalende trap.

Twee spelers doen beurtelings een zet. Wie de laatste steen (de linker benedenhoek) pakt heeft verloren.

Een generalisatie

Meer algemeen, bekijk een partieel geordende verzameling P met kleinste element 0. Een zet bestaat uit het weghalen van een element x samen met alles wat erboven ligt. Wie 0 pakt verliest.

De prijsvraag

Bestudeer het spel "trapafbreken" of (een speciaal geval van) de gegeneraliseerde versie. Welke standen zijn gewonnen voor de speler aan zet? Welke zijn verloren? Is er een strategie? Voor de beste inzending(en) is een fantastisch geldbedrag beschikbaar.

Ideeen

Trappen van de vorm

X
XX
XXX
XXXX
0XXXX

hebben een eenvoudige strategie. Ja, zelfs twee heel verschillende eenvoudige strategieen.

Wie wint er bij het 4x4 vierkant? De 4x10 rechthoek? De 4 bij oneindig rechthoek (4xN rechthoek, met N de verzameling van natuurlijke getallen)?

Als partieel geordende verzameling P kun je een eindige verzameling V samen met alle deelverzamelingen nemen, met de inclusie als ordening. Het spel wordt dan: pak beurtelings een deelverzameling van V die geen eerder gepakte deelverzameling bevat. Wie de lege verzameling pakt verliest. Als V niet leeg is dan wint de beginner. Waarom? Maar wat moet de beginner dan doen om te winnen? Dat weet niemand.

In plaats van naar alle deelverzamelingen te kijken is er het spel op alle deelverzamelingen met hooguit h elementen. Hoe zit het met het spel op alle deelverzamelingen ter grootte hooguit 3 van een verzameling met 10 elementen?

We kunnen van V ook alle punten en sommige paren nemen, en vinden dan een graaf. Het spel wordt: pak om de beurt iets weg, hetzij een kant, hetzij een punt samen met alle kanten op dat punt. Wie de laatste zet doet wint. Is er voor dit spel een theorie op te stellen?

Enz.

Applet

Een applet dat trapafbreken speelt.