Začnime v malom. Môže hľadaná množina obsahovať dve po sebe idúce čísla? Keby mohla, ich rozdiel by bol $1$. Problém je, že $1$ delí všetky prirodzené čísla, a teda bude určite deliť aj ich súčet, preto žiadne dve po sebe idúce čísla v hľadanej množine nebudú.

Poďme ďalej – môže hľadaná množina obsahovať dve čísla s rozdielom $2$? Keby áno, ich súčet by nesmel byť deliteľný dvomi. Lenže dve čísla s rozdielom $2$ sú buď obe párne, alebo obe nepárne. Keď ich sčítame, výsledok bude vždy párny. Takže nie, ani dve čísla s rozdielom $2$ v hľadanej množine nebudú.

Ďalšia rečnícka otázka asi nikoho neprekvapí – môže hľadaná množina obsahovať dve čísla s rozdielom $3$? Rozoberme si tak ako doteraz ich deliteľnosti. Ak by boli tieto čísla deliteľné tromi, aj ich súčet by bol deliteľný tromi a delil by ho potom aj ich rozdiel (ktorý je rovný $3$). Vyskúšajme zvyšok po delení trojkou rovný $1$, teda čísla $3k+1$ a $3k+4$. Ich súčet bude $6k+5$, čiže nebude deliteľný tromi. Hurá, našli sme konečne nejaké čísla, ktoré môžu byť v hľadanej množine!

V prvých dvoch odsekoch sme zistili, že najlepšie, čo vieme dosiahnuť, je množina obsahujúca každé tretie číslo z pôvodnej množiny. Každé tretie číslo znamená, že ostanú čísla vo forme $3k$, $3k+1$ alebo $3k+2$. V treťom odseku sme zahodili možnosť $3k$ a v možnosti $3k+1$ sme zistili, že po sebe nasledujúce dvojice čísel fungujú. Vedeli by ale fungovať všetky? Poďme to zistiť – keď odčítame čísla $3k+1$ a $3l+1$ ich rozdiel bude deliteľný tromi (zvyšky $1$ po delení tromi sa navzájom zrušia). Ich súčet bude $3(k+l)+2$, preto určite nebude deliteľný tromi, teda ani ich rozdielom. Podmnožina pôvodnej množiny obsahujúca čísla $3k+1$ bude preto celá vyhovovať podmienke zo zadania (rovnako viete ukázať, že bude fungovať aj podmnožina s číslami $3k+2$). Ľahko si už teraz dopočítame koľko prvkov má táto podmnožina. Je to počet všetkých prirodzených čísel zo zvyškom po delení tromi rovným $1$. Tých je $668$ a to je aj maximum, ktoré sa dá dosiahnuť.