Soluţie (Szabo Zoltan):

Să observăm că soluția cu N premii întotdeauna este 1+1+1+...+1.

Pentru N-1 echipe premiate soluția se poate scrie unic 1+1+...+1+2. Rezultă că există obligatoriu o echipă formată de două persoane.

Pentru N-2 echipe premiate soluția are două posibilități (1+1+...+1+3 sau 1+1+...+2+2). În primul caz trebuie să avem câte o echipă de 2 respectiv 3 membri, în al doilea caz trebuie să avem două echipe de câte 2 membri. Evident că pentru N maxim este mai convenabilă o combinație 2+3 decât o combinație 2+2.

Păstrând modul de gândire, dar fără să intrăm prea mult în amănunte, observăm ce N maxim se obține folosind elementele șirului lui Fibonacci: 

1,1,2,3,5,8,13,21,34,56.

Iar cele 56 de moduri de premiere se vor prezenta astfel:

1.     56=

2.     56=21+34

3.     56=8+13+34

4.     56=3+5+13+34

5.     56=1+2+5+13+34

6.     56=1+1+1+5+13+34

7.     56=1+1+1+2+3+13+34

8.     56=1+1+1+1+1+3+13+34

9.     56=1+1+1+1+1+1+2+13+34

10.                  56=1+1+1+1+1+1+1+1+13+34

11.                  56=1+1+1+1+1+1+1+1+5+8+34

12.                  56=1+1+1+1+1+1+1+1+2+3+8+34

13.                  56=1+1+1+1+1+1+1+1+1+1+3+8+34

14.                  56=1+1+1+1+1+1+1+1+1+1+1+2+8+34

15.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+8+34

16.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+3+5+34

17.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+1+2+5+34

18.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+5+34

19.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+2+3+34

20.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+3+34

21.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+2+34

22.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+34

23.                  56=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+13+21

24.                  ...

               56=1+1+1+1+1+ ...+1

Deci N=56 este numărul maxim ce se poate obține cu 8 echipe.

Pentru exemplul din enunț, pentru 4 echipe, N maxim este 8 echipele având numărul de membri: (2,3,5,8).

 

Aurel Ionescu a dat o soluţie apropiată.

 

Totuşi, deşi pentru 4 echipe soluţia optimă este dată de şirul Fibonacci, pe cazul general o soluţie mai bună este dată de secvenţa 2^k+1 (ajustînd corespunzător ultimul termen); în acest caz (8 echipe):

2, 3, 5, 9, 17, 33, 65, 70.

1:      70=70

2:      70=65+5

3:      70=65+3+2

4:      70=33+17+17+3

5:      70=33+17+9+9+2

6:      70=33+17+5+5+5+5

7:      70=33+17+5+5+5+3+2

8:      70=33+17+5+5+3+3+2+2

Soluţia optimă (dată pe site-ul Ponder This) este însă una euristică;

2, 3, 5, 8, 16, 24, 54, 78

 

1:      78=78

2:      78=54+24

3:      78=54+16+8

4:      78=54+16+5+3

5:      78=54+16+3+3+2

6:      78=24+24+16+8+3+3

7:      78=24+16+16+8+8+3+3

8:      78=16+16+16+8+8+8+3+3