Legfeljebb hány számot lehet kiválasztani?

Ez cseles feladat. Nem tudom, a bizonyításra hogyan lehet rájönni.

Egy bizonyítás lehet az, hogy létrehozol 20/2 skatulyát úgy, hogy ha két szám egy skatulyába esik, akkor egymás osztói legyenek.

Ha lehet, akkor legyenek a skatulyák diszjunktak, akkor még jobb.

Vagyis, ha sikerül 20/2 színnel színezni a számokat úgy, hogy azonos színûek osszák egymást, akkor nyertél.

Biztos, hogy a felsõ 10 szám különbözõ színt kell kapjon (a "kell" szót arra használom, hogy ha megsúgják a bizonyítás néhány részletét, a maradékot neked kell kipótolnod, akkor mi szükséges a bizonyításon belül), az alsó számokat szeretnéd kiszínezni valahogy úgy, hogy a felsõ számokkal klappoljon a színezés.

Egy jó színezés az, hogy minden alsó szám megkapja annak a felsõ számnak a színét, aki neki kettõhatványszorosa.

Másképp: két szám legyen egyszínû ha megegyezik a legnagyobb páratlan osztójuk. Megint másképp ha egy szám "kék", akkor legyen a szám fele is kék. (Minden színre.) Így kiterjed a fönti számok színezése alulra.

Van tehát 10 (diszjunkt) skatulyád (azaz egy 10-színezésed), tehát 10-nél többet nem lehet kiválasztani. (Mûködik tetszõleges páros N-re 20 helyett.)