Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5269. feladat (2022. október)

B. 5269. Legyen \(\displaystyle p \ge 19\) egy páratlan szám. Színezzük ki a \(\displaystyle 0,1,\dots,p-1\) számokat két színnel. Legyen \(\displaystyle 1\le i\le p\) esetén \(\displaystyle x_i\) a \(\displaystyle \{0,1,\dots,p-1\}\) halmaz egy véletlenszerűen választott eleme (egyenletes eloszlás szerint, egymástól függetlenek a választások). Igazoljuk, hogy legalább \(\displaystyle 3/(2^pp)\) annak a valószínűsége, hogy \(\displaystyle x_1,\dots,x_p\) egyforma színűek és \(\displaystyle p \mid x_1+\ldots + x_p\).

Javasolta: Pach Péter Pál (Budapest)

(6 pont)

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


1. megoldás. Számoljuk meg, hogy az \(\displaystyle x_i\) számok összes lehetséges kiválasztása közül hány esetben teljesül, hogy \(\displaystyle x_1,\dots,x_p\) egyforma színűek és \(\displaystyle p\mid x_1+\dots + x_p\). A két szín legyen piros és kék. A \(\displaystyle \{0,1,\dots,p-1\}\) pirosra színezett elemeinek halmaza legyen \(\displaystyle P\), a kékre színezetteké pedig \(\displaystyle K\).

Legyen \(\displaystyle 0\leq i\leq p-1\) esetén \(\displaystyle f(i)=1\), ha \(\displaystyle i\in P\) és \(\displaystyle f(i)=0\), ha \(\displaystyle i\in K\). Az \(\displaystyle x_1,\dots,x_p\) számok színe pontosan akkor egyforma, ha \(\displaystyle f(x_1)=\dots=f(x_p)=1\) (ekkor pirosak) vagy \(\displaystyle f(x_1)=\dots=f(x_p)=0\) (ekkor kékek). Így az egyszínű megoldások számát a következő összeg adja meg:

\(\displaystyle \sum\limits_{\substack{x_1,\dots,x_p\in \{0,1,\dots,p-1\} \\ p\mid x_1+x_2+\dots+ x_p} } \left(f(x_1)f(x_2)\dots f(x_p) + (1-f(x_1))(1-f(x_2))\dots(1-f(x_p))\right).\)

Az összegzendő kifejezésben a zárójeleket felbontva \(\displaystyle (-1)^k f(x_{i_1})f(x_{i_2})\dots f(x_{i_k})\) alakú szorzatokat kapunk, ahol \(\displaystyle 0\leq k<p\) és \(\displaystyle 1\leq i_1<i_2<\dots<i_k\leq n\), hiszen \(\displaystyle x_1x_2\dots x_p\) kiesik. (A \(\displaystyle k=0\) esetben a szorzat — vagyis az üres szorzat — az 1.) Számoljuk ki tehát a

\(\displaystyle \sum\limits_{\substack{x_1,\dots,x_p\in \{0,1,\dots,p-1\} \\ p\mid x_1+x_2+\dots +x_p} } (-1)^k f(x_{i_1})f(x_{i_2})\dots f(x_{i_k})\)

összeget. Az \(\displaystyle f(x_{i_1})f(x_{i_2})\dots f(x_{i_k})\) szorzat értéke mindig 0 vagy 1, és pontosan akkor 1, ha \(\displaystyle x_{i_1},\dots,x_{i_k}\in P\). Így az \(\displaystyle \{1,2,\dots,p\}\setminus \{i_1,i_2,\dots,i_k\}=\{j_1,j_2,\dots,j_{p-k}\}\) jelölést bevezetve

\(\displaystyle \sum\limits_{\substack{x_1,\dots,x_p\in \{0,1,\dots,p-1\} \\ p\mid x_1+x_2+\dots+ x_p} } (-1)^k f(x_{i_1})f(x_{i_2})\dots f(x_{i_k})=(-1)^k \sum\limits_{x_{i_1},\dots,x_{i_k}\in P}\sum\limits_{\substack{x_{j_1},\dots,x_{j_{p-k}}\in \{0,1,\dots,p-1\} \\ p\mid x_1+x_2+\dots +x_p}}1.\)

Rögzített \(\displaystyle i_1,\dots,i_k\) mellett a \(\displaystyle j_1,\dots,j_{p-k}\in \{0,1,\dots,p-1\}\) értékek közül \(\displaystyle p-k-1 \)-et tetszőlegesen választva az utolsó pontosan egyféleképpen választható úgy, hogy \(\displaystyle p\mid x_1+x_2+\dots+x_p\) teljesüljön. Tehát a második összeg értéke mindig \(\displaystyle p^{n-k-1}\) rögzített \(\displaystyle i_1,\dots,i_k\) mellett. Mivel \(\displaystyle x_{i_1},\dots,x_{i_k}\in P\) megválasztása \(\displaystyle |P|^k\)-féleképpen történhet, ezért

\(\displaystyle \sum\limits_{\substack{x_1,\dots,x_p\in \{0,1,\dots,p-1\} \\ p\mid x_1+x_2+\dots+ x_p} } (-1)^k f(x_{i_1})f(x_{i_2})\dots f(x_{i_k})=(-1)^k|P|^kp^{n-k-1}.\)

Mivel \(\displaystyle 1\leq i_1<i_2<\dots<i_k\leq p\) megválasztására \(\displaystyle \binom{p}{k}\) lehetőség van, ezért

$$\begin{multline*} \sum\limits_{\substack{x_1,\dots,x_p\in \{0,1,\dots,p-1\} \\ p\mid x_1+x_2+\dots +x_p} } \left(f(x_1)f(x_2)\dots f(x_p) + (1-f(x_1))(1-f(x_2))\dots(1-f(x_p))\right)=\\ = \sum\limits_{k=0}^{p-1} \binom{p}{k} (-1)^k|P|^kp^{p-k-1}=\frac{(p-|P|)^p+|P|^p}{p} , \end{multline*}$$

a binomiális tétel szerint. (Ugyanis \(\displaystyle (p-|P|)^p=\sum\limits_{k=0}^{p} \binom{p}{k} (-1)^k|P|^kp^{p-k}=-|P|^p+\sum\limits_{k=0}^{p-1} \binom{p}{k} (-1)^k|P|^kp^{p-k}\).) Tehát annak a valószínűsége, hogy \(\displaystyle x_1,\dots,x_p\) egyforma színűek és \(\displaystyle p\mid x_1+\dots+x_p\):

\(\displaystyle \frac{(p-|P|)^p+|P|^p}{p^{p+1}}.\)

Mivel az \(\displaystyle x^p\) függvény konvex a \(\displaystyle [0,p]\) intervallumon, ezért ez akkor minimális, ha \(\displaystyle |P|\) és \(\displaystyle p-|P|\) eltérése minimális, vagyis, ha \(\displaystyle |P|=\frac{p-1}{2}\) vagy \(\displaystyle |P|=\frac{p+1}{2}\). Ekkor

\(\displaystyle \frac{(p-|P|)^p+|P|^p}{p^{p+1}}=\frac{\left(\frac{p-1}{2}\right)^p+\left(\frac{p+1}{2}\right)^p}{p^{p+1}}=\frac{1}{2^pp}\left[\left(1-\frac1p\right)^p+\left(1+\frac1p\right)^p\right].\)

A feladat megoldásához elég igazolni, hogy \(\displaystyle \left(1-\frac1p\right)^p+\left(1+\frac1p\right)^p\geq 3\), ha \(\displaystyle p\geq 19\). Ismert, hogy az \(\displaystyle \left(1-\frac1p\right)^p\), illetve az \(\displaystyle \left(1+\frac1p\right)^p\) függvények monoton növekedőek (és határértékük \(\displaystyle e^{-1}\), illetve \(\displaystyle e\)), így az egyenlőtlenség ellenőrizhető úgy, hogy kiszámoljuk az összeg értékét \(\displaystyle p=19\)-re:

\(\displaystyle \left(1-\frac1p\right)^p+\left(1+\frac1p\right)^p\geq \left(1-\frac{1}{19}\right)^{19}+\left(1+\frac{1}{19}\right)^{19}\geq 3,008\geq 3,\)

vagyis az igazolandó egyenlőtlenség valóban teljesül. Ezzel a feladat állítását igazoltuk.

Megjegyzés. A megoldásból az is leolvasható, hogy 3 helyett \(\displaystyle e+e^{-1}\approx 3.09\)-et írva az állítás már nem teljesül (elegendően nagy \(\displaystyle p\) esetén sem). Ha ugyanis \(\displaystyle (p-1)/2\) pirosra és \(\displaystyle (p+1)/2\) kékre színezett elem van, akkor a kérdéses valószínűség kisebb, mint \(\displaystyle (e+e^{-1})/(2^pp)\).

2. megoldás. Legyen ismét \(\displaystyle P\) a piros, \(\displaystyle K\) pedig a kék számok száma, ekkor tehát \(\displaystyle P+K=p\). Bármely \(\displaystyle 0\le k\le p\) esetén legyen \(\displaystyle N_k\) az olyan \(\displaystyle x_1,\ldots,x_p\) sorozatok száma, amelyek összege osztható \(\displaystyle p\)-vel, \(\displaystyle x_1\ldots, x_k\) mind piros, \(\displaystyle x_{k+1},\ldots,x_p\) pedig mind kék. (Ha \(\displaystyle k=0\), akkor a feltétel az, hogy \(\displaystyle x_1,\ldots,x_p\) kék, a \(\displaystyle k=p\) esetben pedig mind piros.) A feladat megoldásához az \(\displaystyle N_0+N_p\) értékét kell alulról becsülnünk.

Először azt állítjuk, hogy bármely \(\displaystyle 1\le k\le p\) esetén

\(\displaystyle N_{k-1}+N_k = P^{k-1}N^{p-k}. \)\(\displaystyle (1) \)

Számoljuk össze kétféleképpen az \(\displaystyle x_1,\ldots,x_p\) sorozatok száma, amelyek összege osztható \(\displaystyle p\)-vel, \(\displaystyle x_1\ldots, x_{k-1}\) mind piros, \(\displaystyle x_{k+1},\ldots,x_p\) mind kék, az \(\displaystyle x_k\) pedig tetszőeges színű.

Az ilyen sorozatokat \(\displaystyle x_k\) színe szerint két halmazra bonthatjuk. Ha \(\displaystyle x_k\) színe kék, akkor \(\displaystyle x_1,\ldots,x_{k-1}\) piros és \(\displaystyle x_k,\ldots,x_p\) kék; ilyenből pontosan \(\displaystyle N_{k-1}\) darab van. Ha pedig \(\displaystyle x_k\) színe piros, akkor \(\displaystyle x_1,\ldots,x_k\) piros és \(\displaystyle x_{k+1},\ldots,x_p\) kék; ilyenből pontosan \(\displaystyle N_k\) darab van. Ez összesen \(\displaystyle N_{k-1}+N_k\) sorozat.

Másfelől, a piros színű \(\displaystyle x_1,\ldots,x_{k-1}\) számokat \(\displaystyle P^{k-1}\)-féleképpen választhatjuk, a kék színű \(\displaystyle x_{k+1},\ldots,x_p\) számokat pedig \(\displaystyle K^{n-k}\)-féleképpen; minden ilyen választáshoz pontosan egyféle \(\displaystyle x_k\) létezik, amelyre \(\displaystyle p|x_1+\ldots+x_p\) is teljesül.

Az (1) azonosságból ki tudjuk fejezni \(\displaystyle N_0+N_p\) értékét: mivel \(\displaystyle p\) páratlan,

$$\begin{align*} N_0+N_p &= (N_0+N_1)-(N_1+N_2)+(N_2+N_3)-+\ldots-(N_{p-2}+N_{p-1})-(N_{p-1}+N_p) \\ &= P^0K^{p-1}-P^1K^{p-2}+P^2K^{p-3}-+\ldots-P^{p-2}K+K^{p-1}. \end{align*}$$

Tekintettel az \(\displaystyle x^p+y^p=(x+y)(x^{p-1}-x^{p-2}y+x^{p-3}y^2-+\ldots+y^{p-1})\) azonosságra, célszerű ezt \(\displaystyle p=(P+K)\)-val is megszorozni:

\(\displaystyle p(N_0+N_p) = (P+K)(P^0K^{p-1}-P^1K^{p-2}+-\ldots+K^{p-1}) = P^p+K^p. \)

A keresett valószínűség tehát

\(\displaystyle \frac{N_0+N_p}{p^p} = \frac{P^p+K^p}{p^{p+1}}. \)

A befejezés innen ugyanaz, mint az első megoldásban.

Kapocsolódó feladatok: A. 448., B. 4722.


Statisztika:

21 dolgozat érkezett.
6 pontot kapott:Tarján Bernát, Varga Boldizsár, Wiener Anna.
2 pontot kapott:2 versenyző.
1 pontot kapott:1 versenyző.
0 pontot kapott:14 versenyző.

A KöMaL 2022. októberi matematika feladatai