Cím: Kedvenc problémáim (1982. december)
Szerző(k):  Csirmaz László 
Füzet: 1982/december, 193 - 195. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

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.

Havonta egy-egy, számomra valamilyen oknál fogva kedves feladatot mondok el. Ezek megoldása, noha a középiskolában oktatott ismeretanyagnál többet nem kíván, mégis mély, igazi matematikusi gondolkodást igényel. A problémákra a megjelenést, követő számban megoldást adok, azonban nem kívánok egyetlen problémát sem teljesen lezárni. Akár a feladatokkal, akár azok megoldásával kapcsolatban minden megjegyzést örömmel veszek.

 

*
 

A híres négyszín-tétel azt mondja ki, hogy minden síkra (vagy gömbre) rajzolható térkép országai négy színnel kiszínezhetők úgy, hogy szomszédos országok különböző színűek legyenek. (Két ország szomszédos, ha, közös határszakaszuk van.) Az alábbi állítás ennek a tételnek egy speciális esete, azonban van egy közvetlen, egyszerű bizonyítása is. A feladat : ezt a bizonyítást megtalálni.
Egy asztallapra átfedés nélkül egybevágó fehér korongokat ragasztottak fel. Bizonyítsuk be, hogy a korongok kiszínezhetők négy színnel úgy, hogy az egymással érintkező korongok különböző színűek legyenek !
 

* * *
 

Ha adott n egész szám (n≥2), akkor közülük mindig kiválasztható néhány (lehet, hogy csak egy), melyek összege osztható n-nel. Ez egy jól ismert feladat, melyet az ún. ,,skatulya elvvel'' lehet megoldani. Általában semmit nem lehet mondani arról, hogy a kapott összeg hány tagú. Bizonyítsuk be, hogy akárhogyan is adott 2n-1 darab egész szám, mindig kiválasztható közölük pontosan n, melyek összege osztható n-nel !
 

*
 

Az állítás n=2-re nyilvánvalóan igaz : három egész szám között van két azonos párosságú, s ezek összege osztható 2-vel. Hasonló, bár kissé bonyolultabb a bizonyítás n=3-ra. Ha az öt szám között a 3-mal való osztásra nézve mindhárom maradék (0,1,2) előfordul, akkor egy ilyen, egy olyan és egy amolyan összege osztható 3-mal. Ha viszont csak kétféle maradék szerepel, akkor valamelyik maradék háromszor is megtalálható, s három azonos maradékot adó szám összege is osztható 3-mal.
n=4-re egy új ötletet vetünk be. (Ez volt az 1968. évi Középiskolai Tanulmányi Verseny II. fordulójának egyik feladata.) Három egész szám között van kettő, melyek összege osztható kettővel, így van az adott 7 szám között is, legyenek ezek a és b. A megmaradó öt szám között is van kettő, c és d, melyek összege páros, végül az utolsó három között is találunk ilyen kettőt, e-t és f-et. Most (a+b)/2, (c+d)/2, (e+f)/2 egész számok, tehát közülük van kettő, melyek összege osztható kettővel. Legyenek ezek, mondjuk (a+b)/2 valamint (c+d)/2. Így tehát 12(a+b2+c+d2)=a+b+c+d4 is egész, vagyis a a+b+c+d osztható 4-gyel. Ezzel megtaláltuk a keresett négy számot.
Ugyanez általában is igaz : Ha (2p-1) egész szám között mindig van p darab, melyek összege osztható p-vel, és (2q-1) egész szám között mindig van q, melyek összege osztható q-val, akkor ugyanez igaz pq-ra is : (2pq-1) egész szám között mindig van pq darab, melyek összege osztható pq-val. Valóban, ha a (2pq-1) szám közül már (2q-2)-szer kiválasztottunk p-p darabot úgy, hogy ezeknek a p-eseknek az összege, s1,s2,...,s2q-2 rendre osztható p-vel, akkor még (2pq-1)-(2q-2)⋅p=2p-1 darab számunk marad, melyekből feltevésünk értelmében kiválaszthatunk még p darabot, melyek összege, s2q-1, szintén osztható p-vel. Az s1/p,s2/p,...s2q-1/p együtt 2q-1 darab egész szám, így van közöttük pontosan q, melyek összege osztható q-val, mondjuk
s1/p+...+sq/pq=s1+...+sqpq
egész. Ám ekkor az első q darab p-es csoportban álló pq darab szám összege osztható pq-val, s ezt akartuk belátni.
A feladat állítását n=2 és n=3 esetében már beláttuk, s az előbbiek alapján már következik az összes n=2k⋅3l alakú számra is. Ahhoz, hogy minden n-re igazoljuk, elegendő csak azokat az eseteket tekintenünk, amikor n 3-nál nagyobb prímszám, hiszen prímek szorzataként minden kettőnél nagyobb egész szám előáll.
Legyen tehát n>3 prím, és legyen adva (2n-1) egész szám. Jelölje a1,a2,...,a2n-1 ezeknek n-nel való osztásakor kapott maradékait (0≤ai<n). Különböztessünk meg két esetet : a) Van olyan maradék, amely legalább n-szer előfordul. Ebben az esetben a megfelelő n-es nyilvánvalóan létezik. b) Minden maradék legfeljebb (n-1)-szer szerepel. Ekkor a számok sorrendjét meg tudjuk választani úgy, hogy a2 és a3,a4 és a5, általában a2i és a2i+1 különböző legyen. (Például úgy, hogy először a számokat olyan sorrendbe tesszük, hogy az egyforma maradékokat adók egymás mellé kerüljenek, majd a számokat ebben a sorrendben az 1,3...,2n-3,2n-1,2,4,...,2n-2 sorszámú helyekre tesszük.) Állítjuk, hogy minden 1≤i≤n-re az (ebben a sorrendben) első (2i-1) számból kiválasztható i-es összegek legalább i különböző maradékot adnak n-nel osztva. Ebből a feladat állítása azonnal következik: az n-es összegek legalább n különböző maradékot adnak, tehát a 0 maradéknak is elő kell fordulnia.
Ezek szerint csak e legutóbbi állításunk igazolása maradt hátra. Ezt i-re vonatkozó indukcióval tesszük meg. i=1-re az első 2i-1=1 szám n-nel osztva legalább 1 különböző maradékot ad.
Legyen most i<n, és x1,x2,...,xi, olyan i-tagú összegek, melyek tagjai a1,...a2i-1 közül kerülnek ki, s melyek n-nel osztva különböző maradékokat adnak. Ilyenek az indukciós feltevésünk szerint léteznek. Tekintsük most a következő (i+1)-tagú összegeket :
x1+a2i,x2+a2i,...,xi+a2i,x1+a2i+1,x2+a2i+1,...,xi+a2i+1.
Sem a felső, sem az alsó sorban nincs két olyan szám, mely n-nel osztva ugyanazt a maradékot adná. Így ahhoz, hogy azt igazoljuk, hogy ezen (i+1)-tagú összegek között legalább i+1 különböző maradék fordul elő, elegendő ellenőriznünk, hogy a felső és az alsó sorban nem fordulhatnak elő pontosan ugyanazok a maradékok. Valóban, ha ez így volna, akkor a felső sorban álló számok összege és az alsó sorban álló számok összege is ugyanazt a maradékot adná, azaz különbségük: i⋅a2i-i⋅a2l+1=i⋅(a2i-a2l+1) osztható lenne n-nel. Mivel 1≤i<n, n nem osztója i-nek, továbbá az a2i és a2i+1 választása miatt nem osztója (a2l-a2i+1)-nek sem. Ez pedig lehetetlen, mivel n prímszám, s ha osztója egy szorzatnak, akkor osztója valamelyik tényezőjének is.
Ezzel a bizonyítást befejeztük.
Megjegyezzük, hogy a feladat állítása 2n-1 számnál kevesebbre nem igaz. Legyen ugyanis 2n-2 szám közül n-1 osztható n-nel, és a többi n-nel osztva adjon 1 maradékot. Ezek közül nem választható ki n úgy, hogy összegük n-nel osztható legyen.