Katrs naturāls skaitlis no \(1\) līdz \(2005\) ieskaitot nokrāsots vienā no \(n\) krāsām. Ir zināms: ja \(a,\ b\) un \(c\) ir dažādi skaitļi, \(a\) dalās ar \(b\) un \(b\) dalās ar \(c\), tad \(a,\ b\) un \(c\) nav visi nokrāsoti vienā un tai pašā krāsā. Atrast mazāko iespējamo \(n\) vērtību.
Atbilde: \(6\) krāsas.
Risinājums. Nekādi \(3\) no \(11\) skaitļiem \(1;\ 2;\ 4;\ 8;\ 16;\ 32;\ 64;\ 128;\ 256;\ 512;\ 1024\) nevar būt nokrāsoti vienā krāsā. Tātad krāsu skaits ir vismaz \(11:2=5,5\), tātad vismaz \(6\).
Ar \(6\) krāsām var iztikt. Ievērosim, ka neviens no apskatāmajiem skaitļiem nesatur vairāk par \(10\) pirmreizinātājiem, jo \(2^{11}=2048>2005\). Krāsojam \(1.\) krāsā vieninieku un pirmskaitļus; otrajā krāsā divu un triju pirmskaitļu reizinājumus (varbūt reizinājumā pirmskaitļi atkārtojas), trešajā krāsā četru un piecu pirmskaitļu reizinājumus, utt.