Exercițiul 355

E.355. Avem de înșirat 1010 mărgele pe un fir de ață. Se știe că șiragul trebuie să conțină mărgele de 33 culori diferite și oricare două mărgele consecutive nu trebuie să fie de aceeași culoare. Aflați în câte moduri se pot înșira mărgelele.

Test de selecție, Centrul județean de excelență Timiș, octombrie 2024; MateMaraton, 20.08.2024
Răspuns | Soluție

Răspuns: 1530.1530.

Soluție:
  • Pentru prima mărgea avem 3 opțiuni;
  • Pentru a doua mărgea avem 2 opțiuni (nu poate avea aceeași culoare ca prima mărgea);
  • Pentru a treia mărgea avem din nou 2 opțiuni (nu poate avea aceeași culoare ca a doua mărgea), și așa mai departe.

Astfel, numărul total de moduri în care putem înșira mărgelele este: 3⋅29=1536.3 \cdot 2^9=1536. Din acest total trebuie să eliminăm cele 66 aranjări care conțin doar două culori, adică:

  • 0 1 0 1 0 1 ...
  • 0 2 0 2 0 2 ...
  • 1 0 1 0 1 0 ...
  • 1 2 1 2 1 2 ...
  • 2 0 2 0 2 0 ...
  • 2 1 2 1 2 1 ...

unde prin "0" "1" și "2" am notat cele 3 culori disponibile. Deci șiragul poate fi aranjat în 1536−6=15301536 - 6 = 1530 moduri.

Obs: În baremul oficial, răspunsul este 15361536 (eronat).