Az A. 670. feladat (2016. április)

A. 670. Legyen $\displaystyle a_1,a_2,\ldots$ nemnegatív egészekből álló sorozat, amelyre

$\displaystyle \sum_{i=1}^{2n} a_{id} \le n$

teljesül tetszőleges $\displaystyle (n,d)$ pozitív egész pár esetén. Bizonyítsuk be, hogy tetszőleges $\displaystyle K$ pozitív egész számhoz léteznek olyan $\displaystyle N$ és $\displaystyle D$ pozitív egészek, amelyekre

$\displaystyle \sum_{i=1}^{2N} a_{iD} = N-K.$

(Kínai feladat)

(5 pont)

A beküldési határidő 2016. május 10-én LEJÁRT.

Megoldás. Legyen minden $\displaystyle d\ge1$ és $\displaystyle n\ge0$ egész párra

$\displaystyle S(d,n) = \sum_{i=1}^{2n} a_{id}.$

A feltétel szerint $\displaystyle S(d,n)\le n$. A feltételt az $\displaystyle n=1$ esetre felírva látjuk, hogy $\displaystyle 0\le a_d\le a_d+a_{2d} = S(d,1) \le 1$; ebből következik, hogy az $\displaystyle (a_1,a_2,\ldots)$ sorozat minden eleme $\displaystyle 0$ vagy $\displaystyle 1$.

A megoldáshoz olyan $\displaystyle D,M$ pozitív egészeket fogunk keresni, amelyekre $\displaystyle S(D,M)\le M-K$. Gondoljuk meg, hogy az ilyenek létezéséből hogyan következik az állítás. Tekintsük a $\displaystyle h_n=n-S(D,n)$ sorozatot; ebben $\displaystyle h_0=0<K$ és $\displaystyle h_M=M-S(D,M)\ge K$; másrészt

$\displaystyle h_{n+1}-h_n = (n+1)-S(D,n+1)-(n-S(D,n)) = 1-a_{(2n+1)D}-a_{(2n+2)D} \in \{0,+1,-1\},$

vagyis a $\displaystyle (h_n)$ sorozat elemei mindig legfeljebb $\displaystyle 1$-gyel változnak. Ezért biztosan lesz olyan $\displaystyle 0<N\le M$ index is, amikor $\displaystyle h_N$ értéke pontosan $\displaystyle K$.

Most tegyük fel indirekte, hogy a kívánt $\displaystyle D,M$ értékek nem léteznek, tehát $\displaystyle S(d,n)>n-K$ bármely $\displaystyle d$ és $\displaystyle n$ esetén.

Tetszőleges pozitív egész $\displaystyle n$ és $\displaystyle m$ esetén adjuk össze az alábbi, $\displaystyle 2m \times 2n$ méretű táblázat elemeit:

$\displaystyle \begin{array}{|cccccccc|} \hline a_1 & a_{2} & a_{3} & a_{4} & \dots & a_{j} & \dots & a_{2n} \\ a_{2} & a_{4} & a_{6} & a_{8} & \dots & a_{2j} & \dots & a_{4n} \\ \vdots & \vdots & \vdots & \vdots &\ddots& \vdots &\ddots&\vdots \\ a_{i} & a_{2i} & a_{3i} & a_{4i} & \dots & a_{ij} & \dots & a_{2in} \\ \vdots & \vdots & \vdots & \vdots &\ddots& \vdots &\ddots&\vdots \\ a_{2m}& a_{4m} & a_{6m} & a_{8m} & \dots & a_{2mj}& \dots & a_{4mn} \\ \hline \end{array}$

A táblázat elemeit oszloponként és soronként is összeadva látjuk, hogy $\displaystyle \sum_{j=1}^{2n} S(j,m) = \sum_{i=1}^{2m} S(i,n)$, amiből

$\displaystyle \sum_{j=1}^{2n} \big(m - S(j,m)\big) = \sum_{i=1}^{2m} \big(n-S(i,n)\big) < 2m\cdot K.$

A baloldalon minden tag nemnegatív egész; ebből azt láthatjuk, hogy bármely rögzített $\displaystyle m$-hez csak véges sok, $\displaystyle 2mK$-nál kevesebb olyan kivételes $\displaystyle j$ index lehet, amikor $\displaystyle S(j,m)\ne m$. Az $\displaystyle m=1,2,3,4,5$ esetekhez ez összesen is csak véges sok kivételes index. Vegyünk most egy olyan $\displaystyle k_0$-t, ami az összes, $\displaystyle m\le 5$-höz tartozó kivételes indexnél nagyobb. Ekkor tehát $\displaystyle k\ge k_0$ és $\displaystyle m\le5$ esetén $\displaystyle S(k,m)=m$, így például

$\displaystyle a_{9k}+a_{10k} = S(k,5) - S(k,4) = 5 - 4 = 1;$

$\displaystyle a_{10k}+a_{12k} = S(2k,3) - S(2k,2) = 3 - 2 = 1;$

$\displaystyle a_{9k}+a_{12k} = S(3k,2) - S(3k,1) = 2 - 1 = 1.$

Ezek az egyenletek azt állítják, hogy a $\displaystyle (a_{9k},a_{10k},a_{12k})$ ciklusban felváltva következnek a $\displaystyle 0$-k és $\displaystyle 1$-esek. De ez nem lehetséges, mert a ciklus hossza páratlan.

(Williams Kada dolgozata alapján)

Megjegyzések. 1. A megoldást egy lépésbe is összesűríthetjük úgy, hogy a következő táblázat elemeit adjuk össze kétféleképpen:

$\displaystyle \begin{array}{|cccccccc|} \hline a_1 & a_2 & a_3 & a_4 & a_5 & \dots & a_k & \dots & a_{2n} \\ a_2 & a_4 & a_6 & a_8 & a_{10} & \dots & a_{2k} & \dots & a_{4n} \\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\ddots&\vdots \\ a_{10} & a_{20} & a_{30} & a_{40} & a_{50} & \dots & a_{10k} & \dots & a_{20n} \\ % \hline % 1,4 a_1 & a_2 & a_3 & a_4 & a_5 & \dots & a_k & \dots & a_{2n} \\ a_2 & a_4 & a_6 & a_8 & a_{10} & \dots & a_{2k} & \dots & a_{4n} \\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\ddots&\vdots \\ a_{8} & a_{16} & a_{24} & a_{32} & a_{40} & \dots & a_{8k} & \dots & a_{16n} \\ % \hline % 2,3 a_2 & a_4 & a_6 & a_{8} & a_{10} & \dots & a_{2k} & \dots & a_{4n} \\ a_{4} & a_{8} & a_{12} & a_{16} & a_{20} & \dots & a_{4k} & \dots & a_{8n} \\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\ddots&\vdots \\ a_{12} & a_{24} & a_{36} & a_{48} & a_{60} & \dots & a_{12k} & \dots & a_{24n} \\ % \hline % 2,2 a_2 & a_4 & a_6 & a_{8} & a_{10} & \dots & a_{2k} & \dots & a_{4n} \\ a_{4} & a_{8} & a_{12} & a_{16} & a_{20} & \dots & a_{4k} & \dots & a_{8n} \\ a_{6} & a_{12} & a_{18} & a_{24} & a_{30} & \dots & a_{6k} & \dots & a_{12n} \\ a_{8} & a_{16} & a_{24} & a_{32} & a_{40} & \dots & a_{8k} & \dots & a_{16n} \\ % \hline % 3,2 a_3 & a_6 & a_9 & a_{12} & a_{15} & \dots & a_{3k} & \dots & a_{6n} \\ a_{6} & a_{12} & a_{18} & a_{24} & a_{30} & \dots & a_{6k} & \dots & a_{12n} \\ a_{9} & a_{18} & a_{27} & a_{36} & a_{45} & \dots & a_{9k} & \dots & a_{18n} \\ a_{12} & a_{24} & a_{36} & a_{48} & a_{60} & \dots & a_{12k} & \dots & a_{24n} \\ % \hline % 3,1 a_3 & a_6 & a_9 & a_{12} & a_{15} & \dots & a_{3k} & \dots & a_{6n} \\ a_{6} & a_{12} & a_{18} & a_{24} & a_{30} & \dots & a_{6k} & \dots & a_{12n} \\ % \hline \end{array}$

A sorösszegek összege

$\displaystyle 2S(1,n) + 4S(2,n) + 4S(3,n) + 4S(4,n) + 2S(5,n) + 6S(6,n) + 2S(7,n) + 4S(8,n) +$

$\displaystyle + 2S(9,n) + 2S(10,n) + 2S(12,n) \ge 34 \cdot \min\big( S(1,n), S(2,n), \ldots, S(10,n), S(12,n) \big).$

A $\displaystyle k$-adik oszlopban álló összeg

$\displaystyle S(k,5)+S(k,4)+S(2k,3)+S(2k,2)+S(3k,2)+S(3k,1) =$

$\displaystyle = 2a_k +4a_{2k} +4a_{3k} +4a_{4k} +2a_{5k} +6a_{6k} +2a_{7k} +4a_{8k} +2a_{9k} +2a_{10k} +2a_{12k}$

páros szám, másrészt

$\displaystyle S(k,5)+S(k,4)+S(2k,3)+S(2k,2)+S(3k,2)+S(3k,1) \le 5+4+3+2+2+1=17,$

tehát mindegyik oszlopösszeg legfeljebb $\displaystyle 16$. A $\displaystyle k$ szerint összegezve azt kapjuk, hogy a táblázat összege legfeljebb $\displaystyle 32n$, így

$\displaystyle \min\big( S(1,n), S(2,n), \ldots, S(10,n), S(12,n) \big) \le \frac{16}{17} n.$

Ezek után $\displaystyle M=17K$-hoz biztosan létezik megfelelő $\displaystyle 1\le D\le 12$ és $\displaystyle 1\le N\le 17K$.

2. A feladat kapcsolódik az Erdős-féle diszkrepanciaproblémához, lásd pl. itt vagy itt.

Statisztika:

1 dolgozat érkezett.
5 pontot kapott:	Williams Kada.

A KöMaL 2016. áprilisi matematika feladatai