Feladat: Gy.2527 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1989/november, 387 - 388. oldal  PDF  |  MathML 
Témakör(ök): Számhalmazok, Oszthatósági feladatok, Természetes számok, Gyakorlat
Hivatkozás(ok):Feladatok: 1989/január: Gy.2527

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.

Két 2-hatvány közül a kisebbik osztója a nagyobbiknak, ezért a hét darab 100-nál kisebb 2-hatvány közül semelyik kettő nem kerülhet ugyanabba a csoportba. Ez azt jelenti, hogy legalább 7 csoportra van szükség.
Ennyi viszont elegendő, ha azok az n számok kerülnek 2k-nal egy csoportba, amelyekre 2kn<2k+1 (0k6). Két ilyen szám hányadosa ugyanis ‐ ha a nagyobbikat osztjuk a kisebbikkel ‐ 1 és 2 között van és így nem lehet egész.

 

Megjegyzések. 1. Nem a fenti az egyetlen lehetséges felosztás. Ha az i-edik csoportba kerülnek azok a számok, amelyek törzstényezős felbontásában pontosan i darab prímszám szerepel és egy külön csoportba az 1, akkor éppen 7 megfelelő csoportot kapunk. A legkisebb 7-tényezős szorzat ugyanis a 27, ami 100-nál nagyobb, és egy szám valódi osztóiban kevesebb prímtényező szerepel, mint magában a számban, így az egy csoportba sorolt számok között valóban nem állhat fenn oszthatóság.
2. Hasonló gondolatmenettel igazolható, hogy az első N darab pozitív egész számot 1+[log2N] darab csoportba lehet beosztani az előírt módon, ennél kevesebb csoportba viszont nem.