Problema 2, Olimpiada Nationala de Matematica 2012

[mircea.lascu]

Problema 2. Fiecare element al multimii $\{2,3,4,...,50\}$ se coloreaza cu cate o culoare, respectand regula: daca un numar are o anumita culoare, atunci orice divizor al sau are aceeasi culoare. Care este numarul maxim de culori care pot fi utilizate?

[Anghelina Ion]

Presupunem ca nr.2=galben.
Atunci nr: {2,4,6,8,...,50}-25 nr. sunt galbene.
Dar daca nr. 6=galben$\Rightarrow$3-galben$\Rightarrow$ca numerele {3,6,9,...,48}- galbene.
Dar daca nr. 45=galben$\Rightarrow$5-galben$\Rightarrow$ numerele {5,10,15,20,...,50} galbene.
Analog pentru 14,7 si nr. {7,14,21,28,...,49};
Insa numerele {29,31,37,41,43,47}-6 numere nu sunt galbene deci au 6 culori diferite.
Astfel in total sunt 7 culori