Soluţii corecte: Zoltan Szabo, Jean Henry Berevoescu, Traian Dajma, Alexandru Cohal, Ioan Scutaru.

Nota: din numarul mare de rezolvitori care au rezolvat altceva (spre exemplu imposibilitatea MI -> MU), deducem ca poate enuntul problemei nu a fost suficient de clar. Insa au existat rezolvitori care au dat raspunsul asteptat fara nicio precizare suplimentara.

 

Alexandru Cohal:

1) Dacă secvența dată s este de forma Mx (unde x este o secvență oarecare) sau poate fi redusă la forma Mx (e.g. UUMxUIIIMxIIIUMx), atunci se poate obține o secvență de lungime infinită prin aplicarea succesivă a regulii 2.

2) Dacă secvența dată s este de forma xI (unde x este o secvență oarecare), atunci se poate obține o secvență mai lungă cu 1 prin aplicarea regulii 1.

3) Dacă secvența dată s este de oricare altă formă, atunci nu se poate crește lungimea prin aplicarea regulilor date.

 

Zoltan Szabo:

Intrucat ne intereseaza lungimea maxima a unei secvente, nu vom folosi regulile 3 și 4, acestea scurtând lungimea secvenței.

Regula 1 mărește lungimea secvenței de la n la n+1. Condiția este ca aceasta să se termine inițial cu I, apoi se vatermina cu U și regula nu se mai poate repeta.

Conform regulii 2 o secvență de lungime n care începe cu litera M, având forma Mx, se poate transforma în Mxx. La rândul ei secvența Mxx se transformă în Mxxxx, ș.a.m.d. putem obține M(x) unde am notat cu (x) secvența concatenată x de 2p ori. Dar p nu are limită maximă, deci lungimea secvenței poate fi mai mare decât orice limită L impusă (L număr natural), cu condiția că secvența începe cu literea M.

Dacă secvența începe cu litera M și se termină cu litera I, atunci o singură dată la sfârșitul secvenței putem adăuga un U, și regula de mai sus rămâne valabilă cu secvența de lungime cresciută cu 1. Astfel cazul Mx, dacă explicităm ultimul caracter are trei forme:

       a. MxM, secvența finală va fi M(xM)  (secvența se repetă de 2p ori)  (x fiind cu lungime mai mare sau egală cu 0)

       b. MxU, secvența finală va fi M(xU)  (secvența se repetă de 2p ori)  (x fiind cu lungime mai mare sau egală cu 0)

       c. MxI, secvența finală va fi M((xI)U)  (secvența interioară se repetă de 2p ori iar cea exterioară de 2q ori)  (x fiind cu lungime mai mare sau egală cu 0)

  Pentru toate celelelate reguli secvența inițială este cea de lungime maximă cu lungimea n inițială fără modificări.

 

Jean Henry Berevoescu:

Pentru ca secventa trebuie sa fie de cel putin doua caractere (n > 1), sa analizam cel mai simplu caz: n = 2.

Notatie: caracterul ⇒ semnifica “genereaza”, caracterul ♦ arata sfirsit de generare, iar caracterul … arata o serie oarecare de pasi similari sau continuare la infinit (cind este la sfirsitul seriei de transformari).

  1. Primul caracter I:
    1. II ⇒IIU♦
    2. IU♦
    3. IM♦
  2. Primul caracter U:
    1. UI ⇒UIU♦
    2. UU⇒(null)
    3. UM♦
  3. Primul caracter M:
    1. MI:
      1. MI⇒MIU⇒MIUIU⇒MIUIUIUIU⇒…
      2. MI⇒MII:
        1. MI⇒MII⇒MIIII⇒MUI⇒MUIUI⇒MUIUIUIUI⇒…
        2. MI⇒MII⇒MIIII⇒MIIIIIIII⇒…
    2. MU
      1. MU⇒MUU⇒M♦
      2. MU⇒MUU⇒MUUUU⇒MUUUUUUUU⇒…
    3. MM⇒MMM⇒MMMMM⇒MMMMMMMMM⇒…

Este evident ca din cele patru reguli, doar primele doua genereaza secvente mai lungi decit originea, iar intre variantele structurii secventei, cele incepute cu U sau I dau variante finite. Singura structura care genereaza secvente mai lungi este cea in care secventele incep cu M.

Avind in vedere ca problema cere maximizarea lungimii secventei, putem neglija regulile 3 si 4 (care duc la reducere in lungimea secventei).

In cazul general, secventa x se poate scrie: x = qy, unde q apartine setului {U, I, M}, iar y este o secventa de lungime mai mare sau egala cu 1 (secventa x trebuie sa fie strict mai mare decit 1, conform enuntului problemei).

Rescriem cele trei cazuri de mai sus:

  1. Primul caracter I:
    1. Iy: seria y se termina in I (y=zI) sau nu se termina in I
      1. IzI ⇒IzIU♦
      2. Iy♦
  2. Primul caracter U:
    1. Uy: seria y se termina in I (y=zI) sau nu se termina in I
      1. UzI ⇒UzIU♦
      2. Uy♦
  3. Primul caracter M: y se termina in I (y=zI) sau nu se termina in I:
    1. MzI⇒MzIU⇒MzIUzIU⇒…⇒M[(2k)zIU]…
    2. My⇒Myy⇒…⇒M[(2k)y]…

Unde constructia de genul M[(2k)y] reprezinta secventa: M urmat de secventa y luata de 2k ori, unde k este numarul de pasi (generari), iar k creste nelimitat.

Primele doua cazuri (primul caracter I sau U) dau lungimi maxime de n + 1 (cazurile in care sint terminate in I), altfel nu au cum sa genereze secvente mai lungi si ramin la lungimea n.

Cazul #3 (cu secvente incepind cu M) dau lungimi din ce in ce mai mari, in care la fiecare pas (k), secventa are lungimea:

  1. Cind secventa x se termina in I: nk = 1 + 2k * n
    1. Nota: pasul k este de fapt pasul (k + 1), avind in vedere ca primul pas este cel in care zI duce in zIU.
  2. Cind secventa x nu se termina in I: nk = 1 + 2k * (n – 1)