Az A. 904. feladat (2025. március)

A. 904. Legyen \(\displaystyle n\) pozitív egész szám. Egy \(\displaystyle 2n\) oldalú szabályos sokszög egyik csúcsában ül Luca, a lusta bolha. Luca minden ugrása során kiválasztja a sokszögnek valamelyik szimmetriatengelyét, majd annak átugrik a túloldalára úgy, hogy tükrözi magát arra a tengelyre. Jelölje \(\displaystyle P(n)\) azt, hogy hány különböző módon tud Luca \(\displaystyle 2n\) egymás utáni ugrást végrehajtani úgy, hogy útja végén visszatérjen kezdeti helyzetébe és közben ne tükrözze magát ugyanarra a tengelyre kétszer. (Előfordulhat, hogy Luca helyben ugrik egyet, ez is ugrásnak minősül.)

a) Határozzuk meg \(\displaystyle P(n)\) értékét, ha \(\displaystyle n\) páratlan.

b) Igazoljuk, hogy ha \(\displaystyle n\) páros, akkor

\(\displaystyle P(n)=(n-1)!\cdot n!\cdot \sum_{d\mid n,d\in \mathbb{N}}\biggl(\varphi\left (\dfrac{n}{d}\right) \cdot \binom{2d}{d} \biggr), \)

ahol \(\displaystyle \varphi(k)\) a \(\displaystyle k\)-nál kisebb, \(\displaystyle k\)-hoz relatív prím pozitív egészek számát jelöli.

Javasolta: Csikvári Péter és Nagy Kartal (Budapest)

(7 pont)

A beküldési határidő 2025. április 10-én LEJÁRT.

Számozzuk meg a sokszög csúcsait az \(\displaystyle 1,2,...,2n\) számokkal. Egy tengelyes tükrözés egy \(\displaystyle a\) számmal írható le, ahol \(\displaystyle a\) végigfut az \(\displaystyle 1,2,...,2n\) számokon, és az \(\displaystyle x\) csúcs képe \(\displaystyle a-x\) (modulo \(\displaystyle 2n\)). A feladatban tehát azt kérdezik, hogy az \(\displaystyle 1,2,...,2n\) számoknak hány olyan \(\displaystyle a_1,a_2,...,a_{2n}\) sorrendje van, amelynél \(\displaystyle L=a_{2n}-(a_{2n-1}-(...-(a_2-(L-a_1))))\) modulo \(\displaystyle 2n\) (ahol \(\displaystyle L\) Luca kezdeti pozícióját jelöli). A zárójeleket felbontva azt kapjuk, hogy \(\displaystyle L=L+(a_{2n}-a_{2n-1}+...+a_2-a_1)\) modulo \(\displaystyle 2n\), azaz \(\displaystyle a_{2n}-a_{2n-1}+....+a_2-a_1=0\) modulo \(\displaystyle 2n\).

a) Megmutatjuk, hogy ha \(\displaystyle n\) páratlan, akkor nem kaphatunk 0-t modulo \(\displaystyle 2n\). Ez azért van, mert az \(\displaystyle 1+2+...+2n=n(2n+1)=n\) modulo \(\displaystyle 2n\), de ha \(\displaystyle a_1+a_3+...+a_{2n-1}=a_2+a_4+...+a_{2n}=x\) modulo \(\displaystyle 2n\), akkor \(\displaystyle 2x=n\) modulo \(\displaystyle 2n\), ami nyilván lehetetlen, ha \(\displaystyle n\) páratlan. Ilyenkor tehát \(\displaystyle P(n)=0\).

b) Az előző részt felhasználva az \(\displaystyle x=n/2\) modulo \(\displaystyle n\), azaz azt kell kiszámolnunk, hogy hányféle módon lehet \(\displaystyle n\) számot kiválasztani az \(\displaystyle 1,2,...,2n\) számok közül, hogy az összegük \(\displaystyle n\)-nel osztva \(\displaystyle m=n/2\) maradékot adjon. A stratégiánk a következő: kiszámoljuk, hogy hány esetben lesz az \(\displaystyle n\) darab kiválasztott szám összege osztható \(\displaystyle m=n/2\)-vel, és kivonjuk belőle azokat az eseteket, amikor \(\displaystyle n\)-nel is osztható az összeg.

Tekintsük a

\(\displaystyle p(x,y)=\prod_{i=1}^{2n}(1+x^iy) \)

kétváltozós polinomot. Ebben a polinomban az \(\displaystyle x^ay^b\) tag együtthatója azzal egyenlő, hogy hány olyan \(\displaystyle b\) elemű részhalmaza van az \(\displaystyle \{1,2,...,2n\}\) halmaznak, amelyben az elemek összege \(\displaystyle a\). Nekünk tehát az \(\displaystyle x^{i}y^n\) együtthatóinak az összegére van szükség, ahol \(\displaystyle i\) végigfut az \(\displaystyle m=n/2\) többszörösein. Legyen \(\displaystyle \omega\) egy \(\displaystyle m=n/2\)-ik primitív egységgyök. Most az állítjuk, hogy a

\(\displaystyle \frac{1}{m}\sum_{k=1}^{m}p(\omega^k,y) \)

polinomban az \(\displaystyle y^n\) együtthatója épp a keresett szám. Ez azon a jól ismert tényen múlik, hogy a \(\displaystyle \sum_{k=1}^{m}\omega^{ak}\) összeg értéke 0, ha \(\displaystyle a\) nem osztható \(\displaystyle m\)-mel, egyébként pedig \(\displaystyle m\). Következő célunk tehát \(\displaystyle p(\omega^k,y)\) meghatározása. Legyen \(\displaystyle \xi\) egy \(\displaystyle d\)-ik primitív egységgyök, ahol \(\displaystyle d|2n\). Ekkor a jól ismert \(\displaystyle z^d-1=(z-1)(z-\xi)(z-\xi^2)...(z-\xi^{d-1})\) állítás alapján \(\displaystyle \prod_{i=1}^{d}(1+\xi^iy)=1-(-1)^dy^d\). Így, mivel a \(\displaystyle \xi\) hatványai ciklikusan ismétlődnek, \(\displaystyle p(\xi,y)=(1+(-1)^{d+1}y^d)^{\frac{2n}{d}}\). Innen megvagyunk, hiszen \(\displaystyle \omega^k\) egy \(\displaystyle \frac{m}{\text{gcd}(k,m)}\)-ik primitív egységgyök (\(\displaystyle \text{gcd}(a,b)\) az \(\displaystyle a\) és \(\displaystyle b\) szám legnagyobb közös osztóját jelöli).

Vizsgáljuk most \(\displaystyle y^n\) együtthatóját a \(\displaystyle \frac{1}{m}\sum_{k=1}^{m}p(\omega^k,y)\) polinomban. Az \(\displaystyle (1+(-1)^{d+1}y^d)^{\frac{2n}{d}}\) polinomban a binomiális tétel alapján az \(\displaystyle y^n\) együtthatója \(\displaystyle (-1)^{\frac{n(d+1)}{d}}\binom{2n/d}{n/d}\), ha \(\displaystyle d|n\), amúgy nem keletkezik \(\displaystyle y^n\)-es tag. Azt is meg kell számolnunk, hogy hány esetben lesz \(\displaystyle \omega^k\) egy \(\displaystyle d\)-ik primitív egységgyök (ilyenkor \(\displaystyle d\) persze \(\displaystyle m=n/2\)-t is osztja, és ezen a ponton jegyezzük meg, hogy ez szerencsére azt is jelenti, hogy az \(\displaystyle (-1)\) kitevője páros, hiszen \(\displaystyle n/d\) is az): ez pontosan akkor következik be, ha \(\displaystyle \text{gcd}(k,m)=m/d\), azaz \(\displaystyle k\) az \(\displaystyle m/d\) és egy \(\displaystyle 1\) és \(\displaystyle d\) közötti, \(\displaystyle d\)-hez relatív prím szám szorzata, vagyik \(\displaystyle \varphi(d)\) darab esetben. Tehát a keresett együttható

\(\displaystyle \frac{1}{m}\sum_{d|m}\varphi(d)\binom{2n/d}{n/d}=\frac{1}{m}\sum_{d'|m}\varphi(m/d')\binom{4d'}{2d'}=\frac{1}{m}\sum_{d''|n,\,d''\text{ páros}}\varphi(n/d'')\binom{2d''}{d''}. \)

Ha most az \(\displaystyle n\)-nel osztható részhalmazok számát szeretnénk meghatározni, akkor hasonló módon járhatunk el, csak most \(\displaystyle \omega\)-t egy \(\displaystyle n\)-ik egységgyöknek kell választani. A fenti számolásban ott lesz egy apró különbség, hogy \(\displaystyle (-1)^{\frac{n(d+1)}{d}}\) most tud \(\displaystyle -1\) is lenni: ha \(\displaystyle d\) osztópárja, \(\displaystyle d''=n/d\) páratlan (ilyenkor \(\displaystyle d\) páros érték, tehát \(\displaystyle d+1\) is páratlan), vagy más szóval \(\displaystyle d\) osztja \(\displaystyle n\)-et, de \(\displaystyle n/2\)-t nem (itt érdemes megfigyelni, hogy éppen ezek az osztók hiányoztak a korábbi összegünkből). Így most az \(\displaystyle n\)-nel osztható összegekre azt kapjuk, hogy

\(\displaystyle \frac{1}{n}\sum_{d|n}(-1)^{\frac{n(d+1)}{d}}\varphi(d)\binom{2n/d}{n/d}=\frac{1}{n}\sum_{d''|n}(-1)^{d''}\varphi(n/d'')\binom{2d''}{d''}. \)

Így végül a keresett szám a fenti összegek különbsége (most már \(\displaystyle d''\) helyett \(\displaystyle d\)-t írva a szummákban):

\(\displaystyle \left(\frac{1}{m}-\frac{1}{n}\right)\sum_{d|n,d \text{ páros}}\varphi(n/d)\binom{2d}{d}+\frac{1}{n}\sum_{d|n,d \text{ páratlan}}\varphi(n/d)\binom{2d}{d}, \)

és ez épp a bizonyítandót adja, hiszen \(\displaystyle 1/m-1/n=2/n-1/n=1/n\), és a kiválasztott \(\displaystyle n\)-est, illetve a komplementerét \(\displaystyle n!\cdot n!\) féle módon lehet sorbarendezni (a megoldás elején elmondottakból következik az a nem magától értetődő tény, hogy az egy ponton átmenő tengelyű tükrözések kompoziciójánál nem számít a páros, illetve a páratlan helyeken szereplő tükrözések sorrendje).

Statisztika:

Az A. 904. feladat értékelése még nem fejeződött be.

A KöMaL 2025. márciusi matematika feladatai