Az A. 812. feladat (2021. december)

A. 812. Két játékos a következő játékot játssza: van két kupac, melyekből felváltva kell kavicsokat elvenniük, és az nyer, aki az utolsó kavicsot elveszi. Ha a kupacok mérete egy adott pillanatban $\displaystyle A$ és $\displaystyle B$, akkor a soron következő játékos valamelyik kupacból elveheti $\displaystyle A$ egy többszörösét vagy $\displaystyle B$ egy többszörösét.

Határozzuk meg azokat az $\displaystyle (k,n)$ számpárokat, melyekre a második játékosnak van nyerő stratégiája, ha kezdetben az egyik kupacban $\displaystyle k$, a másikban pedig $\displaystyle n$ darab kavics van.

Javasolta: Pálvölgyi Dömötör (Budapest)

(7 pont)

A beküldési határidő 2022. január 10-én LEJÁRT.

Megoldás. Azt állítjuk, hogy pontosan akkor van a második játékosnak nyerő stratégiája, ha $\displaystyle n \leq \varphi k$ és $\displaystyle k \leq \varphi n$, ahol $\displaystyle \varphi=\frac{\sqrt{5}+1}{2}$ az úgynevezett aranymetszés. Ismert, és könnyen ellenőrizhető, hogy $\displaystyle \varphi^2-\varphi-1=0$, ezt az azonosságot többször fogjuk alkalmazni.

Nevezzünk egy helyzetet nyerőnek, ha onnan a kezdő játékos nyer, vesztőnek, ha a második. Egy helyzet pontosan akkor nyerő, ha onnan lehet vesztőre lépni, és akkor vesztő, ha onnan csak nyerőre lehet lépni. Világos, hogy a $\displaystyle (0,k)$ és $\displaystyle (k,0)$ helyzetek nyerők, és a $\displaystyle (k,k)$ helyzet vesztő, mivel onnan csak $\displaystyle (0,k)$-ra vagy $\displaystyle (k,0)$-ra lehet lépni ($\displaystyle k>0$), így ezekben az esetekben tényleg igaz az állításunk. Mostantól a $\displaystyle (k,n)$ állapotot vizsgáljuk, és feltesszük, hogy $\displaystyle n,k>0$ és $\displaystyle k<n$.

Először tegyük fel, hogy $\displaystyle (k,n)$ vesztő helyzet, igazoljuk, hogy ekkor csak nyerő helyzetre lehet lépni. Azt tudjuk, hogy $\displaystyle k<n\leq \varphi k<2k$, így ebből az állásból csak a $\displaystyle (0,n)$, $\displaystyle (k,0)$ és $\displaystyle (k,n-k)$ helyzetekbe lehet lépni. Az első kettő nyerő, és a harmadik is, mivel

$\displaystyle \varphi (n-k) \leq \varphi^2k-\varphi k=k,$

és $\displaystyle \varphi$ irracionális, így $\displaystyle \varphi(n-k)<k.$

Most tegyük fel, hogy $\displaystyle (k,n)$ nyerő helyzet, azaz $\displaystyle \varphi k<n$. Indirekten tegyük fel, hogy nem tudunk innen vesztő helyzetre lépni. Osszuk el $\displaystyle n$-t maradékosan $\displaystyle k$-val, legyen $\displaystyle n=dk+r$ ahol $\displaystyle r<k$. Ekkor a $\displaystyle (k,r)$ párra lehet lépni, így $\displaystyle \varphi r<k$. Továbbá a $\displaystyle \varphi k<r+k$ egyenlőtlenség is teljesül, mivel vagy tudunk ide lépni, és akkor az indirekt feltevés miatt igaz, vagy $\displaystyle r+k=n$, ekkor azért igaz, mert $\displaystyle (k,n)$ nyerő helyzet. Ezt a két egyenlőtlenséget összevetve kapjuk, hogy

$\displaystyle \varphi k<r+k<\frac{k}{\varphi}+k.$

Átrendezve és $\displaystyle \varphi$-vel szorozva

$\displaystyle k(\varphi^2-\varphi-1)<0,$

ami ellentmondás, mivel $\displaystyle \varphi^2-\varphi-1=0$.

Ezzel a bizonyítást befejeztük.

Statisztika:

18 dolgozat érkezett.
7 pontot kapott:	Bán-Szabó Áron, Ben Gillott, Diaconescu Tashi, Lovas Márton, Móra Márton Barnabás, Móricz Benjámin, Nádor Benedek, Seres-Szabó Márton, Simon László Bence, Sztranyák Gabriella, Tarján Bernát, Varga Boldizsár.
6 pontot kapott:	Berkó Sebestyén .
5 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2021. decemberi matematika feladatai