Rezolvare:

Solutia 1 (Szabo Zoltan):

          Pornim de la o permutare si incercam sa adaugam printr-un numar minim de cifre toate permutarile inca neadaugate. Adaugarea unei noi cifre se realizeaza cu scopul de a salva cat mai multe din ultimele cifre generate.

          Am notat toate cele 24 de permutari de 4 numere, si fiind atent sa nu repet o permutare de doua ori inutil am ajuns urmatoarele trei solutii de baza, dintre care doar prima are lungime minima de 7+5+5+6+5+5=33.

123412314231243121342132413214321     - solutia buna

1234123142312431214321413241342134  - solutie fara restrictia de lungime minimala

12341231423124312413241342134321432   - solutie fara restrictia de lungime minimala

Numarul solutiilor distincte: putem incepe cu 24 de permutari distincte, fiecare generand cate o solutie diferita de celelalte. Deci numarul solutiilor distincte este 4!=24.

  1. 123412314231243121342132413214321

  2. 124312413241234121432142314213421

  3. 132413214321342131243123412314231

     ...

24. 432143241324312434213423142341234

 

Soluţia 2 (Ştefan Gaţachiu):

          Cel mai scurt șir, cu lungimea 33, este 123412314231243121342132413214321

          care conține permutările în următoarea ordine, de la stânga la dreapta („sărind” acolo unde este cazul peste una sau două poziții):

1234, 2341, 3412, 4123, 2314, 3142, 1423, 4231, 3124, 1243, 2431, 4312, 2134, 1342, 3421, 4213, 1324, 3241, 2413, 4132, 3214, 2143, 1432, 4321.

 

Soluţia 3 (Ady Nicolae): Va fi postata in curand