Pe un mal al unui râu se afla containere de mase (in tone)
1, 2, 3, 4, 5.

Ele trebuie transportate toate pe celalalt mal. (In mai multi pasi.)
Un vapor complicat le transporta, dar la fiecare transport de la un mal la altul exista anumite conditii.

(1) La fiecare pas pot fi transportate cel mult doua containere pe celalalt mal.
(2) La primul pas, vaporul poate fi calibrat sa transporte orice masa.
(3) De al un pas la altul incarcaturile sunt fie egale, fie difera printr-o unitate. (Recalibrarea nu permite o diferenta mai mare.)

Care este numarul minim de transporturi / de pasi necesari pentru a duce cele cinci containere de pe un mal pe celalalt?

Nota:
Pentru incalzire, cititorul poate sa isi puna "probleme asemanatoare":

(A) "Aceeasi problema" pentru "cazul N=4", cel in care avem de transportat masele
1, 2, 3, 4.

(B) O alta problema este cea cu N=3...

(C) O alta problema este cea legata de transportul maselor 2, 3, 4, 5.

(D) O alta problema este cea legata de transportul maselor 2, 3, 4, 5, 6.

Nota:
Aceasta problema este una "nestructurala", solutia rog a fi doar atunci cautata cand se identifica o oarecare structura care permite (cât de cât) o cautare dupa jaloane "cunoscute).

"Pas" înseamnă transportul de pe malul A pe malul B, sau și de pe malul B pe A? (cam ca în puzzle-ul cu lupul, capra și varza)

Sanatate si toate cele bune!

Un pas este
- fie trecerea de la malul A la malul B,
- fie trecerea de la malul B la malul A.

Sa zicem ca se pleaca de pe malul A, cu toate masele, 1,2,3,4,5, pe scurt A(12345), cand in acelasi timp in B avem "lista vida", B(), atunci in exemplul urmator numaram pasii dupa cum urmeaza,

A(12345), B() -> A(235), B(14) este un pas,
primul, se transporta 14, suma 5, am ajuns cu vaporul in B.

A(235), B(14) -> A(2345), B(1) este un pas, al doilea, se transporta 4 inapoi, suma 4, am ajuns cu vaporul in A inapoi.

A(2345), B(1) -> A(45), B(123) este un pas, al treilea, se transporta 23, suma 5, am ajuns cu vaporul in B.

(Putem acum sa transportam in A in total o incarcatura totala cu doua obiecte de suma 4 sau 5 sau 6, suma 6 este exclusa, suma 5 se poate obtine doar din 23, regres, altfel doar suma 4, obtinuta doar din 13.)

Da, este o problema de tip "lupul, capra si varza", doar putin mai sofisticata. Problema mi-a fost comunicata de catre tatal unei eleve de clasa a XII-a (Frankfurt, Germania), nu am sursa exacta a problemei, se pare ca era inglobata intr-un sir de probleme asemanatoare implementate ca un joc pe telefonul mobil in versiunea cu piesele 1,2,3,4. (Fara 5.)

Un avantaj al problemei este faptul ca ea este deschisa pentru orice nivel.
Probabil ca si la nivel de clasa a patra se percepe "progresul" sau "regresul" unui pas sau unui lant de pasi, exact simtul care pune stampila de matematician pe un matematician.
Este asa sau intr-o varinata mai "ascutita" (de exemplu cu mai multe obiecte ce pot fi transportate) o problema ce se poate propune in concursurile de matematica si de informatica de orice nivel. Orice mica schimbare a "jocului" schimba problema... Lucrurile se pot ascuti "combinatoric" mai departe daca intrebam cate drumuri diferite realizeaza numarul minimal de pasi.

Trebuie clarificat primul pas. Inițial se întelege că numai UNA dintre mase poate fi trecută peste apă, dar exemplul dat în postul imediat următor arată că DOUĂ mase sunt trecute. În acest caz, de ce nu am transporta TOTUL într-o singură trecere?

[Citat] Trebuie clarificat primul pas. Inițial se întelege că numai UNA dintre mase poate fi trecută peste apă, dar exemplul dat în postul imediat următor arată că DOUĂ mase sunt trecute. În acest caz, de ce nu am transporta TOTUL într-o singură trecere?

Cer scuze, incerc sa reformulez, folosind cele din postarea initiala.
Problema are de-a face cu containere.
Containerele au mase diferite, 1,2,3,4,5.

O prima conditie este cea de a muta la fiecare pas cel mult doua containere.

Acum desigur, daca nu impunem nici o conditie asupra maselor transportate, problema nu depinde de ele. Introducem o astfel de constrângere, cerem ca de la un pas la altul diferenta de mase transportate

- masa totala a acelui singur sau a celor doua containere transportate la pasul anterior si
- masa totala a acelui singur sau a celor doua containere transportate la pasul prezent

sa difere doar printr-o unitate.

Trebuie sa trimit, dar revin.

23 de mutări:

Dar nu am o soluție matematică. Ideea e de a forma un graf și a rezolva apoi o problemă de drum minim. Vârfurile grafului indexează mutările posibile, iar muchiile sunt reprezentate de două mutări consecutive care satisfac regulile impuse.