Az A. 924. feladat (2026. január)

A. 924. Mely pozitív egész $\displaystyle (k,l)$ párokra teljesül, hogy bármely pozitív egész $\displaystyle n$ esetén létezik olyan $\displaystyle 0\leq i\leq l-1$ egész, amelyre

$\displaystyle \binom{n}{i}+(-1)^l\binom{n}{i+l}+(-1)^{2l}\binom{n}{i+2l}+\ldots $

nem osztható $\displaystyle k$-val?

(Kvant feladat nyomán)

(7 pont)

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

1. megoldás: A megoldás során használni fogjuk a következő jelölést: az $\displaystyle a(x)$, $\displaystyle b(x)$, $\displaystyle m(x)$ egész együtthatós polinomokra

$\displaystyle a(x) \equiv b(x) \pmod{m(x)}, $

ha van olyan egész együtthatós $\displaystyle h(x)$ polinom, amelyre $\displaystyle a(x)-b(x)=h(x)m(x)$. Továbbá, ha egy egész együtthatós $\displaystyle a(x)$ polinom mindegyik együtthatója osztható $\displaystyle k$-val, akkor azt mondjuk, hogy az $\displaystyle a(x)$ polinom osztható $\displaystyle k$-val.

Rögzítsük az $\displaystyle l$-et, legyen

$\displaystyle A_{n,i}=\binom{n}{i}+ (-1)^l\binom{n}{i+l}+(-1)^{2l}\binom{n}{i+2l}+\ldots$

a feladatbeli kifejezés, és vizsgáljuk az

$\displaystyle R_n(x) = \sum_{i=0}^{l-1}(-1)^iA_{n,i}x^i $

polinomot. A feladat kérdése az, hogy milyen $\displaystyle n$ esetén igaz, hogy $\displaystyle R_n(x)$ semmilyen $\displaystyle n$-re sem osztható $\displaystyle k$-val.

1. lemma.

$\displaystyle R_n(x) \equiv (1-x)^n \pmod{x^l-1}. $

Bizonyítás. Vegyük észre, hogy

$$\begin{align*} R_n(x)-(1-x)^n &= \sum_{i=0}^{l-1}(-1)^i\bigg( \binom{n}{i}+ (-1)^l\binom{n}{i+l} +\ldots \bigg)x^i - \sum_{i=0}^{n}(-1)^i\binom{n}{i}x^i= \\ &= \sum_{i=0}^{l-1}(-1)^i \bigg((-1)^l\binom{n}{i+l}(1-x^l)+(-1)^{2l}\binom{n}{i+2l}(1-x^{2l})+\ldots\bigg)x^i \end{align*}$$

osztható az $\displaystyle x^l-1$ polinommal. $\displaystyle \Box$

2. lemma. Ha valamely $\displaystyle n$-re $\displaystyle R_n(x)$ osztható $\displaystyle k$-val, akkor $\displaystyle R_{n+1}(x)$ is osztható $\displaystyle k$-val.

Bizonyítás. Legyen $\displaystyle R_n(x)$-ben az $\displaystyle x^{l-1}$ együtthatója $\displaystyle c$. Ekkor

$\displaystyle R_{n+1}(x) \equiv (1-x)^{n+1} \equiv (1-x)R_n(x) \equiv (1-x)R_n(x)+c(x^l-1) \pmod{x^l-1}, $

$\displaystyle x^l-1 \,\big|\, R_{n+1}(x)-(1-x)R_n(x)-c(x^l-1). $

Az utóbbi polinomban az $\displaystyle x^l$ tag kiesik, így foka kisebb, mint $\displaystyle n$; az oszthatóság csak a konstans $\displaystyle 0$ polinomra lehet igaz, tehát

$\displaystyle R_{n+1}(x) = (1-x)R_n(x)+c(x^l-1). $

Mivel $\displaystyle R_n(x)$ együtthatói és $\displaystyle c$ is osztható $\displaystyle k$-val, ugyanez igaz az $\displaystyle R_{n+1}(x)$-re is. $\displaystyle \Box$

Most több esetre bontjuk a feladatot. Tegyük fel, hogy $\displaystyle k,l\ge 2$, hiszen $\displaystyle k=1$ esetén vagy $\displaystyle l=1$ esetén nyilván nem igaz a feladat állítása ($\displaystyle l=1$ esetén $\displaystyle n=1$-re 0-t kapunk).

1. eset: $\displaystyle l$-nek van olyan prímosztója, amely különbözik a $\displaystyle k$ szám valamely $\displaystyle p$ prímosztójától.

Tekintsünk egy tetszőleges $\displaystyle n$ pozitív egészt, és legyen $\displaystyle t$ olyan nagy pozitív egész, amelyre $\displaystyle p^t\ge n$.

Vizsgáljuk meg a $\displaystyle R_{p^t}(x)$ polinomot. Az $\displaystyle l$-nek van $\displaystyle p$-től különböző prímosztója, így az $\displaystyle l$ nem lehet osztója $\displaystyle p^t$-nek.

$\displaystyle A_{p^t,0} = \binom{p^t}{0}+ (-1)^n\binom{p^t}{l}+(-1)^{2l}\binom{p^t}{2l}+\ldots, $

összegben $\displaystyle \binom{p^t}{0}=1$, és nem szerepel a $\displaystyle \binom{p^t}{p^t}$, mert $\displaystyle p^t$ nem többszöröse $\displaystyle l$-nek. Az összegben szereplő többi binomiális együttható mind osztható $\displaystyle p$-vel. Tehát $\displaystyle A_{p^t,0}\equiv1\pmod{p}$, és így az $\displaystyle R_{p^t}(x)$ polinom nem lehet osztható $\displaystyle p$-vel.

A 2. lemma miatt, ha $\displaystyle R_n(x)$ osztható lenne $\displaystyle p$-vel, akkor $\displaystyle R_{n+1}(x),R_{n+2}(x),\ldots,$ is osztható lenne $\displaystyle p$-vel, holott, mint láttuk, $\displaystyle R_{p^t}(x)$ nem osztható $\displaystyle p$-vel. Ezzel azt kaptuk, hogy $\displaystyle R_n(x)$ semmilyen $\displaystyle n$-re sem osztható $\displaystyle p$-vel, és így $\displaystyle k$-val sem (hiszen $\displaystyle p\mid k$).

2. eset: ha az előző állítás nem teljesül $\displaystyle l$-re és $\displaystyle k$-ra, akkor $\displaystyle l$-nek csak egyféle prímosztója lehet. Ha $\displaystyle k$-nak lenne ettől különböző prímosztója, akkor is teljesülne az előző állítás $\displaystyle l$-re és $\displaystyle k$-ra. Így tehát az az eset van hátra, ha $\displaystyle l$ és $\displaystyle k$ is ugyanannak a $\displaystyle p$ prímnek a hatványa.

Legyen $\displaystyle l=p^s$ és $\displaystyle k=p^t$. Azt állítjuk, hogy $\displaystyle R_{tp^{s}}(x)$ osztható $\displaystyle p^t$-nel. Ha $\displaystyle t=1$, akkor

$$\begin{align*} R_{p^s}(x) =(1-x)^{p^s}-(-1)^p(x^{p^s}-1) =\sum_{i=1}^{p^s-1}(-1)^s\binom{p^s}{i}x^i+\big(1+(-1)^{p}\big); \end{align*}$$

A szummában mindegyik $\displaystyle \binom{p^s}{i}$ osztható $\displaystyle p$-vel. Ha $\displaystyle p$ páratlan, akkor az utolsó két tag kiesik, ha pedig $\displaystyle p=2$, akkor $\displaystyle 1+(-1)^{p}=2$ osztható $\displaystyle 2$-vel, tehát az $\displaystyle R_{p^s}(x)$ polinom valóban osztható $\displaystyle p$-vel.

Ha most $\displaystyle t$ tetszőleges, akkor a $\displaystyle q(x)=\frac1p \left(\sum_{i=1}^{p^s-1}(-1)^s\binom{p^s}{i}x^i+\big(1+(-1)^{p}\big)\right)$ jelöléssel

$\displaystyle (1-x)^{tp^{s}}=\left((1-x)^{p^s}\right)^t=\left(p\cdot q(x)+(-1)^p(x^{p^s}-1)\right)^t=p^t\cdot q^t(x)+(x^{p^s}-1)\cdot r(x) $

alkalmas $\displaystyle r(x)$ polinommal, azaz $\displaystyle (1-x)^{tp^{s}}\equiv p^t\cdot q^t(x) \pmod{x^{p^s}-1}$, és ezzel az állítást igazoltuk.

Összefoglalva,

Ha létezik olyan prímszám, melynek $\displaystyle k$ és $\displaystyle l$ is hatványa vagy $\displaystyle k=1$ vagy $\displaystyle l=1$, akkor nem igaz a feladat állítása,
Ellenkező esetben (azaz lehet találni $\displaystyle p\neq q$ prímszámokat, melyekre $\displaystyle p\mid k$, $\displaystyle q\mid l$) pedig igaz a feladat állítása.

2. megoldás: A feladat állítása nyilván nem igaz, ha $\displaystyle k=1$ vagy $\displaystyle l=1$, ezért tegyük fel, hogy $\displaystyle k,l\ge2$. Fogalmazzuk át a feladatot. Legyen $\displaystyle l$ rögzített. Ekkor $\displaystyle n$-et és $\displaystyle i$-t változtatva az eredményeket megkaphatjuk a következő módon: legyen felírva egy körre $\displaystyle l$ darab szám, kezdetben egy 1-es és azon kívül csupa 0 (ez éppen $\displaystyle n=0$-ra a képlet értéke $\displaystyle i=0,1,2,\ldots ,l-1$-re). Ezután minden lépésben vesszük a körre írt számokat, $\displaystyle a_0,a_1,\ldots ,a_{l-1}$-et, és helyettük a szomszédosak különbségeit, azaz az $\displaystyle a_1-a_0,a_2-a_1,\ldots ,a_0-a_{l-1}$ számokat írjuk fel. Teljes indukcióval bizonyítható, hogy az $\displaystyle n.$ lépésben előjeltől eltekintve éppen a képlet értékeit kapjuk az adott $\displaystyle l$ mellett $\displaystyle i=0,1,\ldots ,l-1$-re. A feladat átfogalmazva tehát az, hogy milyen $\displaystyle l$ esetén lesz minden lépés után legalább egy $\displaystyle k$-val nem osztható szám a körön.

A megoldás kulcsa az a megfigyelés, hogy ha nem igaz a feladat állítása, azaz megjelenik előbb-utóbb a csupa 0 (mod $\displaystyle k$) a körön, akkor ez akkor is igaz, ha $\displaystyle l$ darab tetszőleges egész számból indulunk ki a körön. Ennek az az oka, hogy a forgásszimmetria miatt bárhol lehet a kezdeti 1-es a körön, és hogy az ilyen kiindulási állapotok (egy darab 1-es valahol, egyébként csupa 0) lineáris kombinációjaként bármely kezdeti szám $\displaystyle l$-es megkapható, továbbá hogy a képzési szabály lineáris. Ebből az is következik, hogy ha az $\displaystyle N.$ lépésben csupa 0 jön ki abból a kiindulási állapotból, amely egy darab 1-esből és rajta kívül csupa 0-ból áll, akkor bármely kiindulási állapot esetén is csupa 0 lesz a körön $\displaystyle N$ lépés után.

Először megmutatjuk, hogy ha $\displaystyle k$-nak van olyan $\displaystyle p$ prímosztója, amely nem osztja $\displaystyle l$-et, akkor ez nem teljesül (azaz a feladat eredeti állítása igaz). Ehhez elég azt megmutatni, hogy akármilyen sok lépés esetén van olyan kiindulási állapot, amely az adott lépésszám után nem nullázódik ki modulo $\displaystyle p$ (itt rejlik a lényeg: bár nekünk ezt eredetileg egy konkrét szám $\displaystyle l$-esre kellett volna megmutatni, kiderült, hogy ha a lépések számának függvényében más és más szám $\displaystyle l$-est mutatunk, ami nem nullázódik ki, az is egyenértékű ezzel). Ezt úgy mutatjuk meg, hogy ha van olyan kiindulási állapot, amely $\displaystyle \ell$ lépés után nem nullázódik ki, akkor olyan is van, amelyik $\displaystyle \ell+1$ lépés után nem nullázódik ki. Ehhez az az ötlet, hogy ha az $\displaystyle a_0,a_1,\ldots, a_{l-1}$ nem nullázódik ki $\displaystyle \ell$ lépésben, akkor $\displaystyle a_0+c,a_1+c,\ldots, a_{l-1}+c$ sem, hiszen az első lépés után már ugyanazt a szám $\displaystyle l$-est kapjuk a körön. Ha tudnánk találni olyan $\displaystyle b_0,\ldots ,b_{l-1}$ szám $\displaystyle l$-est, amelyből egy lépés után az $\displaystyle a_0+c,\ldots ,a_{l-1}+c$ szám $\displaystyle l$-est kapjuk (mod $\displaystyle p$), készen lennénk. Egy szám $\displaystyle l$-est pontosan akkor tudunk megkapni egy lépést elvégezve modulo $\displaystyle p$, ha a megkapni kívánt $\displaystyle l$ darab szám összege 0 mod $\displaystyle p$, azaz $\displaystyle c$-t úgy kéne választani, hogy $\displaystyle a_0+\ldots +a_{l-1}+lc$ 0 legyen mod $\displaystyle p$: ez pedig lehetséges, ha $\displaystyle p\nmid l$, hiszen ekkor $\displaystyle lc$ maradéka bármi lehet mod $\displaystyle p$, $\displaystyle c$ alkalmas választásával. Arra kell még figyelni, hogy kell egy olyan $\displaystyle l$-es, amellyel legalább egy lépést lehet csinálni anélkül, hogy kinullázódna, ez pedig $\displaystyle l\ge 2$ miatt lehetséges.

Ebből az is következik, hogy ha $\displaystyle l$-nek van $\displaystyle p$-hez relatív prím, 1-nél nagyobb osztója (legyen ez $\displaystyle l_0$), akkor is teljesül a feladat állítása. Vegyünk $\displaystyle b_0,b_1,\ldots ,b_{l_0-1}$-t, amellyel $\displaystyle \ell$ lépésen át nem nullázódik ki a kör: az előző bekezdés alapján ez lehetséges. Ezután legyen $\displaystyle a_i=b_j$, ha $\displaystyle l_0\mid i-j$: könnyű látni, hogy ez sem nullázódik ki $\displaystyle \ell$ lépésben (hiszen egy $\displaystyle l_0$ hosszú szakaszon épp ugyanaz történik a nagyobb körön, mint amikor csak $\displaystyle l_0$ darab számot írtunk a körre).

Így végül azt kaptuk, hogy ha van $\displaystyle k$-nak olyan $\displaystyle p$ prímosztója, melyre $\displaystyle l$-nek van $\displaystyle p$-től különböző prímosztója, akkor a feladat állítása igaz. Ez pedig teljesül, ha $\displaystyle k$-nak van legalább 2 prímosztója. Ha $\displaystyle k$ prímhatvány, és $\displaystyle l$ nem ugyanennek a prímnek a hatványa, akkor is teljesül az állítás.

Most megmutatjuk, hogy ha $\displaystyle k=p^t$ és $\displaystyle l=p^s$, akkor fogunk kapni csupa 0 maradékot mod $\displaystyle k=p^t$. Ez egyszerű, ha $\displaystyle t=1$, felhasználva azt az ismert állítást, hogy $\displaystyle p\mid \binom{p^s}{i}$, ha $\displaystyle i\neq 0,p^s$, így $\displaystyle n=p^s$ jó lesz, mert $\displaystyle \binom{p^s}{0}$ és $\displaystyle \binom{p^s}{p^s}$ kiejtik egymást az $\displaystyle i=0$ esetben, a többi esetben pedig egyetlen $\displaystyle p$-vel osztható binomiális együtthatót kell összegezni.

Végül $\displaystyle t$ szerinti teljes indukcióval igazolhatjuk a fenti állítást, ismét csak a körös átfogalmazást felhasználva: láttuk, hogy $\displaystyle l=p^s$ esetén néhány (amúgy $\displaystyle p^s$) lépés után minden szám osztható lesz $\displaystyle p$-vel; akkor újabb ugyanennyi lépés után minden szám osztható lesz $\displaystyle p^2$-tel (hiszen a $\displaystyle p$-vel való oszthatóság bármilyen szám $\displaystyle l$-esből kiindulva igaz lesz), és ezt $\displaystyle t-1$-szer megismételve (azaz összesen $\displaystyle tp^{s}$ lépés után) eljutunk a $\displaystyle p^t$-es oszthatóságig.

Tehát a válasz a feladat kérdésére: a $\displaystyle k=p^t$, $\displaystyle l=p^s$ párok kivételével lesz igaz a feladat állítása $\displaystyle k,l\ge 2$ esetén, és nem lesz igaz, ha $\displaystyle k=1$ vagy $\displaystyle l=1$.

Statisztika:

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

A KöMaL 2026. januári matematika feladatai

Már regisztráltál?
Új vendég vagy?