Apskatām naturālos skaitļus no \(1\) līdz \(100\) ieskaitot. Kādu lielāko daudzumu no tiem var izvēlēties tā, lai nekādi divi izvēlētie skaitļi nedalītos viens ar otru un katriem diviem izvēlētajiem skaitļiem lielākais kopīgais dalītājs būtu lielāks par \(1\)?
Atbilde: \(25\) skaitļus.
Risinājums. Apskatīsim skaitļus \(52;\ 54;\ 56;\ \ldots;\ 96;\ 98;\ 100\). Tie visi dalās ar \(2\) un neviens nedalās ar otru, jo pat lielākā skaitļa dalījums ar mazāko ir \(\frac{100}{52}<2\), tātad nekādu divu apskatāmo skaitļu dalījums nav naturāls skaitlis.
Pierādīsim, ka vairāk par \(25\) skaitļiem, kas apmierina uzdevuma prasības, izvēlēties nevar. Pieņemsim, ka kopa \(M\) ir kopa ar maksimālo skaitļu skaitu tajā. Ja eksistē tāds \(x \in M\), ka \(x \leqslant 50\), tad \(2x \notin M\); mazāko no šādiem \(x\) var aizstāt ar \(2x\). (Viegli pārbaudīt, ka kopai \(M\) izvirzāmās prasības saglabājas.) Ar galīgu skaitu gājienu \(M\) varam pārveidot par \(M_{1}\), kurā visi skaitļi ir lielāki par \(50\), bet elementu ir tikpat, cik kopā \(M\). Ja \(M_{1}\) būtu vairāk nekā \(\mathbf{25}\) elementi, tad vismaz divi no tiem atrastos vienā no \(25\) pāriem \((51; 52),\ (53; 54),\ (55; 56),\ \ldots,\ (97; 98),\ (99; 100)\). Bet tā ir pretruna, jo diviem skaitļiem, kas atšķiras viens no otra par \(1\), lielākais kopīgais dalītājs ir \(1\).