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. Megoldás. Definiáljuk az és változókat a következőképpen:
Ha az mezőn lévő érmét egy lépésben kiválasztjuk, akkor az megváltozik. Ha vagy , akkor az változatlan marad. Ha és , vagy és , akkor a fenti összegben két tag változik, így az változatlan marad. Ha és , akkor a fenti összegben mind a négy tag megváltozik, így az változatlan marad. Tehát, ha egy lépésben az mezőn lévő érmét átfordítjuk, akkor csak az változik, a többi nem. Induljunk ki abból a táblázatból, ahol az mezőn pontosan akkor van írás, ha (vagyis és is páratlan).
Látható, hogy minden 1≤i,j≤n esetén yi,j=1. Ha minden érmén fej van, akkor minden 1≤i,j≤n esetén yi,j=0. Így a fenti táblázathoz n2 lépés szükséges, tehát L(n)≥n2. Ha van egy tetszőleges táblázat, akkor soronként, pozitív irányban haladva nézzük végig az érméket. Ha valamelyik érmén írás van, akkor fordítsuk meg. Egy lépés során a korábban bejárt érmék nem fordulnak meg, így mindegyiken fej lesz. Ha az összes érmét bejártuk, akkor az összesen fej lesz. Minden érmét legfeljebb egyszer fordítottunk meg, így legfeljebb n2 lépés volt, ezért L(n)≤n2. Tehát L(n)=n2. |