Feladat: B.4161 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Balla Attila ,  Baranyai Zoltán ,  Bodor Bertalan ,  Csere Kálmán ,  Deák Zsolt ,  Éles András ,  Korondi Zénó ,  Kunos Vid ,  Matyuska Péter ,  Mészáros András ,  Nguyen Milán ,  Szabó Attila ,  Zsakó András 
Füzet: 2010/április, 215. oldal  PDF file
Témakör(ök): Feladat, Halmazelmélet, Természetes számok
Hivatkozás(ok):Feladatok: 2009/február: B.4161

Tegyük föl, hogy a természetes számok halmazának véges sok pozitív elemét elhagyva egy olyan S halmazt kaptunk, amely zárt az összeadásra. Legyen az S egyik eleme k. Hány olyan eleme van S-nek, amiből k-t kivonva S-hez nem tartozó számot kapunk?

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.

Megoldás. Tekintsük a természetes számok k szerinti maradékosztályait. (Egy x szám az i-edik (0ik-1) maradékosztályban van, ha k-val osztva i maradékot ad.) Mivel S-et a természetes számok halmazából véges sok elem elhagyásával kaptuk, az egyes maradékosztályokból is csak véges sok elemet hagytunk el. Tehát S a k szerinti maradékosztályok mindegyikéből tartalmaz elemet.
Válasszuk ki minden maradékosztályból a legkisebb elemet, melyet az i-edik maradékosztály esetén jelöljön xi. Mivel S zárt az összeadásra, azért S-nek eleme xi+k, xi+2k stb. Az így kapott elemek bármelyikéből k-t kivonva tehát az i-edik maradékosztály és így S egy eleméhez jutunk. Egyedül xi-kS.
Mivel S-et k darab maradékosztályra osztottuk, így k darab olyan eleme van, amiből k-t kivonva S-hez nem tartozó számot kapunk.