Feladat:	1999. évi Kürschák matematikaverseny 3. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2000/február, 70 - 71. oldal		PDF  |  MathML
Témakör(ök):	Természetes számok, Teljes indukció módszere, Számsorozatok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 2000/február: 1999. évi Kürschák matematikaverseny 3. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Az állítás nyilván igaz $k=0$ esetén. A bizonyítást teljes indukcióval fogjuk végezni. Legyen tehát $k\ge 1$, és tegyük fel, hogy $k$ helyett $\left(k-1\right)$-et írva az állítás már igazolást nyert. Jelöljön $a_1$, $a_2$, $\text{...}$, $a_{\ell }$ ($\ell >2^k$) különböző egész számokat. Meg kell mutatnunk, hogy kiválasztható közülük $k+2$ a feladatban megadott követelménynek megfelelően. Ezt pontosan akkor lehet megtenni, ha a $0=a_1-a_1$, $a_2-a_1$, $\text{...}$, $a_{\ell }-a_1$ számok közül kiválasztható $k+2$ a megfelelő módon. Feltehetjük tehát a továbbiakban, hogy a számok között szerepel a 0. Továbbá, ha az $a_1$, $a_2$, $\text{...}$, $a_{\ell }$ számok mindegyike osztható egy $q$ pozitív egész számmal, akkor elegendő az állítást $a_1$, $\text{...}$, $a_{\ell }$ helyett az $\frac{a_1}{q}$, $\text{...}$, $\frac{a_{\ell }}{q}$ számokra igazolni. Feltehetjük tehát, hogy a számok relatív prímek. Számaink között tehát szerepel páros és páratlan szám is. Vagy a páros vagy a páratlan számok száma nagyobb, mint $2^{k-1}$. Tegyük fel először, hogy több, mint $2^{k-1}$ páratlan számunk van. Ezekből az indukciós feltevés alapján kiválasztható $k+1$ a követelménynek megfelelően. Jelölje ezeket $b_1$, $\text{...}$, $b_{k+1}$, és legyen $c$ valamelyik páros szám az $a_1$, $\text{...}$, $a_{\ell }$ számok közül. Tegyük fel, hogy a $b_1$, $\text{...}$, $b_{k+1}$, $c$ számok között van $x_1<x_2<\text{...}<x_m$ és $y_1<y_2<\text{...}<y_m$ úgy, hogy $x_1+x_2+\text{...}+x_m=y_1+y_2+\text{...}+y_m$ teljesül. A $c$ szám az egyenlőség mindkét oldalán legfeljebb egyszer fordulhat elő. Ha az $x_1+x_2+\text{...}+x_m$ ugyanolyan maradékot ad 2-vel osztva, mint $m$, akkor szükségképpen az $x_i$ és $y_i$ számok is mind páratlanok, és az $x_1=y_1$, $\text{...}$, $x_m=y_m$ egyenlőségek következnek az indukciós feltevésben a $b_1$, $b_2$, $\text{...}$, $b_{k+1}$ számokra kirótt feltételből. Ellenkező esetben a $c$ szám az egyenlőség mindkét oldalán szerepel, azt mindkét oldalról elhagyva meggyőződhetünk arról, hogy a fennmaradó számok páronként egyenlők. Hasonló módon okoskodhatunk akkor is, ha az $a_1$, $\text{...}$, $a_{\ell }$ számok között a páros számokból van több, mint $2^{k-1}$.   II. megoldás. Feltehetjük, hogy a szóban forgó számok mindegyike pozitív, ezt ugyanis elérhetjük, ha mindegyik számot megnöveljük ugyanazzal az elegendően nagy pozitív egész számmal. Ha az újonnan kapott számokra teljesül az állítás, akkor az eredeti számokra is teljesülnie kell. Írjuk fel most a számokat kettes számrendszerben, és tekintsük azt a legkisebb helyiértéket, ahol valamely két szám különbözik. Jelölje ezt a helyet $i_1$. Az összes szám megegyezik tehát az utolsó $i_1-1$ helyen, az $i_1$-edik helyen azonban bizonyos számokban 0 áll, a többiben pedig 1. Legyen $b_1$ egyike azon számoknak, amelyekből kevesebb van; ha ugyanannyi van a két különböző típusból, akkor egy olyat válasszunk ki, amelynek (hátulról számítva) az $i_1$-edik jegye 1. Tekintsük a továbbiakban csak azokat a számokat, amelyek különböznek $b_1$-től az $i_1$-edik helyen. $b_1$ kiválasztása miatt ezek száma nagyobb, mint $2^{k-1}$, és utolsó $i_1$ jegyük rendre megegyezik. Jelölje $i_2$ azt a legkisebb helyiértéket, ahol valamelyik két szám eltér, $i_2>i_1$. Különböztessük meg a számokat aszerint, hogy az $i_2$-edik helyen milyen számjegy áll bennük, és válasszuk $b_2$-t azok közül, amelyek kevesebben vannak, a másik csoport számmal (amelyekből több, mint $2^{k-2}$ van) pedig folytassuk ezt az eljárást. Ily módon olyan $i_1<i_2<\text{...}<i_{k+1}$ helyiértékeket és $b_1$, $b_2$, $\text{...}$, $b_{k+1}$ számokat találunk, amelyekre igaz minden $j=1$, 2, $\text{...}$, $k$ esetén, hogy $b_j$, $b_{j+1}$, $\text{...}$, $b_{k+1}$ utolsó $i_j-1$ jegye megegyezik, de $b_j$ $i_j$-edik jegye különbözik $b_{j+1}$, $\text{...}$, $b_{k+1}$ $i_j$-edik jegyétől. Sőt, egy $b_{k+2}$ szám is található, amelynek utolsó $i_{k+1}-1$ jegye $b_{k+1}$-ével megegyezik, de az $i_{k+1}$-edik helyen a két szám eltér egymástól. Tegyük fel most, hogy a $b_1$, $b_2$, $\text{...}$, $b_{k+2}$ számok között van $x_1<x_2<\text{...}<x_m$ és $y_1<y_2<\text{...}<y_m$ úgy, hogy $x_1+x_2+\text{...}+x_m=y_1+y_2+\text{...}+y_m=S$ teljesül. Az $x_1$, $x_2$, $\text{...}$, $x_m$, $y_1$, $y_2$, $\text{...}$, $y_m$ számok utolsó $i_1-1$ jegyéből álló szám mind megegyező, jelöljük ezt $u_1$-gyel. Az $S-m\cdot u_1$ szám utolsó $i_1-1$ jegye tehát 0, és az $i_1$-edik jegyet megvizsgálva eldönthető, hogy az $x_1$, $\text{...}$, $x_m$ (és ugyanígy az $y_1$, $\text{...}$, $y_m$) számok között szerepel-e a $b_1$. Ha nem, akkor áttérünk az utolsó $i_2$ hely vizsgálatára. Ha igen, akkor mindkét oldalról töröljük a $b_1$ összeadandót, és úgy térünk át az utolsó $i_2$ jegy vizsgálatára. Ilyen módon a $b_1$, $b_2$, $\text{...}$, $b_{k+1}$ számokról sorra eldönthetjük, hogy szerepelnek-e az összegben: ha igen, akkor mind a két oldalon szerepelniük kell. Ezeket sorra elhagyva az egyenlőség mindkét oldaláról végül vagy a $0=0$ egyenlőséghez jutunk, vagy mindkét oldalon egy-egy szám marad, amely kizárólag $b_{k+2}$-vel lehet egyenlő.   Megjegyzések. 1. Mindkét bizonyítás egy algoritmust is szolgáltat a keresett $k+2$ szám kiválasztására, méghozzá lényegében ugyanazt az algoritmust. 2. Kézenfekvő kérdés, hogy $2^k$ helyettesíthető-e valamely, annál kisebb számmal. Terpai Tamás észrevette, hogy van olyan pozitív $c$ konstans, hogy $c\cdot \frac{2^k}{k^{3/2}}$ mellett az állítás már nem igaz. Ha ugyanis az első $n$ számból ki lehet választani $k+2$ számot a kívánt feltétel mellett, akkor szükségképpen $\ell =\lfloor \frac{k+2}{2}\rfloor$ esetén a számokból alkotott $\left(\genfrac{}{}{0ex}{}{k+2}{\ell }\right)\approx 4\sqrt[]{\frac{2}{\pi }}\frac{2^k}{\sqrt[]{k}}$ $\ell$-tagú összeg mind különböző, márpedig ezek egyike sem lehet nagyobb, mint $n\ell \approx \frac{nk}{2}$.