Az 1,2,3,4, ..., 200 számokat külön csoportokba osztjuk úgy, hogy egyik csoportban se szerepeljen együtt semelyik szám sem egy tőle különböző többszörösével. Legalább hány csoportra van ehhez szükség?

Ennél a feladatnál nem a prímek felé kell elindulni.

Próbáld így:

Sorban haladunk a számokkal és ha az adott csoportban az már többszörös lenne, akkor azzal a számmal új csoportot indítasz.

Nyilván az 1 külön csoport lesz, mert minden szám a többszöröse.

Tehát a 2. Csoport első tagja a 2, mehet mellé a 3, de a 4 már nem, tehát a 3. Csoport a 4-essel indul. Abban lesz 4,5,6,7, de a 8 már egy új csoport.

Így kell haladni 200-ig.

Ha jól csinálod, akkor 8 csoport elég.

Mivel 1-es elég sokat elmondott már a megoldásból, leírok egy teljes bizonyítást. Felteszem, hogy a kérdező úgysem fog rájönni. Ha mégis lett volna esély, akkor bocs.

- Az első csoportba kerül az 1-es.

- A másodikba az összes prím.

- A harmadikba az összes prím kéttényezős szorzata, vagyis p1*p2, ahol p1 és p2 lehet egyforma is.

- Az n-edikbe az összes prím n tényezős szorzata. Ez biztosítja, hogy egy csoportban ne legyen 2 olyan szám, amiből az egyik osztója a másiknak. Mert ez azt jelentené, hogy az osztó törzstényezős felbontása része az osztandó törzstényezős felbontásának, ami lehetetlen. Ugyanis mindkettőben ugyanannyi tényező van, de van közöttük különböző. Ezért az egyik nem tartalmazhatja a másikat.

- Elegendő-e 8 csoport? Azaz van-e olyan 200 alatti szám, aminek a törzstényezős felbontása több, mint 7 tényezőből áll? A legkisebb prímből 8 darab szorzata (2^8) nagyobb, mint 200, ezért nincs.

- 8 csoport viszont biztosan kell, mert a 2^n számok, ahol n=0, ..., 7 nem kerülhetnek egy csoportba.