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