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