Az A. 666. feladat (2016. március)

A. 666. Legyen $\displaystyle p$ prímszám, $\displaystyle k$ pozitív egész, és legyen $\displaystyle \mathcal{A}$ egész számokból álló, legalább $\displaystyle p^k$-elemű véges halmaz. Jelölje $\displaystyle N_{\text{páros}}$ az $\displaystyle \mathcal{A}$ olyan, páros elemszámú részhalmazainak számát, amelyekben az elemek összege osztható $\displaystyle p^k$-nal. Hasonlóan, jelölje $\displaystyle N_{\text{páratlan}}$ az $\displaystyle \mathcal{A}$ olyan, páratlan elemszámú részhalmazainak számát, amelyekben az elemek összege osztható $\displaystyle p^k$-nal. Mutassuk meg, hogy $\displaystyle N_{\text{páros}}\equiv N_{\text{páratlan}} \pmod{p}$.

(5 pont)

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

Megoldás (vázlat). Legyen $\displaystyle \mathcal{A}=\{a_1,a_2,\ldots,a_n\}$, ahol tehát $\displaystyle n=|\mathcal{A}|\ge p^k$. Az $\displaystyle \mathcal{A}$ részhalmazait $\displaystyle n$ hosszúságú $\displaystyle 0-1$ sorozatokkal fogjuk kódolni. Minden egyes $\displaystyle (\chi_1,\ldots,\chi_n)$ sorozat, amelyben $\displaystyle \chi_1,\ldots,\chi_n\in\{0,1\}$, megfelel az $\displaystyle \{a_i: \chi_i=1\}$ részhalmaznak; a részhalmaz elemeinek összege $\displaystyle \chi_1a_1+\ldots+\chi_na_n$.

Konstruálunk egy $\displaystyle f(x_1,\ldots,x_n)$ valós együtthatós polinomot, amire a következők teljesülnek:

(1) Az $\displaystyle f$ foka kisebb, mint $\displaystyle p^k$;

(2) Tetszőleges $\displaystyle \chi_1,\ldots,\chi_n\in\{0,1\}$ sorozatra $\displaystyle f(\chi_1,\ldots,\chi_n)$ egész szám, és

Az $\displaystyle f$ függvényt fogjuk használni az olyan részhalmazok összeszámolására, amelyekben az elemek összege osztható $\displaystyle p^k$-val.

A konstrukció a következő, jól ismert tényen alapul: tetszőleges $\displaystyle S$ pozitív egészre

Ez egyszerű következménye a Lucas-lemmának, de közvetlenül is könnyen ellenőrizhető.

Legyen

$\displaystyle f(x_1+\ldots+x_n) = \binom{a_1x_1+\ldots+a_nx_n+p^k-1}{p^k-1} = \dfrac{\prod\limits_{i=1}^{p^k-1} (a_1x_1+\ldots+a_nx_n+i)}{(p^k-1)!};$

ez egy $\displaystyle n$-változós polinom, a foka legfeljebb $\displaystyle p^k-1$, és egész helyeken az értéke is egész. Az $\displaystyle (L)$ tulajdonságból $\displaystyle (*)$ azonnal következik.

Az $\displaystyle f$ polinom birtokában igazoljuk a feladat állítását. Legyen az $\displaystyle f(x_1,\dots,x_n)$ kifejtése

ahol az $\displaystyle u_1,\ldots,u_n$ kitevők mindig nemnegatív egészek, és megállapodunk abban, hogy a változók nulladik hatványa a konstans $\displaystyle 1$-et jelenti. Ekkor

$\displaystyle N_{\text{páros}} - N_{\text{páratlan}} \equiv \sum_{\chi_1,\ldots,\chi_n\in\{0,1\}} (-1)^{\chi_1+\ldots+\chi_n} f(\chi_1,\ldots,\chi_n) \pmod{p}.$

A jobboldalon álló szám

$\displaystyle \sum_{\chi_1,\ldots,\chi_n\in\{0,1\}} (-1)^{\chi_1+\ldots+\chi_n} \sum_{u_1,\ldots,u_n} C_{u_1,\ldots, u_n} \chi_1^{u_1} \ldots \chi_n^{u_n} =$

$\displaystyle = \sum_{u_1,\ldots,u_n} C_{u_1,\ldots, u_n} \sum_{\chi_1,\ldots,\chi_n\in\{0,1\}} (-1)^{\chi_1+\ldots+\chi_n} \chi_1^{u_1} \ldots \chi_n^{u_n} =$

Mivel $\displaystyle \deg f<p^k\le n$, minden (F)-ben előforduló $\displaystyle (u_1,\ldots,u_n)$ kitevősorozat tartalmaz legalább egy $\displaystyle 0$ értéket. Ha viszont valamelyik $\displaystyle i$ indexre $\displaystyle u_i=0$, akkor a (J) utolsó szorzatában az $\displaystyle i$-edik tényező $\displaystyle 0$:

$\displaystyle \sum_{\chi_i\in\{0,1\}} (-1)^{\chi_i} \chi_i^{u_i} = \sum_{\chi_i\in\{0,1\}} (-1)^{\chi_i} \chi_i^0 = 1-1 = 0.$

Tehát, a (J)-ben az utolsó összeg biztosan $\displaystyle 0$.

Ezzel bebizonyítottuk, hogy $\displaystyle N_{\text{páros}} - N_{\text{páratlan}} \equiv 0 \pmod{p}$.

Megjegyzés. Olyan $\displaystyle f(x_1,\ldots,x_n)$ polinom is létezik, amelyre (1) és (2) teljesül, és az együtthatói egész számok. Mutatunk egy ilyen konstrukciót.

Készítsük el $\displaystyle n$-változós polinomok egy sorozatát a következőképpen: vegyünk $\displaystyle a_1$ példányt az $\displaystyle x_1$ monomból, $\displaystyle a_2$ példányt az $\displaystyle x_2$ monomból, ..., és $\displaystyle a_n$ példányt az $\displaystyle x_n$ monomból, végül vegyünk $\displaystyle p^k-1$ darab konstans $\displaystyle 1$-et. A kapott polinomsorozatot jelölje

$\displaystyle \big( P_1(x_1,\ldots,x_n),\, P_2(x_1,\ldots,x_n),\, \ldots,\, P_N(x_1,\ldots,x_n) \big) = \big( \underbrace{x_1,\ldots,x_1}_{a_1\mathrm{~db}}, \underbrace{x_2,\ldots,x_2}_{a_2\mathrm{~db}}, \ldots, \underbrace{x_n,\ldots,x_n}_{a_n\mathrm{~db}}, \underbrace{1,\ldots,1}_{p^k-1 \mathrm{~db}} \big),$

ahol tehát $\displaystyle N=a_1+a_2+\ldots+a_n+p^k-1$, és tetszőleges $\displaystyle \chi_1,\ldots,\chi_n\in\{0,1\}$ esetén

$\displaystyle \sum_{i=1}^N P_i(\chi_1,\ldots,\chi_n) = \chi_1a_1+\ldots+\chi_na_n + p^k-1.$

Válasszunk ki az $\displaystyle P_1,\ldots,P_N$ polinomok közül minden lehetséges módon $\displaystyle p^k-1$ darabot, ezeket szorozzuk össze, és legyen $\displaystyle f$ az így kapott, összesen $\displaystyle \binom{N}{p^k-1}$ szorzat összege:

$\displaystyle f(x_1,\dots,x_n) = \sum_{1\le i_1<\ldots<i_{p^k-1}\le N} P_{i_1}(x_1,\dots,x_n) \ldots P_{i_{p^k-1}}(x_1,\dots,x_n).$

Könnyen látható, hogy ez a polinom is eleget tesz $\displaystyle (*)$-nak.

2. megoldás (vázlat). Az $\displaystyle \mathcal{A}$ elemeit a $\displaystyle p^k$ többszöröseivel növelhetjük, ezért feltehetjük, hogy az $\displaystyle \mathcal{A}$ elemei (különböző) pozitív egészek. A megoldás során tetszőleges $\displaystyle H\subset\mathcal{A}$-ra $\displaystyle \Sigma H$ fogja jelölni a $\displaystyle H$ elemeinek összegét; tetszőleges $\displaystyle P(x)$ és $\displaystyle Q(x)$ egész együtthatós polinomokra $\displaystyle P(x)\equiv Q(x)\pmod{p}$ jelöli azt, hogy a $\displaystyle P(x)-Q(x)$ polinom minden együtthatója osztható $\displaystyle p$-vel; továbbá, tetszőleges $\displaystyle P(x)=c_0+c_1x+c_2x^2+\ldots$ polinom esetén legyen $\displaystyle S(P) = c_0+c_{p^k}+c_{2p^k}+\ldots$ a $\displaystyle p^k$-val osztható fokú tagok együtthatóinak összege $\displaystyle P(x)$-ben.

Tekíntsük a következő polinomot:

és vizsgáljuk az $\displaystyle S(F)$ összeget. A zárójeleket felbontva,

$\displaystyle F(x) = \sum_{H\subset\mathcal{A}} (-1)^{|H|} x^{\Sigma H},$

ezért

$\displaystyle S(F) = \sum_{\substack{H\subset\mathcal{A}\\ p^k|\Sigma H}} (-1)^{|H|} = N_{\text{páros}}-N_{\text{páratlan}}.$

A (2) jobboldalán $\displaystyle |\mathcal{A}|\ge p^k$ tényező szerepel, mindegyik osztható az $\displaystyle (1-x)$ polinommal, ezért $\displaystyle (1-x)^{p^k} \big| F(x)$, és így $\displaystyle F(x)=(1-x)^{p^k}\cdot G(x)$ egy alkalmas $\displaystyle G(x)$ egész együtthatós polinommal.

Vegyük észre, hogy

$\displaystyle (1-x)^{p^k} = \sum_{\ell=0}^{p^k} (-1)^\ell \binom{p^k}{\ell} x^\ell \equiv 1 + (-1)^{p^k} x^{p^k} \equiv 1-x^{p^k} \pmod{p},$

ugyanis $\displaystyle 0<\ell<p^k$ esetén a $\displaystyle \binom{p^k}{\ell}=\frac{p^k}{\ell}\cdot\binom{p^k-1}{\ell-1}$ binomiális együttható osztható $\displaystyle p$-vel. Így

$\displaystyle N_{\text{páros}}-N_{\text{páratlan}} = S(F) = S\Big( (1-x)^{p^k}\cdot G(x) \Big) \equiv$

$\displaystyle \equiv S\Big( (1 - x^{p^k}) G(x) \Big) = S\big(G(x)\big) - S\big(x^{p^k}G(x)\big) = 0 \pmod{p}.$

Glasznova Maja dolgozata és Nádor Péter KöMaL fórumon közzétett megoldása alapján

Statisztika:

7 dolgozat érkezett.
5 pontot kapott:	Bukva Balázs, Glasznova Maja, Williams Kada.
4 pontot kapott:	Baran Zsuzsanna.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2016. márciusi matematika feladatai