Exercițiul 693

E.693. Fiecare număr din șirul 2,3,4,…,502,3,4,\ldots,50 se colorează cu câte o culoare, respectând regula: dacă un număr are o anumită culoare, atunci orice divizor al său are aceeași culoare. Care este numărul maxim de culori care pot fi utilizate?

ONM 2012
Art, Matematică pentru excelență, 20/49
Răspuns | Soluție

Răspuns: 77 culori.

Soluție:

Colorăm cu albastru numărul 2.2. Orice număr par îl are pe 22 ca divizor, deci toate numerele pare de la 22 la 5050 sunt albastre.
Dacă xx este un număr impar, cu x≤25,x \leq 25, atunci 2≤2x≤50,2\leq 2x \leq 50, deci 2x2x este albastru. Cum xx este un divizor al lui 2x,2x, înseamnă că și xx va fi albastru.

Mai rămân de analizat numerele impare mai mari decât 25.25. Acestea pot fi:

  • Numere compuse: 27,33,35,39,45,4927,33,35,39, 45, 49 - au un divizor albastru, deci vor fi albastre.
  • Numere prime: 29,31,37,41,43,4729, 31,37,41,43,47 - nu au niciun divizor mai mic sau egal cu 50,50, deci pot avea culori diferite.

Așadar, numărul maxim de culori este 1+6=7.1+6=7.