Feladat:	2000. évi Kürschák matematikaverseny 3. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Csikvári Péter ,  Kovács Erika Renáta ,  Nagy Zoltán ,  Zábrádi Gergely
Füzet:	2001/február, 73 - 77. oldal		PDF  |  MathML
Témakör(ök):	Oszthatósági feladatok, Maradékosztályok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 2001/február: 2000. é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 általánosság megszorítása nélkül feltehető, hogy az $a_1$, $a_2$, $\text{...}$, $a_{2k}$ számok páronként különböző maradékot adnak $\left(n+k\right)$-val osztva. Tekintsük a következő $n+k$ különböző számot: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle b_1}& {\displaystyle =a_1\mathrm{,}{b}_2=a_1\mathrm{,}{b}_3=a_1+a_2}\hfill \\ \hfill {\displaystyle b_{3i+1}}& {\displaystyle =a_1+a_2+\text{...}+a_{2i}+a_{2i+1}}\hfill & \hfill {\displaystyle \text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo fence="true" stretchy="true">(</mo><mrow><mn>0</mn><mo stretchy="false"><</mo><mi>i</mi><mo stretchy="false"><</mo><mi>k</mi></mrow><mo fence="true" stretchy="true">)</mo></mrow></math>, }}\\ \hfill {\displaystyle b_{3i+2}}& {\displaystyle =a_1+a_2+\text{...}+a_{2i}+a_{2i+2}}\hfill & \hfill {\displaystyle \text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo fence="true" stretchy="true">(</mo><mrow><mn>0</mn><mo stretchy="false"><</mo><mi>i</mi><mo stretchy="false"><</mo><mi>k</mi></mrow><mo fence="true" stretchy="true">)</mo></mrow></math>, }}\\ \hfill {\displaystyle b_{3i+3}}& {\displaystyle =a_1+a_2+\text{...}+a_{2i}+a_{2i+1}+a_{2i+2}}\hfill & \hfill {\displaystyle \text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo fence="true" stretchy="true">(</mo><mrow><mn>0</mn><mo stretchy="false"><</mo><mi>i</mi><mo stretchy="false"><</mo><mi>k</mi></mrow><mo fence="true" stretchy="true">)</mo></mrow></math>, }}\\ \hfill {\displaystyle b_j}& {\displaystyle =a_1+a_2+\text{...}+a_{j-k}}\hfill & \hfill {\displaystyle \text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo fence="true" stretchy="true">(</mo><mrow><mn>3</mn><mi>k</mi><mo stretchy="false"><</mo><mi>j</mi><mo>≤</mo><mi>n</mi><mo stretchy="false">+</mo><mi>k</mi></mrow><mo fence="true" stretchy="true">)</mo></mrow></math>. }}\end{array}}}\end{array}$ Ha ezek között van olyan, amelyik osztható $\left(n+k\right)$-val, akkor mar készen is vagyunk. Ellenkező esetben pedig van a számok között kettő, mondjuk $b_s$ és $b_t$ ($s<t$) amelyik ugyanolyan maradékot ad $\left(n+k\right)$-val osztva. Ekkor $b_t-b_s$ nyilván osztható $\left(n+k\right)$-val. Azt kell már csak észrevennünk, hogy ez a különbség felírható az $a_1$, $a_2$, $\text{...}$, $a_n$ számok közül néhánynak az összegeként. Ha ugyanis ez nem így lenne, akkor valamilyen $k$-nál kisebb $i$-re $s=3i+1$ és $t=3i+2$, vagyis $b_t-b_s=a_{2i+2}-a_{2i+1}$ volna. Ez azonban feltételezésünk értelmében nem osztható $\left(n+k\right)$-val.   II. megoldás. Ugyanehhez a végeredményhez egy kissé eltérő kiindulással is eljuthatunk. Állítás. Tetszőleges $b_1$, $b_2$, $\text{...}$, $b_N$ egész számok esetén léteznek olyan $1\le i\le j\le N$ indexek, hogy a $b_i+b_{i+1}+\text{...}+b_j$ összeg osztható $N$-nel. Ez egyébként éppen a feladat állítása a $k=0$ esetben. A bizonyításhoz tekintsük $t=0$, $1$, $\text{...}$, $N$ esetén az $s_t=b_1+\text{...}+b_t$ összegeket, ahol $s_0=0$ az üres összeg. Az így felírt $N+1$ egész szám között biztosan van kettő, amelyik ugyanolyan maradékot ad $N$-nel osztva. Ha $s_k$ és $s_{\ell }$ ($0\le k<\ell \le N$) két ilyen összeg, akkor $s_{\ell }-s_k=b_{k+1}+b_{k+2}+\text{...}+b_{\ell }$ osztható $N$-nel. A feladatot ezután a következő módon vezethetjük vissza erre a speciális esetre. Az első megoldáshoz hasonlóan, most is feltehetjük, hogy az $a_1$, $a_2$, $\text{...}$, $a_{2k}$ számok páronként különböző maradékot adnak $\left(n+k\right)$-val osztva. Tekintsük a $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle b_1=a_1\mathrm{,}{b}_2=a_2-a_1\mathrm{,}{b}_3=a_1\mathrm{,}{b}_4=a_3\mathrm{,}{b}_5=a_4-a_3\mathrm{,}{b}_6=a_3\mathrm{,}\text{...}\mathrm{,}{b}_{3k}=a_{2k-1}\mathrm{,}}\\ \hfill {\displaystyle b_{3k+1}=a_{2k+1}\mathrm{,}{b}_{3k+2}=a_{2k+2}\mathrm{,}\text{...}\mathrm{,}{b}_{n+k}=a_n}\end{array}}}\end{array}$ számokat. Így éppen $N=n+k$ egész számot írtunk fel. A fenti állítás értelmében léteznek olyan $1\le i\le j\le N$ indexek, hogy $S=b_i+b_{i+1}+\text{...}+b_j$ osztható $N$-nel. Elegendő azt megmutatni, hogy $S$ felírható az $a_1$, $a_2$, $\text{...}$, $a_n$ számok közül néhánynak az összegeként. Ez egészen nyilvánvaló akkor, ha $i\ge 3k+1$, ebben az esetben ugyanis $\begin{array}{c}{\displaystyle S=a_{i-k}+a_{i-k+1}+\text{...}+a_{j-k}\mathrm{.}}\end{array}$ Ha $i\le 3k<j$, akkor legyen $i=3s+q$, ahol $0\le s<k$ és $1\le q\le 3$. Ekkor nyilván $\begin{array}{c}{\displaystyle S=A+a_{2s+3}+a_{2s+4}+\text{...}+a_{j-k}\mathrm{,}}\end{array}$ ahol $A=a_{2s+1}+a_{2s+2}$, $a_{2s+2}$, vagy $a_{2s+1}$ annak megfelelően, hogy $q$ értéke 1, 2, vagy pedig 3. Végül $j\le 3k$ esetén legyen $i=3s+q$, $j=3t+r$, ahol $0\le s\le t<k$ és $1\le q\mathrm{,}r\le 3$. Ekkor könnyen ellenőrizhető, hogy $\begin{array}{c}{\displaystyle S=A+a_{2s+3}+a_{2s+4}+\text{...}+a_{2t}+B\mathrm{,}}\end{array}$ ahol $A$-t ugyanúgy definiáljuk, mint az előző esetben, $B$ értéke pedig $a_{2t+1}$, $a_{2t+2}$, vagy pedig e kettő összege aszerint, hogy $r=1$, $2$, vagy $3$, feltéve, hogy $s\ne t$. Ha $s=t$, akkor is könnyen látható, hogy $S$ értéke $a_{2s+1}+a_{2s+2}$, $a_{2s+2}$, vagy $a_{2s+1}$. Kivételt képezne az az egyetlen esetet, amikor $s=t$ és $q=r=2$. Ez azonban nem fordulhat elő, hiszen ekkor $S=a_{2s+2}-a_{2s+1}$ lenne, az $a_1$, $a_2$, $\text{...}$, $a_{2k}$ számok közül viszont semelyik kettő különbsége nem osztható $N$-nel.   III. megoldás. (Kovács Erika Renáta megoldása.) Ismét tegyük fel, hogy az $a_1$, $\text{...}$, $a_{2k}$ számok páronként különböző maradékot adnak $\left(n+k\right)$-val osztva. Vezessük be az $A=\left\{a_1\mathrm{,}{a}_2\mathrm{,}\text{...}\mathrm{,}{a}_{2k}\right\}$ jelölést, és legyen $b_1=a_1$. Ha valamilyen $1<j\le k+1$ esetén a $b_1$, $b_2$, $\text{...}$, $b_{j-1}$ számokat már definiáltuk, akkor legyen $b_j$ az $A$ halmaznak egy olyan eleme, amelyik a $b_1$, $b_2$, $\text{...}$, $b_{j-1}$, $b_1+b_2$, $b_1+b_2+b_3$, $\text{...}$, $b_1+b_2+\text{...}+b_{j-1}$ számok egyikével sem ad azonos maradékot $\left(n+k\right)$-val osztva. Ilyen szám valóban létezik, hiszen ezekkel a feltételekkel az $A$ halmaznak legfeljebb $\left(j-1\right)+\left(j-2\right)<2k$ elemét zártuk ki. Jelölje $b_{k+2}$, $b_{k+3}$, $\text{...}$, $b_{2k}$ az $A$ halmaz fennmaradó elemeit valamilyen sorrendben, és tekintsük a következő $n+k$ számot: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{ccc}\hfill {\displaystyle s_i}& {\displaystyle =b_1+b_2+\text{...}+b_i}\hfill & \hfill {\displaystyle \left(1\le i\le 2k\right)\mathrm{,}}\\ \hfill {\displaystyle s_j}& {\displaystyle =a_1+a_2+\text{...}+a_j}\hfill & \hfill {\displaystyle \left(2k<i\le n\right)\mathrm{,}}\\ \hfill {\displaystyle s_{n+1}}& {\displaystyle =b_2\mathrm{,}{s}_{n+2}=b_3\mathrm{,}\text{...}\mathrm{,}{s}_{n+k}=b_{k+1}\mathrm{.}}\hfill \end{array}}}\end{array}$ Ha ezek közül valamelyik osztható $\left(n+k\right)$-val, akkor készen is vagyunk, ellenkező esetben viszont közülük kettő azonos maradékot ad $\left(n+k\right)$-val osztva, ezek különbsége tehát ismét csak osztható $\left(n+k\right)$-val. Az nyilván nem lehetséges hogy mindkét szám az utolsó $k$ darab közül kerüljön ki, hiszen ezek páronként különböző maradékkal rendelkeznek. Ha mindkét szám az első $n$ szám között van, akkor különbségük éppen az $a_i$ számok közül néhánynak az összege, ebben az esetben tehát megint csak célhoz értünk. Végül, ha a két szám közül az egyik $s_i$, ahol $1\le i\le n$, a másik pedig $s_{n+j}$, $1\le j\le k$, akkor a $b_i$ számok megválasztása miatt $i>j$ kell, hogy teljesüljön. Ekkor azonban $s_{n+j}=b_{j+1}$ éppen az $s_i$ egyik összeadandója, következésképpen az $\left(n+k\right)$-val osztható $s_i-s_{n+j}$ szám most is felírható az $a_i$ számok közül néhánynak az összegeként.   IV. megoldás. (Zábrádi Gergely ötlete.) Most egy indukciós bizonyítást mutatunk. Pontosabban az alábbi erősebb állítást fogjuk teljes indukcióval igazolni. Állítás. Legyenek $m$, $n$ pozitív egész számok. Ha az $a_1$, $a_2$, $\text{...}$, $a_n$ egész számok legalább $2i$ különböző maradékot adnak $m$-mel osztva, akkor vagy van közöttük néhány, amelyek összege osztható $m$-mel, vagy képezhető belőlük legalább $n+i$ olyan összeg, amelyek páronként különböző maradékot adnak $m$-mel osztva. Ebből az állításból $m=n+k$, $i=k$ választással az eredeti feladat megoldása azonnal leolvasható. Ha $i=0$, akkor egyszerűen tekintjük az $a_1$, $a_1+a_2$, $\text{...}$, $a_1+a_2+\text{...}+a_n$ összegeket; ha ezek között van két olyan, amelyik azonos maradékot ad $m$-mel osztva, akkor különbségük, ami szintén néhány $a_i$ összege, osztható $m$-mel. Tegyük fel most egy pillanatra, hogy $i=1$ esetén is igazoltuk már az állítást. Az indukciós lépéshez legyen $j\ge 1$ és tegyük fel azt is, hogy az állítás igazolást nyert már $i=j$ esetén is. Ebből $i=\left(j+1\right)$-re a következőképpen kaphatjuk meg az állítást. Legyenek $a_1$, $a_2$, $\text{...}$, $a_n$ olyan egész számok, amelyek legalább $2j+2$ különböző maradékot adnak $m$-mel osztva. Válasszunk ki közülük két különböző maradékot adót, és tekintsük az összes olyan $a_i$-t, amelyik ezek valamelyikével kongruens modulo $m$. Az általánosság megszorítása nélkül feltehetjük, hogy ezek éppen az $a_{t+1}$, $a_{t+2}$, $\text{...}$, $a_n$ számok. Az $a_1$, $a_2$, $\text{...}$, $a_t$ számokról tudjuk azt, hogy legalább $2j$ különböző maradékot adnak $m$-mel osztva. Tegyük fel, hogy az $a_i$ számokból nem képezhető $m$-mel osztható összeg. Ekkor az indukciós feltevés és az $i=1$ esetre vonatkozó feltevés értelmében az $a_1$, $a_2$, $\text{...}$, $a_t$ számokból képezhető $t+j$ különböző maradékot adó összeg, az $a_{t+1}$, $a_{t+2}$, $\text{...}$, $a_n$ számokból pedig képezhető $n-t+1$ különböző maradékot adó összeg. Jelölje ezeket rendre $s_1$, $s_2$, $\text{...}$, $s_{t+j}$, illetve $r_1$, $r_2$, $\text{...}$, $r_{n-t+1}$. Minden további nélkül feltehető az is, hogy $s_1=a_1+a_2+\text{...}+a_t$. Tekintsük most a következő $n+j+1$ számot: $s_1$, $s_2$, $\text{...}$, $s_{t+j}$, $s_1+r_1$, $s_1+r_2$, $\text{...}$, $s_1+r_{n-t+1}$, ezek bármelyike felírható az $a_i$ számok közül néhánynak az összegeként. Tudjuk, hogy az első $t+j$ szám páronként inkongruens modulo $m$, és hasonlóképpen az utolsó $n-t+1$ is az. Az sem lehet, hogy valamelyik $s_b$ ugyanolyan maradékot ad $m$-mel osztva, mint $s_1+r_c$, hiszen különbségük, $\left(s_1-s_b\right)+r_c$ jól láthatóan néhány $a_i$ összege. A felsorolt $n+j+1$ szám tehát páronként inkongruens modulo $m$, és éppen ezt akartuk megmutatni. Annyi van már csak hátra, hogy a fent kimondott állítást $i=1$ esetén is igazoljuk. Tegyük fel tehát, hogy az $a_1$, $a_2$, $\text{...}$, $a_n$ számok közül $a_1$ és $a_2$ különböző maradékot adnak $m$-mel osztva. Ha az $a_1\mathrm{,}{a}_2\mathrm{,}{a}_1+a_2\mathrm{,}{a}_1+a_2+a_3\mathrm{,}\text{...}\mathrm{,}{a}_1+a_2+\text{...}+a_n$ számok között van kettő, ami ugyanazt a maradékot adja, akkor különbségük, ami nem más, mint néhány $a_i$ összege, osztható lesz $m$-mel. Ellenkező esetben pedig máris találtunk $n+1$ olyan összeget, ami mind különböző maradékot ad $m$-mel osztva.   Megjegyzések. 1. Ahogy azt Gyenes Zoltán és Kiss Gergely is megjegyzik, az első megoldásból (és az azzal lényegében megegyező másodikból is) világosan látszik, hogy nem kell megkövetelnünk $2k$ különböző maradék létezését: elegendő, ha az $a_i$ számokból kiválasztható $k$ olyan pár, hogy az azonos párban lévő számok különböző maradékot adnak $\left(n+k\right)$-val osztva. Ez megtehető már akkor is (hogyan?), ha csak $k+1$ különböző maradék létezését követeljük meg (feltéve persze, hogy $2k\le n$). 2. A KöMaL 2000. decemberi számának A. 252. feladata szerint a $2k\le n$ feltételre valójában nincs is szükség: a feladatban megfogalmazott állítás igazolásához elég annyit feltenni, ahogy az $a_1$, $a_2$, $\text{...}$, $a_n$ számok legalább $k+1$ különböző maradékot adnak $\left(n+k\right)$-val osztva. Az alábbiakban erre mutatunk két különböző bizonyítást. 3. Megjegyezzük még, hogy Szemerédi Endre egy nehéz eredményére támaszkodva ez a feltétel is lényegesen gyengíthető: ha $k$ értéke $n$-hez képest ,,elég nagy'', akkor elegendő annyit feltenni, hogy az $a_i$ számok több, mint $c\sqrt[]{k}$ különböző maradékot adnak $\left(n+k\right)$-val osztva.   V. megoldás. (Csikvári Péter megoldásából.) Ha $k=0$, akkor a feltétel semmitmondó, és a bizonyítandó állítás következik a II. megoldás elején kimondott egyszerű állításból. A továbbiakban legyen tehát $k>0$. Tegyük fel, hogy az $a_1$, $a_2$, $\text{...}$, $a_{k+1}$ számok különböző maradékot adnak $\left(n+k\right)$-val osztva. Legyen $s=a_1+a_2+\text{...}+a_{k+1}$, és tekintsük $1\le i\le k+1$ esetén az $a_i$ és $b_i=s-a_i$ számokat, valamint $1\le j\le n-k$ esetén a $c_j=a_1+a_2+\text{...}+a_{k+j}$ számokat, ez összesen $n+k+2$ egész szám. Vizsgáljuk meg, hogyan adhat ezek közül kettő ugyanolyan maradékot $\left(n+k\right)$-val osztva. Az $a_i$ számok páronként különböző maradékot adnak, csakúgy mint a $b_i$ számok. Ha a $c_j$ számok közül kettő ugyanazt a maradékot adja, akkor már készen is vagyunk. Hasonlóképpen készen vagyunk akkor is, ha valamelyik $c_j$ szám ugyanolyan maradékot ad, mint valamelyik $a_i$ vagy $b_i$, hiszen mind maga az $a_i$ szám, mind pedig a $b_i$ minden egyes összeadandója szerepel bármelyik $c_j$ összeadandói között. Mivel $a_i$ a $b_j$-nek is összeadandója $j\ne i$ esetén, feltehetjük azt is, hogy ilyen esetekben $a_i$ és $b_j$ különböző maradékot adnak. Összefoglalva, feltehetjük tehát, hogy ha a fent felsorolt $n+k+2$ szám között kettő azonos maradékot ad $\left(n+k\right)$-val osztva, akkor ez a két szám $a_i$ és $b_i$ egy alkalmas $1\le i\le k+1$ indexre. Minden egyéb esetben ugyanis a bizonyítandó állítás az elmondottak miatt rögtön következik. Vegyük észre azt is, hogy azonnal befejezettnek tekinthetjük a bizonyítást akkor is, ha a felsorolt $n+k+2$ szám valamelyike osztható $\left(n+k\right)$-val. Egyetlen olyan eset képzelhető már csak el, amelyben még nem végeztük el a bizonyítást, nevezetesen ha 3 különböző $i$ index is létezik úgy, hogy $a_i$ és $b_i$ ugyanazt a maradékot adják, vagyis különbségük, $s-2a_i$ osztható $\left(n+k\right)$-val. Legyenek ezek $i_1$, $i_2$ és $i_3$, ekkor a $2a_{i_1}$, $2a_{i_2}$ és $2a_{i_3}$ számok ugyanolyan maradékot adnak $\left(n+k\right)$-val osztva. Nem nehéz megmutatni, hogy ez csak úgy lehetséges, ha az $a_{i_1}$, $a_{i_2}$, $a_{i_3}$ számok közül kettőnek a maradéka megegyezik, ellentétben a megoldás legelején tett feltevésünkkel. Ez mutatja, hogy a bizonyítást már minden esetben elvégeztük.   VI. megoldás. (Nagy Zoltán megoldásából.) Ha a számok közül valamelyik osztható $\left(n+k\right)$-val, akkor már készen is vagyunk, találtunk egy egytagú megfelelő összeget. Tegyük fel tehát, hogy az $a_i$ számok $p$ különböző maradékot ($p\ge k+1$) adnak $\left(n+k\right)$-val osztva, és ezek $0<m_1<m_2<\text{...}<m_p<n+k$. Ha egy összeg minden egyes tagját egy azzal azonos maradékot adó számmal helyettesítünk, a kapott összeg nyilván pontosan akkor lesz osztható $\left(n+k\right)$-val, ha az eredeti összeg is ilyen volt. Ezért feltehetjük azt is, hogy mindegyik $a_i$ valamelyik $m_j$-vel egyenlő. Állítsuk nagyság szerinti sorrendbe az $a_i$ számokat, vagyis legyen $a_1=a_2=\text{...}=a_{k_1}=m_1$, $a_{k_1+1}=a_{k_1+2}=\text{...}=a_{k_2}=m_2$, $\text{...}$, $a_{k_{p-1}+1}=\text{...}=a_n=m_p$, ahol $1\le k_1<k_2<\text{...}<k_{p-1}<n$. Tekintsük most minden $1\le i\le n$ esetén az $s_i=a_1+a_2+\text{...}+a_i$ összeget, és minden $1\le j\le p-1$ esetén a $t_j=a_1+a_2+\text{...}+a_{k_j-1}+a_{k_j+1}$ összeget is. Ez összesen $n+p-1\ge n+k$ szám. Ha ezek között van $\left(n+k\right)$-val osztható, akkor készen vagyunk. Ellenkező esetben kell, hogy legyen kettő, amelyik ugyanolyan maradékot ad $\left(n+k\right)$-val osztva. Ha az $s_i$ számok között van két ilyen, akkor a szokásos indoklás működik. Ha $s_i-t_j$ osztható $\left(n+k\right)$-val valamilyen $i$, $j$ esetén, akkor ismét csak készen vagyunk. Ha ugyanis $i<k_j$, akkor az $s_i$ összeg valódi része a $t_j$ összegnek, és ezért $t_j-s_i$ néhány $a_i$ összege. Ha $i>k_j$, akkor pedig a $t_j$ összeg képezi valódi részét az $s_i$ összegnek. Az pedig nem lehet, hogy $i=k_j$, mert ekkor $s_i-t_j=a_{k_j}-a_{k_j+1}=m_j-m_{j+1}$ lenne, ami nem osztható $\left(n+k\right)$-val. Végül tegyük fel, hogy $t_{\ell }-t_j$ osztható $\left(n+k\right)$-val valamilyen $1\le j<\ell \le p-1$ esetén. Ha még $j+1<\ell$ is teljesül, akkor könnyen látható, hogy $t_{\ell }-t_j$ az $a_i$ számok közül néhánynak az összege. Ugyanez a helyzet akkor is, ha $\ell =j+1$ és $k_{j+1}\ge k_j+2$. Az pedig nem lehetséges, hogy $\ell =j+1$ és $k_{j+1}=k_j+1$, ekkor ugyanis $t_{\ell }-t_j=a_{k_{j+1}+1}+a_{k_j}-a_{k_{j+1}}=m_{j+2}+m_j-m_{j+1}$. Viszont az $m_i$ számokra tett feltevés miatt nyilván $0<m_j<m_{j+2}+m_j-m_{j+1}<m_{j+2}<n+k$, vagyis az egyetlen megmaradt esetben $t_{\ell }-t_j$ nem osztható $\left(n+k\right)$-val.