Feladat: F.2460 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Alexy N. ,  Badics T. ,  Bán Rita ,  Bóna M. ,  Bujdosó 419 L. ,  Csermely Ágnes ,  Dinnyés Enikő ,  Edvi T. ,  Fülöp T. ,  Füst Ágnes ,  Hetyei Judit ,  Horváth A. ,  Hraskó A. ,  Ilosvay F. ,  Ispány Márton ,  Kaiser A. ,  Karácsony P. ,  Katona Gy. ,  Kerner Anna ,  Komorovicz J. ,  Kós Géza ,  Kovács 111 S. ,  Kruzslicz F. ,  Limbek Cs. ,  Magyar Á. ,  Megyesi G. ,  Mócsy M. ,  Németh-Buhin Ákos ,  Paál Beatrix ,  Pfeil T. ,  Pintér A. ,  Pintér Gabriella ,  Ribényi Ákos ,  Simon Gy. ,  Simon P. ,  Sobor G. ,  Varga K. 
Füzet: 1986/április, 153 - 154. oldal  PDF file
Témakör(ök): Függvények, Részhalmazok, Számhalmazok, Indirekt bizonyítási mód, Komplex számok, Legkisebb közös többszörös, Számsorok, Számtani sorozat, Feladat
Hivatkozás(ok):Feladatok: 1984/február: F.2460

Az A1,A2,...,An halmazok a pozitív egész számok részhalmazai, amelyekről a következőket tudjuk:
a) az A1...An halmaz az összes pozitív egész szám halmaza;
b) Ai halmaz elemei bi különbségű végtelen számtani sorozatot alkotnak.
Bizonyítsuk be, hogy van olyan bj, amely osztója a többi bi szám legkisebb közös többszörösének.

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.

A legkisebb közös többszöröst a szóban forgó számok []-be foglalt felsorolásával jelöljük.
Jelölje M a pozitív egész számok halmazát. Ha b1=1, akkor az állítás nyilván igaz (1|[b2,b3,...,bn]). Ha b12, akkor vagy a b1-gyel osztható, vagy pedig a b1-gyel osztva 1 maradékot adó számok teljesen kimaradnak az A1-ből, hiszen A1 minden eleme ugyanannyi maradékot ad b1-gyel osztva. Az M\A1 halmaznak tehát végtelen sok eleme van.
Tekintsük most a legnagyobb olyan j-t, amelyre M\(A1A2...Aj) végtelen halmaz. Mivel a feltétel szerint M\(A1A2...An) üres, tehát ilyen j létezik, j<n és M\(A1A2...Aj+1) véges.
Memutatjuk, hogy bj+1|[b1,b2,...,bj]. Ebből az állítás már következik, hisz [b1,...,bj]|[b1,...,bj, bj+2,...,bn].
A j megválasztása miatt végtelen sok olyan Aj+1-beli szám van, amelyik nem eleme az A1A2...Aj halmaznak. Ha x egy ilyen szám, akkor azt állítjuk, hogyx-b sem eleme A1A2...Aj-nek, ahol b=[b1,b2,...,bj]. Ha ugyanis (x-b)Ai volna valamilyen 1ij-re, akkor (x-b)+(b/bi)bi=x is Ai-beli volna, hiszen az Ai egy bi differenciájú számtani sorozat, b/bi pedig pozitív egész.
Azt kaptuk tehát, hogy végtelen sok olyan Aj+1-beli x szám van, amelyre x-bA1A2...Aj. Másfelől az A1A2...Aj+1 halmazban csak véges sok természetes szám nincs ott, a talált végtelen sok x-b alakú szám között így van olyan ‐ végtelen sok ‐, amelyik benne van ebben a halmazban. Mivel pedig láttuk, hogy az első j halmaz uniójában nincs benne, ezért valamennyi ilyen számnak az Aj+1-ben kell lennie.
Van tehát ‐ mégpedig végtelen sok, de erre nincs szükség ‐ olyan Aj+1-beli x, amelyre x-bAj+1 is igaz. Ebből viszont már következik az állítás, hiszen az Aj+1 számtani sorozat bármely két elemének különbsége osztható a sorozat differenciájával, bj+1-gyel.

 

Megjegyzések. 1. A feladatban leírt tulajdonságokkal rendelkező halmazrendszereket véges fedőrendszereknek nevezik, és igen sok a velük kapcsolatos megoldatlan probléma. Nem ismeretes például, hogy létezik- e olyan véges fedőrendszer, ahol a differenciák egymástól és 1-től különböző páratlan számok. Azt sem tudjuk még, hogy igaz-e az a ‐ feladatunkénál jóval erősebb ‐ állítás, miszerint egy véges fedőrendszerben mindig van olyan differencia, amelyik egy másiknak osztója.
2. Ha a szóban forgó sorozatokról még azt is föltesszük, hogy semelyik kettőnek nincs közös eleme, akkor jóval többet állíthatunk: azt, hogy a differenciák közt vannak egyenlők. A bizonyításhoz a számelmélet egy jól ismert, bár első találkozáskor kétségkívül meghökkentő eszközének, a komplex változós függvényeknek néhány elemi tulajdonságára van szükség. Az alábbiakban vázoljuk a fenti állítás bizonyítását.
Tegyük fel, hogy a természetes számokat ‐ ez nem lényeges különbség ‐ sikerült felbontanunk véges sok ‐ mondjuk k darab ‐ közös elem nélküli végtelen számtani sorozat egyesítésére. Legyenek ezek az {ai+nbi} alakú sorozatok (i=1,2,...,...,k,nN).
Tekintsük az alábbi végtelen mértani sort:
1+z+z2+...+zn+...

Könnyen igazolható, hogy a fenti sor komplex számok körében is minden |z|<1-re konvergens és összege 11-z.
Mivel a kitevők éppen a természetes számok, a fenti összeg tagjait átrendezhetjük a feltételezésünk szerint létező felbontásnak megfelelően k darab végtelen mértani sorrá. Amit felhasználunk még, az az, hogy ez az átrendezés a sor összegén ‐ jelen esetben ‐ nem változtat. Így tehát ‐ felhasználva, hogy az egyes mértani sorok összege zai1-zbi, ha |z|<1, az átrendezhetőség miatt
11-z=za11-zb1+za21-zb2+...+zak1-zbk,(*)
ha |z|<1.
Ha a bi-k különbözők, akkor legyen b1<b2<...<bk és legyen ε egy primitív bk-adik egységgyök ‐ így εbk=1 és εbi1, ha i<k. Ha most zε úgy, hogy eközben |z|<1, akkor a bal oldal, illetve a jobb oldal első k-1 tagja korlátos, az utolsó, k-adik tag viszont nem az, a (*) egyenlőség tehát nem állhat fenn minden |z|<1-re. A kapott ellentmondásból következik, hogy a differenciák között vannak egyenlők, sőt az is kiderül, hogy a differenciák maximuma legalább kétszer fordul elő.