Feladat: F.2880 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Csörnyei Marianna 
Füzet: 1992/április, 157 - 158. oldal  PDF  |  MathML 
Témakör(ök): Konstruktív megoldási módszer, Számtani sorozat, Számhalmazok, Feladat
Hivatkozás(ok):Feladatok: 1991/december: F.2880

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.

Jelöljük Sd,a-val azt a számtani sorozatot, amelynek differenciája d és első eleme a (például S5,2=(2,7,12,17,...)).
Könnyű ellenőrizni, hogy az

S2,0,S3,0,S4,1,S6,1,S12,11(1)
sorozatok együttvéve az összes pozitív egész számot tartalmazzák. Valóban, S2,0 tartalmazza mindazokat a pozitív egészeket, amelyek 12-vel osztva 0,2,4,6,8 vagy 10 maradékot adnak; S3,0 tartalmazza azokat a számokat, amelyek 12-vel osztva 0,3,6, vagy 9 maradékot adnak; S4,1 azokat, amelyek 1-et, 5-öt vagy 9-et; S6,1 azokat, amelyek 1-et vagy 7-et; végül S12,11 azokat, amelyek 12-vel osztva 11 maradékot adnak. Mivel mindegyik lehetséges maradék szerepelt legalább egyszer, a felsorolt öt sorozat valóban tartalmazza az összes pozitív egészt. A baj csak az, hogy az egyik sorozat differenciája a 2.
Az (1)-ben szereplő sorozatok segítségével megadunk néhány sorozatot, amelyek lefedik az összes páros számot, és megadunk néhány további sorozatot, amelyek a páratlan számokat tartalmazzák.
Tekintsük a következő sorozatokat:
S32,0,S48,0,S64,16,S96,16,S192,176,S16,8,S8,4,S4,2.(2)
Az első öt éppen az (1)-ben szereplő sorozatok 16-szorosa; ezek tehát a 16-tal osztható pozitív egészeket tartalmazzák. Az S16,8 sorozat azokat a természetes számokat tartalmazza, amelyek 8-cal oszthatók, de 16-tal nem; az S8,4 azokat, amelyek 4-gyel oszthatók, de 8-cal nem; végül az S4,2 azokból a pozitív páros számokból áll, amelyek 4-gyel nem oszthatók. A (2)-ben megadott sorozatok tehát az összes páros számot tartalmazzák.
Tekintsük ezután a következő sorozatokat:
S3,1,S6,5,S9,3,S18,15.(3)

Megmutatjuk, hogy ezek minden olyan (pozitív) páratlan számot tartalmaznak, amely nem osztható 9-cel.
Az S3,1 és S6,5 tartalmazzák a 3-mal nem osztható számokat (ha egy páratlan szám 3-mal osztva 2 maradékot ad, akkor 6-tal osztva 5-öt ad maradékul, ezért az ilyeneket tartalmazza S6,5), míg S9,3 és S18,15 együttesen tartalmazzák azokat a 3-mal osztható páratlan számokat, amelyek 9-cel nem oszthatók, hiszen az ilyen számok 18-cal osztva csak 3 vagy 15 maradékot adhatnak.
Végül a 9-cel osztható páratlan számokat a következő sorozatok tartalmazzák:
S12,9,S36,27,S72,45.(4)

Egy 9-cel osztható páratlan szám ugyanis 72-vel osztva 9,27,45 vagy 63 maradékot ad.
Az S36,27 tartalmazza azokat, amelyek 27 vagy 63 maradékot adnak; az S72,45 azokat, amelyek 45-öt; végül az S12,9 az összes olyan számot tartalmazza, amely 72-vel osztva 9 maradékot ad.
A (2), (3) és (4) pontokban felsorolt sorozatok tehát az összes pozitív egész számot tartalmazzák. A differenciák szerint felsorolva:
S3,1;S4,2;S6,5;S8,4;S9,3;S12,9;S16,8;S18,15;S32,0;S36,27;S48,0;S64,16;S72,45;S96,16;S192,176.



 
Megjegyzések. 1. Természetesen sok más megoldás is létezik (például kicserélhetjük S192,176-ot S24,16-ra). Egy másik megoldás (Csörnyei Marianna dolgozata alapján):
S3,0;S4,0;S5,0;S6,1;S8,2;S10,1;S12,5;S15,2;S20,19;S24,22;S30,23;S40,14;S60,38;S120,86.



2. A feladattal kapcsolatban sok nevezetes megoldatlan kérdés ismert; például lehet-e az összes differencia páratlan? Lehet-e a legkisebb differencia akármilyen nagy? (Ez utóbbi Erdős Pál problémája.)
3. Ha azt is megköveteljük, hogy a sorozatok diszjunktak legyenek, akkor a feladatnak nincs megoldása. Erről részletesebben a KöMaL 1986/4. számában, a 154. oldalon olvashatnak az érdeklődők.