Cím: 2000. évi Kürschák József Matematikai Tanulóverseny feladatainak megoldása
Szerző(k):  Károlyi Gyula 
Füzet: 2001/február, 66 - 77. oldal  PDF file
Témakör(ök): Kürschák József (korábban Eötvös Loránd)

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.

 
1. Az A(0,0), B(n,0), C(n,n) és D(0,n) pontok által meghatározott négyzet határán és belsejében elhelyezkedő rácspontokat pirosra vagy zöldre színezzük úgy, hogy a négyzetbe eső valamennyi egységoldalú rácsnégyzetnek pontosan két csúcsa legyen piros. Hányféleképpen tehetjük ezt meg?
 
Megoldás. A szóban forgó rácspontok n+1 sorban és n+1 oszlopban helyezkednek el. Nevezetesen, az i-edik sor (0in) azokat a rácspontokat tartalmazza, amelyeknek a második koordinátája i. Hasonlóképpen, az i-edik oszlop azokból a rácspontokból áll, amelyek első koordinátája i. Két rácspontot szomszédosnak fogunk hívni akkor, ha ugyanabban a sorban vagy oszlopban egymás mellett helyezkednek el. Az (i,j) pont szomszédai tehát az (i-1,j), (i+1,j), (i,j-1) és (i,j+1) pontok, amennyiben ezek is az ABCD négyzet pontjai.
Nyilván jó színezését kapjuk a pontoknak akkor, ha minden sorban felváltva színezzük pirosra és zöldre az egymást követő pontokat. Az egyes sorokat ekkor egymástól függetlenül kétféleképpen színezhetjük, ezért az ilyen színezéseknek a száma 2n+1. Ugyanilyen megfontolásból lesz jó az a 2n+1 színezés is, ahol az egyes oszlopokban követik egymást felváltva a piros és zöld pontok. Mivel a pontokat kétféleképpen lehet úgy kiszínezni, hogy sem a sorokban, sem az oszlopokban nincs két szomszédos azonos színű pont, ezért így összesen
2n+1+2n+1-2=2n+2-2
jó színezést találtunk.
Megmutatjuk, hogy a fentieken kívül nincs más jó színezés. Ehhez tegyük fel először azt, hogy a pontokat megszíneztük a kívánt módon, és valamelyik oszlopban ‐ mondjuk az i-edikben ‐ van egymás mellett két azonos színű szomszédos pont. Legyenek ezek (i,j) és (i,j+1). Ekkor az (i-1)-edik és az (i+1)-edik oszlopban is található egymás mellett két azonos színű pont. Nevezetesen az (i-1,j), (i-1,j+1), (i+1,j), (i+1,j+1) pontok mind azonos színűek, és egyben az (i,j), (i,j+1) pontoktól eltérő színűek kell, hogy legyenek. Indukcióval könnyen ellenőrizhető ezután, hogy az (i-k,j), (i-k,j+1), (i+k,j), (i+k,j+1) pontok színe az (i,j), (i,j+1) pontokéval megegyező, ha k páros, illetve azokétól eltérő, ha k páratlan.
Tegyük fel most még azt is, hogy valamelyik sorban ‐ mondjuk a j'-edikben ‐ is van egymás mellett két azonos színű pont: (i',j') és (i'+1,j'). Az előbbihez hasonló gondolatmenettel (vagy egyszerűbben: szimmetria okokra hivatkozva) megállapíthatjuk, hogy minden k-ra az (i',j'-k), (i'+1,j'-k), (i',j'+k), (i'+1,j'+k) pontok azonos színűek.
A fentiek szerint az (i',j) pont színe meg kell, hogy egyezzen mind az (i',j+1), mind az (i'+1,j) pont színével. Ez azonban egy jó színezésben nem történhet meg, hiszen a felsorolt három pont éppen egy egységoldalú rácsnégyzet három csúcsa. Ez az ellentmondás igazolja azon állításunkat, miszerint minden jó színezésben vagy az oszlopokban, vagy a sorokban váltakozó színű pontok követik egymást. A kérdéses színezések száma tehát 2n+2-2.
 
2. Legyen ABC szabályostól különböző háromszög, P pedig a síknak a háromszög csúcsaitól különböző pontja. Jelöljék AP, BP és CP rendre az AP, BP és CP egyeneseknek az ABC háromszög köré írt körrel vett második metszéspontjait. Mutassuk meg, hogy a síknak pontosan két olyan P és Q pontja van, hogy az APBPCP és AQBQCQ háromszögek szabályosak, továbbá, hogy a PQ egyenes áthalad az ABC háromszög köré írt kör középpontján.
 
Az első két megoldás a körre vonatkozó inverzió fogalmára támaszkodik, ezért röviden összefoglaljuk ennek a transzformációnak legfontosabb tulajdonságait. Ha adott a síkon egy O középpontú, r sugarú k kör, akkor a k körre vonatkozó inverzió a sík O-tól különböző pontjainak az a leképezése, amely tetszőleges P ponthoz az OP félegyenes azon P' pontját rendeli hozzá, amelyre OPOP'=r2. Ha az A pont (vagy alakzat) képe B, akkor a B ponté (alakzaté) éppen A. A leképezés tehát egy-egyértelmű, a k pontjait helyben hagyja, k-n belüli pontokat pedig k-n kívüli pontokba visz, és fordítva. Ha egy kör az O pontot elkerüli, akkor a körvonal képe egy, az O-t szintén elkerülő körvonal, egy O-n áthaladó k1 körvonal képe pedig egy O-ra nem illeszkedő egyenes: a k és k1 körök hatványvonala. Fontos tulajdonsága az inverziónak a szögtartás: ha k1 és k2 egy-egy körvonal (elfajuló esetben O-ra nem illeszkedő egyenes), akkor a k1' és k2' körök ugyanolyan szög alatt metszik egymást, mint a k1 és k2 körök. (Két egymást metsző kör által bezárt szög alatt közös pontjukban húzott érintőik hajlásszögét értjük.) Speciálisan, ha a k1 kör k-t merőlegesen metszi, akkor k'=k miatt k1' is merőlegesen metszi k-t, méghozzá ugyanabban a két pontban, ezért k1'=k1.
Ezek után lássuk először a legkevesebb diszkussziót igénylő megoldást.
 
I. Megoldás. Ha P az ABC háromszög köré írható k körön van, akkor AP=BP=CP=P, és így az APBPCP háromszögről nem beszélhetünk. Az egyazon húrhoz tartozó kerületi szögek egyenlőségéről szóló tételre hivatkozva az 1. ábráról leolvasható, hogy az APBPP háromszög hasonló a BAP háromszöghöz, függetlenül attól, hogy P a k körön belül, vagy azon kívül helyezkedik-e el. Ezért APBPBPP=BAAP, és hasonló módon CPBPBPP=BCCP.
Az APBP=BPCP feltétel tehát ekvivalens az APCP=ABCB feltétellel, vagyis azzal, hogy P az A és C pontokhoz, valamint az ABCB arányhoz tartozó Apollóniusz-körnek k-ra nem illeszkedő pontja. (Abban a speciális esetben, amikor AB=CB, ez az Apollóniusz-kör elfajuló, és az AC szakasz felező merőlegesével egyezik meg.) Ugyanígy kapjuk azt is, hogy az APBP=APCP feltétel ekvivalens azzal, hogy P a B és C pontokhoz, valamint az BACA arányhoz tartozó Apollóniusz-körnek k-ra nem illeszkedő pontja. Az APBPCP háromszög tehát pontosan akkor szabályos, ha P az említett két Apollóniusz-kör (k-ra nem illeszkedő) közös pontja.
Az AC egyenes elválasztja az első Apollóniusz-kör k-val való, B-től különböző B' metszéspontját a B ponttól. Ugyanígy, a BC egyenes elválasztja a második Apollóniusz-kör k-val való, A-től különböző A' metszéspontját az A ponttól. Következésképpen az A, B, A', B' pontok a k körön ilyen sorrendben helyezkednek el (2. ábra), és ezért a két Apollóniusz-kör mind a k körön belül, mind azon kívül egy-egy pontban metszi egymást. Pontosabban, a k-n kívüli metszéspont nem létezik abban az esetben, ha mind a két Apollóniusz-kör elfajuló, ez azonban pontosan akkor következik be, ha az ABC háromszög szabályos. Ezzel a feladat első állítását beláttuk.
A második állítás bizonyítása azon az észrevételen alapul, hogy az említett Apollóniusz-körök a k kört merőlegesen metszik. Ekkor ugyanis a szögtartás miatt a k-ra vonatkozó inverzió mind a két Apollóniusz-kört saját magába viszi, és ezért a körök metszéspontjainak képe az inverzió során ugyanez a két pont. Mivel a k körön belüli pontok a k-n kívüli pontokba transzformálódnak, ez csak úgy lehetséges, ha az inverzió P-t és Q-t felcseréli. A P és Q pontok tehát egymásnak a k körre vonatkozó inverz képei, ennek megfelelően a PQ egyenes valóban áthalad a k kör O középpontján.

Szimmetria okokból elegendő azt megmutatni, hogy az első Apollóniusz-kör (jelöljük ezt k1-gyel) merőlegesen metszi k-t. Ez nyilvánvaló, ha AB=CB, egyébként pedig feltehetjük, hogy α=BAC>BCA=γ. Legyen a B-ből induló belső szögfelező talppontja T, a külsőé S. A szögfelező-tétel értelmében ST éppen a k1 körnek az AC egyenesre eső átmérője, amely tartalmazza az A pontot is (3. ábra). Ezért SBT=π2. Továbbá
TBO=β2-(π2-α)=π2-(π-(α+β2))=π2-BTS=BST=SBO1,
ahol O1 a k1 kör középpontja. Ezért
O1BO=SBT+TBO-SBO1=π2,
és éppen ezt akartuk bizonyítani.

 
II. Megoldás. Rögzítsük a pozitív forgásirányt úgy hogy az A, B, C csúcsok ilyen sorrendben helyezkedjenek el a háromszög köré írt k körön. Hogy kevesebb esetet kelljen megkülönböztetni, irányított szögekkel fogunk dolgozni. Két irányított szöget azonosnak tekintünk akkor, ha különbségük 2π egész számú többszöröse.
Ha X, Y a k kör pontjai, akkor az XY irányított ívhez tartozó (irányított) kerületi szöget jelölje φ(XY). Például φ(AB)=γ, ϕ(BC)=α és ϕ(CA)=β a háromszög szögei, ugyanakkor φ(BA)=180-γ. Azt mondjuk, hogy az XY (irányított) szakasz a P pontból ϕ szög alatt látszik, ha XPY=ϕ, ekkor az YX szakasz P-ből -ϕ szög alatt látszik. Az ilyen P pontok összessége alkotja az XY szakaszra támaszkodó ϕ szögű látókörívet, ami ϕ=π esetén a végpontjait nem tartalmazó XY szakasszal, ϕ=0 esetén pedig az XY egyenes XY szakaszon kívül eső részével egyezik meg.
Ennyi előkészület után most már rátérhetünk a megoldás lényegi részére. A k körön nyilván nem helyezkedhet el megfelelő pont. Legyen tehát először P a k kör egy tetszőleges belső pontja, ekkor az ABC és APBPCP háromszögek azonos körüljárásúak. Az utóbbi háromszög tehát pontosan akkor szabályos, ha a ϕ(APBP), ϕ(BPCP), ϕ(CPAP) szögek közül legalább kettő (és persze akkor a harmadik is) 60. Mármost
APB=180-BAP-PBA=180-BAPA-BPBA=180-ϕ(BAP)-ϕ(BPA)=ϕ(AB)+ϕ(APBP)=γ+ϕ(APBP),
Az AB, BAP, APBP és BPA ívek ugyanis együtt éppen lefedik a k kört, így a hozzájuk tartozó kerületi szögek összege pontosan 180. Hasonlóképpen, BPC=α+ϕ(BPCP) és CPA=β+ϕ(CPAP). Az APBPCP háromszög tehát pontosan akkor szabályos, ha a P pontból az AB, BC, CA szakaszok rendre γ+60, α+60, β+60 szögben látszanak. E három feltétel közül persze elég csak kettőt megkövetelni.
Most már nem nehéz megmutatni, hogy a k körön belül pontosan egy ilyen P pont van. Az általánosság megszorítása nélkül feltehetjük, hogy α, γ<120. Tekintsük most az AB szakaszra támaszkodó γ+60 szögű C látókörívet és a BC szakaszra támaszkodó α+60 szögű A látókörívet, ezek tehát a megfelelő szakaszoknak a háromszöget tartalmazó oldalán helyezkednek el. A harmadik hasonló látókörívre is (amely már nem biztos, hogy az AC szakasznak a háromszöget tartalmazó oldalán helyezkedik el) szükségünk lesz később, ezt jelöljük B-vel. Hogy ez a két ív pontosan egy pontban metszi egymást, méghozzá a k kör belsejében, a következőképpen igazolhatjuk. Először is vegyük észre, hogy mindkét látókörív a k kör belsejében halad. Másodszor, B közös végpontja mindkét ívnek. Ezért a két ívnek legfeljebb egy közös belső pontja lehet, és a metszéspont létrejöttének szükséges és elégséges feltétele az, hogy az A ív a BC oldallal, illetve az C ív a BA oldallal olyan szögeket zárjon be, amelyek összege β-t meghaladja (most kivételesen nem irányított szögektől beszélünk). Egyszerű számolással ellenőrizhető, hogy ez valóban így van. Azt is megállapíthatjuk, hogy lévén ekkor CPA=β+60, ez a P pont akkor esik az ABC háromszög belsejébe, ha β<120, a háromszögön kívül helyezkedik el a β>120 esetben, ha pedig β=120, akkor az AC oldalra illeszkedik.
Összefoglalva tehát megállapíthatjuk, hogy a k körön belül mindig pontosan egy ilyen pont van, méghozzá az ABC háromszög belsejében, ha a háromszög minden szöge 120-nál kisebb, annak határán, ha a háromszögnek van egy 120-os szöge, illetve azon kívül, ha valamelyik szöge 120-nál nagyobb. Ebből a P pontból az AB, BC, CA szakaszok rendre γ+60, α+60, β+60 alatt látszanak.
Legyen most a P pont a k kör egy külső pontja. Az APB meghatározásához különböztessünk meg négy esetet annak megfelelően, hogy a PA és PB félegyeneseken a P, A, AP, illetve P, B, BP pontok milyen sorrendben helyezkednek el (1. ábra). Megjegyezzük, hogy az irányított szögekkel való számolásnak az is előnye, hogy nem kell azzal foglalkoznunk, hogy ez a két félegyenes egymáshoz képest milyen helyzetű. Mind a négy esetben könnyen ellenőrizhető, hogy
APB=180-BAP-PBA=180-ϕ(BAP)-ϕ(BPA)=
(180-ϕ(BAP)-ϕ(APA))-ϕ(BPAP)=ϕ(AB)-ϕ(BPAP)=γ-ϕ(BPAP).
Ugyanígy BPC=α-ϕ(CPBP) és CPA=β-ϕ(APCP). Mivel most az APBPCP háromszög körüljárása ellentétes az ABC háromszögével, ez a háromszög pontosan akkor szabályos, ha a ϕ(BPAP), ϕ(CPBP), ϕ(APCP) szögek közül legalább kettő (és persze akkor a harmadik is) 60. Ezzel ekvivalens az, hogy a P pontból az AB, BC, CA szakaszok rendre γ-60, α-60 és β-60 alatt látszanak. Jelölje az ennek megfelelő látóköríveket rendre C', A' és B'.
Állítás. A k körre vonatkozó inverziónál az A, B, C ívek képe rendre A', B' és C'.
Ebből azonnal következik, hogy a k körön kívül is pontosan egy olyan Q pont van, amelyre az AQBQCQ háromszög szabályos, mégpedig ez a pont a P pont inverz képe. Probléma csak akkor lenne, ha P egybeesne a k kör középpontjával, ez azonban nem lehetséges, hiszen az ABC háromszög nem szabályos. Egyúttal azt is megkaptuk, hogy a k kör középpontja, valamint a P és Q pontok egy egyenesen vannak.
Most már csak a fenti állítást kell igazolni. Ha a háromszög szögeire semmiféle megkötést nem teszünk, akkor szimmetria okok miatt nyilván elég annyit megmutatni, hogy A inverz képe éppen A'. A bizonyítás azon az egyszerű észrevételen múlik, hogy az a két ív, amelynek pontjaiból az XY (irányított) szakasz ϕ1, illetve ϕ2 szög alatt látszik, ϕ1-ϕ2 szöget zár be egymással. Ennek alapján a kerületi szögek tételéből következik, hogy mind az A ív, mind az A' ív 60-os szöget zár be a k körrel. Nem nehéz megmutatni, hogy az A ív a k körön belül, az A' ív pedig azon kívül halad. A két ívnek ugyanazok a végpontjai, de nem egészítik ki egymást egyetlen körvonallá. Mivel az a két körvonal, amely a k-t a B és C pontokban egyaránt 60-os szög alatt metszi, egymás inverz képe a k körre nézve, a szóban forgó két ív is egymás inverze, és ezt akartuk bizonyítani.
 
III. Megoldás. (Béky Bence megoldása.) Az előző megoldások valamelyikét követve először is megállapítjuk, hogy valóban két ilyen pont létezik, méghozzá egy a háromszög köré írható körön belül (jelöljük ezt P-vel), a másik pedig a körön kívül (legyen ez Q). Vegyük most észre, hogy az APBPCP háromszög körüljárása megegyezik az ABC háromszögével, míg az AQBQCQ háromszögé azzal ellentétes. Található tehát egy, a k kör O középpontjára illeszkedő e egyenes, amelyre az APBPCP háromszöget tükrözve az AQBQCQ háromszöget kapjuk.
Vizsgáljuk először azt az általános esetet, amikor AP különbözik a BQ, CQ pontoktól, BP különbözik az AQ, CQ pontoktól és CP is különbözik az AQ, BQ pontoktól. Nem lehet, hogy például az APBQ egyenes egybeesik az AQBP egyenessel, mert ekkor AP=BP lenne. Az APBQ egyenes tehát csak akkor lehet párhuzamos az AQBP egyenessel, ha egyben e-vel is párhuzamos. Ugyanez elmondható a másik két értelemszerűen felírt egyenespárról. Jelölje A*, B* és C* rendre a BPCQ és BQCP egyeneseknek, az APCQ és AQCP egyeneseknek, illetve az APBQ és AQBP egyeneseknek a metszéspontját. Az elmondottak szerint ezen egyenespárok közül legfeljebb egy lehet párhuzamos helyzetben, az e egyenesre eső A*, B*, C* pontok közül tehát kettő biztosan létrejön. Feltehetjük, hogy az A* és B* pontok ilyenek. Világos, hogy A* és B* különböző pontok (4. ábra).
Tekintsük most a k körbe írt BBQCPCCQBP önmagát átmetsző hatszöget. Ennek BBQ és CCQ szemközti oldalai Q-ban, BQCP és CQBP szemközti oldalai A*-ban, CPC és BPB szemközti oldalai pedig P-ben metszik egymást. Pascal tétele szerint tehát az A* pont illeszkedik a PQ egyenesre (5. ábra). Hasonlóképpen belátható, ezúttal az AAQCPCCQAP hatszögből kiindulva, hogy a B* pont is illeszkedik a PQ egyenesre. A PQ egyenes tehát egybeesik az A*B* egyenessel, vagyis az O ponton áthaladó e egyenessel, ami bizonyítja az általános esetben a feladat második állítását.
Tegyük fel végül, hogy mondjuk BP=CQ=X, ekkor az e-re való szimmetria miatt BQ=CP=Y, végül pedig AP=AQ a k körnek az a Z pontja, amelyre az XYZ háromszög szabályos. Világos, hogy Z illeszkedik az e egyenesre, XY pedig merőleges arra. Ekkor az BPCQ és BQCP egyenesek helyett tekintsük a k körhöz annak X, illetve Y pontjában húzott érintőjét, ez a két egyenes a Z pontnak az XY-ra vonatkozó tükörképében metszi egymást. Jelöljük most ezt a pontot A*-gal. A B*, C* pontok ugyanúgy definiálhatók, mint az általános esetben, és ezúttal egybeesnek Z-vel. Az A* és B* pontok tehát most is az e egyenest határozzák meg. Most már szinte szó szerint megismételhetjük az előző bekezdést azzal az apró módosítással, hogy most a BBQCPCCQBP hatszög elfajuló abban az értelemben, hogy két-két szomszédos csúcsa egybeesik. Ezért a Pascal tétel alkalmazásánál a BPCQ és BQCP egyenesek helyett éppen az előbb említett érintőket kell tekinteni.
 
Megjegyzések. 1. A feladat komplex számok segítségével viszonylag egyszerű számolás útján is megoldható. Ezt az utat választotta Gyenes Zoltán a második állítás bizonyításához.
2. Egy mélyebb matematikai eszközöket használó megoldást tartalmaz, és a feladat hátterére mutat rá Hraskó András cikke, amely a következő számunkban jelenik meg.
3. A harmadik megoldásból azonnal leolvasható, hogy az APBPCP és AQBQCQ háromszögek a PQ egyenesre szimmetrikusan helyezkednek el. Erre az eredményre az első megoldás ügyes folytatásával is eljuthatunk. Hogyan? Ennek az önmagában is szép feladatnak a megoldását már az olvasóra bízzuk.

 
3. Legyen k nemnegatív egész szám, és tegyük fel, hogy az a1, a2, ..., an egész számok legalább 2k különböző maradékot adnak (n+k)-val osztva. Bizonyítandó, hogy a számok között van néhány, amelyek összege osztható (n+k)-val.
 
I. megoldás. Az általánosság megszorítása nélkül feltehető, hogy az a1, a2, ..., a2k számok páronként különböző maradékot adnak (n+k)-val osztva. Tekintsük a következő n+k különböző számot:
b1=a1,b2=a1,b3=a1+a2b3i+1=a1+a2+...+a2i+a2i+1(0<i<k)b3i+2=a1+a2+...+a2i+a2i+2(0<i<k)b3i+3=a1+a2+...+a2i+a2i+1+a2i+2(0<i<k)bj=a1+a2+...+aj-k(3k<jn+k)
Ha ezek között van olyan, amelyik osztható (n+k)-val, akkor mar készen is vagyunk. Ellenkező esetben pedig van a számok között kettő, mondjuk bs és bt (s<t) amelyik ugyanolyan maradékot ad (n+k)-val osztva. Ekkor bt-bs nyilván osztható (n+k)-val. Azt kell már csak észrevennünk, hogy ez a különbség felírható az a1, a2, ..., an 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 bt-bs=a2i+2-a2i+1 volna. Ez azonban feltételezésünk értelmében nem osztható (n+k)-val.
 
II. megoldás. Ugyanehhez a végeredményhez egy kissé eltérő kiindulással is eljuthatunk.
Állítás. Tetszőleges b1, b2, ..., bN egész számok esetén léteznek olyan 1ijN indexek, hogy a bi+bi+1+...+bj ö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, ..., N esetén az st=b1+...+bt összegeket, ahol s0=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 sk és s (0k<N) két ilyen összeg, akkor s-sk=bk+1+bk+2+...+b 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 a1, a2, ..., a2k számok páronként különböző maradékot adnak (n+k)-val osztva. Tekintsük a
b1=a1,b2=a2-a1,b3=a1,b4=a3,b5=a4-a3,b6=a3,...,b3k=a2k-1,b3k+1=a2k+1,b3k+2=a2k+2,...,bn+k=an
számokat. Így éppen N=n+k egész számot írtunk fel.
A fenti állítás értelmében léteznek olyan 1ijN indexek, hogy S=bi+bi+1+...+bj osztható N-nel. Elegendő azt megmutatni, hogy S felírható az a1, a2, ..., an számok közül néhánynak az összegeként. Ez egészen nyilvánvaló akkor, ha i3k+1, ebben az esetben ugyanis
S=ai-k+ai-k+1+...+aj-k.

Ha i3k<j, akkor legyen i=3s+q, ahol 0s<k és 1q3. Ekkor nyilván
S=A+a2s+3+a2s+4+...+aj-k,
ahol A=a2s+1+a2s+2, a2s+2, vagy a2s+1 annak megfelelően, hogy q értéke 1, 2, vagy pedig 3.
Végül j3k esetén legyen i=3s+q, j=3t+r, ahol 0st<k és 1q,r3. Ekkor könnyen ellenőrizhető, hogy
S=A+a2s+3+a2s+4+...+a2t+B,
ahol A-t ugyanúgy definiáljuk, mint az előző esetben, B értéke pedig a2t+1, a2t+2, vagy pedig e kettő összege aszerint, hogy r=1, 2, vagy 3, feltéve, hogy st. Ha s=t, akkor is könnyen látható, hogy S értéke a2s+1+a2s+2, a2s+2, vagy a2s+1. Kivételt képezne az az egyetlen esetet, amikor s=t és q=r=2. Ez azonban nem fordulhat elő, hiszen ekkor S=a2s+2-a2s+1 lenne, az a1, a2, ..., a2k 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 a1, ..., a2k számok páronként különböző maradékot adnak (n+k)-val osztva. Vezessük be az A={a1,a2,...,a2k} jelölést, és legyen b1=a1. Ha valamilyen 1<jk+1 esetén a b1, b2, ..., bj-1 számokat már definiáltuk, akkor legyen bj az A halmaznak egy olyan eleme, amelyik a b1, b2, ..., bj-1, b1+b2, b1+b2+b3, ..., b1+b2+...+bj-1 számok egyikével sem ad azonos maradékot (n+k)-val osztva. Ilyen szám valóban létezik, hiszen ezekkel a feltételekkel az A halmaznak legfeljebb (j-1)+(j-2)<2k elemét zártuk ki.
Jelölje bk+2, bk+3, ..., b2k az A halmaz fennmaradó elemeit valamilyen sorrendben, és tekintsük a következő n+k számot:
si=b1+b2+...+bi(1i2k),sj=a1+a2+...+aj(2k<in),sn+1=b2,sn+2=b3,...,sn+k=bk+1.
Ha ezek közül valamelyik osztható (n+k)-val, akkor készen is vagyunk, ellenkező esetben viszont közülük kettő azonos maradékot ad (n+k)-val osztva, ezek különbsége tehát ismét csak osztható (n+k)-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 ai 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 si, ahol 1in, a másik pedig sn+j, 1jk, akkor a bi számok megválasztása miatt i>j kell, hogy teljesüljön. Ekkor azonban sn+j=bj+1 éppen az si egyik összeadandója, következésképpen az (n+k)-val osztható si-sn+j szám most is felírható az ai 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 a1, a2, ..., an 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 a1, a1+a2, ..., a1+a2+...+an ö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 ai ö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 j1 és tegyük fel azt is, hogy az állítás igazolást nyert már i=j esetén is. Ebből i=(j+1)-re a következőképpen kaphatjuk meg az állítást. Legyenek a1, a2, ..., an 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 ai-t, amelyik ezek valamelyikével kongruens modulo m. Az általánosság megszorítása nélkül feltehetjük, hogy ezek éppen az at+1, at+2, ..., an számok. Az a1, a2, ..., at számokról tudjuk azt, hogy legalább 2j különböző maradékot adnak m-mel osztva.
Tegyük fel, hogy az ai 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 a1, a2, ..., at számokból képezhető t+j különböző maradékot adó összeg, az at+1, at+2, ..., an számokból pedig képezhető n-t+1 különböző maradékot adó összeg. Jelölje ezeket rendre s1, s2, ..., st+j, illetve r1, r2, ..., rn-t+1. Minden további nélkül feltehető az is, hogy s1=a1+a2+...+at. Tekintsük most a következő n+j+1 számot: s1, s2, ..., st+j, s1+r1, s1+r2, ..., s1+rn-t+1, ezek bármelyike felírható az ai 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 sb ugyanolyan maradékot ad m-mel osztva, mint s1+rc, hiszen különbségük, (s1-sb)+rc jól láthatóan néhány ai ö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 a1, a2, ..., an számok közül a1 és a2 különböző maradékot adnak m-mel osztva. Ha az a1,a2,a1+a2,a1+a2+a3,...,a1+a2+...+an 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 ai ö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 ai 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 (n+k)-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 2kn).
2. A KöMaL 2000. decemberi számának A. 252. feladata szerint a 2kn 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 a1, a2, ..., an számok legalább k+1 különböző maradékot adnak (n+k)-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 ai számok több, mint ck különböző maradékot adnak (n+k)-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 a1, a2, ..., ak+1 számok különböző maradékot adnak (n+k)-val osztva. Legyen s=a1+a2+...+ak+1, és tekintsük 1ik+1 esetén az ai és bi=s-ai számokat, valamint 1jn-k esetén a cj=a1+a2+...+ak+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 (n+k)-val osztva. Az ai számok páronként különböző maradékot adnak, csakúgy mint a bi számok. Ha a cj 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 cj szám ugyanolyan maradékot ad, mint valamelyik ai vagy bi, hiszen mind maga az ai szám, mind pedig a bi minden egyes összeadandója szerepel bármelyik cj összeadandói között. Mivel ai a bj-nek is összeadandója ji esetén, feltehetjük azt is, hogy ilyen esetekben ai és bj 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 (n+k)-val osztva, akkor ez a két szám ai és bi egy alkalmas 1ik+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ó (n+k)-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 ai és bi ugyanazt a maradékot adják, vagyis különbségük, s-2ai osztható (n+k)-val. Legyenek ezek i1, i2 és i3, ekkor a 2ai1, 2ai2 és 2ai3 számok ugyanolyan maradékot adnak (n+k)-val osztva. Nem nehéz megmutatni, hogy ez csak úgy lehetséges, ha az ai1, ai2, ai3 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ó (n+k)-val, akkor már készen is vagyunk, találtunk egy egytagú megfelelő összeget. Tegyük fel tehát, hogy az ai számok p különböző maradékot (pk+1) adnak (n+k)-val osztva, és ezek 0<m1<m2<...<mp<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ó (n+k)-val, ha az eredeti összeg is ilyen volt. Ezért feltehetjük azt is, hogy mindegyik ai valamelyik mj-vel egyenlő.
Állítsuk nagyság szerinti sorrendbe az ai számokat, vagyis legyen a1=a2=...=ak1=m1, ak1+1=ak1+2=...=ak2=m2, ..., akp-1+1=...=an=mp, ahol 1k1<k2<...<kp-1<n. Tekintsük most minden 1in esetén az si=a1+a2+...+ai összeget, és minden 1jp-1 esetén a tj=a1+a2+...+akj-1+akj+1 összeget is. Ez összesen n+p-1n+k szám. Ha ezek között van (n+k)-val osztható, akkor készen vagyunk. Ellenkező esetben kell, hogy legyen kettő, amelyik ugyanolyan maradékot ad (n+k)-val osztva.
Ha az si számok között van két ilyen, akkor a szokásos indoklás működik.
Ha si-tj osztható (n+k)-val valamilyen i, j esetén, akkor ismét csak készen vagyunk. Ha ugyanis i<kj, akkor az si összeg valódi része a tj összegnek, és ezért tj-si néhány ai összege. Ha i>kj, akkor pedig a tj összeg képezi valódi részét az si összegnek. Az pedig nem lehet, hogy i=kj, mert ekkor si-tj=akj-akj+1=mj-mj+1 lenne, ami nem osztható (n+k)-val.
Végül tegyük fel, hogy t-tj osztható (n+k)-val valamilyen 1j<p-1 esetén. Ha még j+1< is teljesül, akkor könnyen látható, hogy t-tj az ai számok közül néhánynak az összege. Ugyanez a helyzet akkor is, ha =j+1 és kj+1kj+2. Az pedig nem lehetséges, hogy =j+1 és kj+1=kj+1, ekkor ugyanis t-tj=akj+1+1+akj-akj+1=mj+2+mj-mj+1. Viszont az mi számokra tett feltevés miatt nyilván 0<mj<mj+2+mj-mj+1<mj+2<n+k, vagyis az egyetlen megmaradt esetben t-tj nem osztható (n+k)-val.
Károlyi Gyula