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