Kombinatorika · 2026. szeptember
A pártatlan kövek értéke
Egy halom kő akkor érdekes, ha a szabály mindkét félnek ugyanazt engedi. Innen a neve, és innen a szám, amellyel egy egész állás helyettesíthető.
A szabály rövid. Van néhány oszlop. A soron következő játékos egy oszlopot választ, és elvesz belőle legalább egy követ, akár az összeset. Aki nem tud lépni, a játszmát elveszíti. Nincs rejtett lap, nincs jelölő, a teljes az asztalon van. Az alacsony: nem egy ritka kör dönt, hanem az, hogy ki hagyja a másikat nulla értékű állásban.
Egyetlen oszlop értéke maga a kövek száma. Üres oszlopból nincs lépés, az értéke 0. Egy kőből csak a nullába lehet lépni. Két kőből a nullába vagy az egybe. A azt a legkisebb nemnegatív egészet keresi, amely az elérhető értékek között nincs ott. Így az n köves oszlop éppen n.
Ha az oszlopok függetlenek — egy lépés mindig csak egyet érint —, az egész állás értéke a részértékek kizáró vagy kapcsolata. A 3, 4 és 7 köves asztal: 3 xor 4 = 7, és 7 xor 7 = 0. A nulla azt jelenti, hogy a soron következő játékos minden óvatos válasz mellett elveszíti az állást. A 3, 1 és 2: 3 xor 1 = 2, 2 xor 2 = 0. Ugyanez a csend.
Az eredményes lépés onnan látszik, hogy a nulla felé visz. A 3, 4, 5 asztalon 3 xor 4 xor 5 = 2, tehát van első lépés, amely nullát hagy. Ha az 5-ből kettőt elveszünk, 3 xor 4 xor 3 = 4 xor 4 = 0 marad. A többi első lépés pozitív értéket hagy, és a másik fél azt vissza tudja adni.
G(A + B) = G(A) xor G(B)
A bizonyítás váza az, hogy a mex és a párosítás együtt működik. Minden nemnulla értékű állásból van lépés nullába, nulla értékűből minden lépés pozitívba visz. Két független részre ez a tulajdonság a bitenkénti kizáró vaggyal öröklődik, más összeadással nem. A sakkra a tétel nem ül rá: ott a két félnek nem ugyanazok a lépései, a játék nem pártatlan.
Hol törik a modell
Abban a pillanatban, amikor egy lépés két oszlopot egyszerre érint, vagy a levett kövekből új oszlop születik, a „név = kövek száma” egyszerűség eltűnik. Az érték továbbra is mex, de már nem a magasság. A füzet ezért nem állítja, hogy minden köves játék „kiszámolt”. Azt állítja, hogy a független Kőhalom osztálya igen, és hogy az első kérdés mindig ez: a lépés egy komponenst bont, vagy összeköt kettőt.
A mélység nem a kövek számával nő egy az egyben. Nagy oszlopok mellett is lehet sekély a döntés, ha az állás értéke szemmel láthatóan nulla vagy nem nulla. A nehézség ott kezdődik, ahol a komponensek definíciója maga is vita.