Feladat:	B.4781	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Gáspár Attila
Füzet:	2016/szeptember, 346 - 347. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Logikai feladatok
Hivatkozás(ok):	Feladatok: 2016/március: B.4781

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 $x_{i\mathrm{,}j}$ és $y_{i\mathrm{,}j}$ változókat a következőképpen: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle x_{i\mathrm{,}j}}& {\displaystyle =\{{\displaystyle \begin{array}{cc}\hfill {\displaystyle \mathrm{0,}}& {\displaystyle \text{ha }i=\mathrm{0,}\text{ vagy }j=\mathrm{0,}}\hfill \\ \hfill {\displaystyle \mathrm{0,}}& {\displaystyle \text{ha }i\ne \mathrm{0,}\text{ és }j\ne \mathrm{0,}\text{ és az }\left(i\mathrm{,}j\right)\text{ mezőn fej van,}}\hfill \\ \hfill {\displaystyle \mathrm{1,}}& {\displaystyle \text{ha }i\ne \mathrm{0,}\text{ és }j\ne \mathrm{0,}\text{ és az }\left(i\mathrm{,}j\right)\text{ mezőn írás van,}}\hfill \end{array}}}\hfill \\ \hfill {\displaystyle y_{i\mathrm{,}j}}& {\displaystyle =\{{\displaystyle \begin{array}{cc}\hfill {\displaystyle \mathrm{0,}}& {\displaystyle \text{ha az }{x}_{i\mathrm{,}j}+x_{i-\mathrm{1,}j}+x_{i\mathrm{,}j-1}+x_{i-\mathrm{1,}j-1}\text{ összeg páros,}}\hfill \\ \hfill {\displaystyle \mathrm{1,}}& {\displaystyle \text{különben.}}\hfill \end{array}}}\hfill \end{array}}$ Ha az $\left(i\mathrm{,}j\right)$ mezőn lévő érmét egy lépésben kiválasztjuk, akkor az $y_{i\mathrm{,}j}$ megváltozik. Ha $k<i$ vagy $\ell <j$, akkor az $y_{k\mathrm{,}\ell }$ változatlan marad. Ha $k=i$ és $\ell >j$, vagy $k>i$ és $\ell =j$, akkor a fenti összegben két tag változik, így az $y_{k\mathrm{,}\ell }$ változatlan marad. Ha $k>i$ és $\ell >j$, akkor a fenti összegben mind a négy tag megváltozik, így az $y_{k\mathrm{,}\ell }$ változatlan marad. Tehát, ha egy lépésben az $\left(i\mathrm{,}j\right)$ mezőn lévő érmét átfordítjuk, akkor csak az $y_{i\mathrm{,}j}$ változik, a többi nem. Induljunk ki abból a táblázatból, ahol az $\left(i\mathrm{,}j\right)$ mezőn pontosan akkor van írás, ha $i\equiv j\equiv 1\left(\text{mod}2\right)$ (vagyis $i$ és $j$ is páratlan).     Látható, hogy minden $1\le i\mathrm{,}j\le n$ esetén $y_{i\mathrm{,}j}=1$. Ha minden érmén fej van, akkor minden $1\le i\mathrm{,}j\le n$ esetén $y_{i\mathrm{,}j}=0$. Így a fenti táblázathoz $n^2$ lépés szükséges, tehát $L\left(n\right)\ge n^2$. 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 $n^2$ lépés volt, ezért $L\left(n\right)\le n^2$. Tehát $L\left(n\right)=n^2$.