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