Naturālie skaitļi no \(1\) līdz \(2008\) ieskaitot jāsadala grupās tā, lai izpildītos sakarība: ja \(a\) dalās ar \(b\) un \(b\) dalās ar \(c\) (\(a,\ b,\ c\) - dažādi naturāli skaitļi), tad \(a,\ b\) un \(c\) visi nepieder vienai un tai pašai grupai. Kāds ir mazākais iespējamais grupu skaits?
Atbilde: \(6\) grupas.
Minimalitātes pierādījums. Apskatīsim \(11\) skaitļus
\(1; 2; 4; 8; \ldots; 1024=2^{10}\). Ja grupu skaits nepārsniedz \(5\), tad ir
grupa, kas satur \(3\) no šiem skaitļiem (jo \(11>5 \cdot 2\)) \(a
Piemērs. Nosauksim par naturāla skaitļa \(n\) augstumu \(h(n)\) to kāpinātāju summu, ar kuriem \(n\) satur dažādus pirmreizinātājus (piemēram, \(h(8)=h\left(2^{3}\right)=3;\ h(10)=h\left(2^{1} \cdot 5^{1}\right)=2\); \(h(1)=0\)). Acīmredzot, ja \(x\) dalās ar \(y\) un \(x>y\), tad \(h(x)-h(y) \geq 1\). Mūsu apskatāmajiem skaitļiem \(n, 1 \leq n \leq 2008, h(n)<11\) (jo tie visi mazāki par \(2^{11}=2048\)). Iekļaujam \(1.\) grupā skaitļus ar \(h=0\) un \(h=1\); otrajā - ar \(h=2\) un \(h=3; \ldots\); sestajā - ar \(h=10\). Ja \(a \vdots b\) un \(b \vdots c\), tad \(h(a)-h(c) \geq 2\), tātad \(a\) un \(c\) nav vienā grupā.