Ki lehet-e választani az első 100 pozitív egész szám közül 51-et úgy, hogy nincs köztük olyan számpár, ahol az egyik többszöröse a másiknak?

Általánossá is lehet tenni a skatulyaképzési eljárást:

Legyen 50 skatulya az 51-100 számokkal. 50 db. Ha a skatulyában levő szám osztható 2-vel, akkor rakjuk mellé a felét, negyedét, nyolcadát, stb., amíg egészszámot kapunk.

Minden 1-50 tartományba tartozó k számnak van olyan 2^n-szerese, ami az 51-100 tartományba esik. Ezért be fog kerülni egy skatulyába. Mert 2k nem lehet nagyobb 100-nál. És ha 2k kisebb 50-nél, akkor szorozzuk meg még 2-vel. És ezt ismételjük, amig nem esik az 51-100 tartományba.

Ha az összes számot elraktuk, akkor minden skatulyában k*2^n típusú számok lesznek. (n >= 0) Ezekből nem lehet 2-őt kiválasztani, mert k*2^i mindig osztható k*2^j-vel, ha i>j.

Így lehet az én 19-es megoldásom alapján általános módon skatulyákat képezni.

"És ha 2k kisebb 50-nél,..." helyett

És ha 2k kisebb 51-nél,...

Szuperek vagytok! Összefoglalom a lényeget :D

Minden természetes szám felírható egy páratlan szám és egy kettőhatvány szorzatatként. Képezhetők tehát az alábbi diszjunkt halmazok:

1, 2, 4, 8, 16 ...

3, 6, 12, 24, 48 ...

5, 10, 20, 40, 80 ...

7, 14, 28, 56, 112 ...

9, 18, 36, 72, 144 ...

.

.

.

Az első száz egész szám "lefedhető" 50 ilyen halmazzal, hiszen 1-től 100-ig 50 páratlan szám van. 51 számot kell választani, tehát a skatulyaelv miatt lesz két szám, ami ugyanabba a halmazba esik. A kisebbik osztani fogja a nagyobbat, mert a halmazok eleve így vannak megkonstruálva. QED