Motto: Repede este același lent, dar fără întreruperi (proverb japonez)
C. Maşina de amestecat cărţi
Să presupunem că avem o maşină de amestecat cărţi, care ia cărţile 1, 2, 3,.., 52 şi le scoate în ordinea 1, 27, 2, 28, 3, 29,.., 26, 52.
Dacă repunem în maşină pachetul de cărţi amestecat şi repetăm procedeul, după 8 iteraţii vom vom obţine (pentru prima oară) pachetul în forma sa iniţială.
Dacă maşina de amestecat scoate cărţile în ordinea 27, 1, 28, 2, 29, 3,.., 52, 26, atunci sunt necesare 52 tururi de amestec pentru a obţine pachetul în forma sa iniţială.
Să presupunem că putem programa ordinea de amestecare a cărţilor în maşină. Care este cel mai lung şir posibil de tururi care poate fi realizat pentru a reface pachetul de cărti ?
Sursă: Macalester POTW, problema 930 (martie 2001)
Logic
Va rog sa ne detaliati ce inseamna sa programam ordinea de amestecare a cartilor in masina.
Cartile vor fi tot de la 1 la 52 si probabil ca le vom imparti in doua grupuri pentru a le amesteca masina, dar in ce ordine le mai poate amesteca?
Programare inseamna fixarea unei permutari de 52 elemente pe care o va face masina.
Daca x este pachetul de carti la intrare, la iesire va fi perm(x); apoi perm(perm(x)) etc.
Practic trebuie gasita o permutare de ordin maxim posibil.
(ordinul unei permutari fiind numarul de aplicari pana se ajunge din nou la sirul initial de 52 elemente).