Problem B. 5269. (October 2022)

B. 5269. Let $\displaystyle p \ge 19$ be an odd integer, and color the numbers $\displaystyle 0,1,\dots,p-1$ with two colors. For $\displaystyle 1\le i\le p$, let $\displaystyle x_i$ denote a random element of the set $\displaystyle \{0,1,\dots,p-1\}$ (the choices are independent, and have uniform distribution). Prove that the probability of the event that $\displaystyle x_1,\dots,x_p$ have the same color and $\displaystyle p$ divides $\displaystyle x_1+\cdots + x_p$ is at least $\displaystyle 3/(2^pp)$.

Proposed by Péter Pál Pach, Budapest

(6 pont)

Deadline expired on November 10, 2022.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

21 students sent a solution.

6 points: Tarján Bernát, Varga Boldizsár, Wiener Anna.

2 points: 2 students.

1 point: 1 student.

0 point: 14 students.

Problems in Mathematics of KöMaL, October 2022

21 students sent a solution.
6 points:	Tarján Bernát, Varga Boldizsár, Wiener Anna.
2 points:	2 students.
1 point:	1 student.
0 point:	14 students.

Already signed up?
New to KöMaL?