46.          Az első esetben a Másodiknak van nyerő stratégiája. A következőt csinálja: ha van olyan csupa színes élből álló út, amelyet egy él behúzásával körré lehet zárni, akkor ezt az élt húzza be. Ha nincs, akkor az Első által legutoljára behúzott élnek a főátlóra való tükörképét húzza be. Így minden lépés után a főátlóra szimmetrikus gráfot hagy maga után, feltéve, hogy nem nyert. Ebből következik, hogy mindig fog tudni lépni, hiszen az Első mindig megbontja a szimmetriát. Még az volna elképzelhető, hogy az Elsőnek sikerül (színes) kört bezárnia. Tekintsük azt az utat, amelyet az Első körré zár be. Ha ez az út nem metszené  legalább kétszer a főátlót, akkor a főátlóra vett tükörképe is színes út volna, hiszen a Második lépése után mindig szimmetrikus a gráf a főátlóra. Ez az út is egy éllel körré zárható volna, és a két út közül legalább az egyik nem tartalmazza a Második által utoljára behúzott élt. Tehát legalább az egyik út olyan, hogy azt a Második körré zárhatta volna, s ez esetben a stragégia szerint meg is tette. Ez az eset tehát nem jöhet létre. Ez a meggondolás mindig érvényes, ha az Első által talált színes útnak és tükörképének nincs közös éle. Ha van, akkor a közös él tükörképe is közös él, és a főátló másik oldalán helyezkedik el (a főátlóra nem illeszkedik él). De ekkor az Első által talált út legalább kétszer metszi a főátlót, vagyis a főátló az utat legalább két éldiszjunkt útra bontja. Vegyük ezek közül az (egyik olyan) P utat, amelynek két végpontja a főátlón van. Ennek a főátlóra vett P’ tükörképe is csupa színes élből áll, hiszen a Második szimmetrikus gráfot hagyott maga után. De P’ és P ugyanabban a két pontban éri el a főátlót, tehát P és P’ együtt a gráf egy ciklusát alkotja, s így tartalmaz egy kört. A színes élek tehát legalább egy kört már tartalmaznak, így Elsőnek már nincs módja lépni. Első tehát nem nyerhet, így (mivel a játék véges) a Második nyer.

A fordított játékban elég azt meggondolni, hogy pontosan akkor feszítenek kört a színes élek, ha a nem-színes élek által alkotott gráf (az összes ponton, tehát az (n+1)2 ponton) nem összefüggő. Vagyis akkor kényszerül valamelyik játékos színes kört bezárni, ha a nem-színes élekből alkotott gráf fa, azaz n2+2n éle van. Eredetileg 2n(n+1)=2n2+2n nem színes él van, tehát (ha mindketten jól játszanak) az veszít, akinek az n2+1-edik élt kell behúznia. Vagyis páros n-re az Első nyer, páratlanra a Második.

TARTALOMJEGYZÉK