Un automat pleaca cu valoarea initiala 1 (numar natural) afisata pe monitor.
la fiecare pas / joc solitar, automatul aplica una din urmatoarele operatii pe numarul natural afisat:

- il inmulteste cu 5, plecand de la x ajunge deci la 5x
- il inmulteste cu 2, plecand de la x ajunge deci la 2x
- il imparte fara rest cu 2, plecand de la x ajunge deci la [x/2]
- il imparte fara rest cu 5, plecand de la x ajunge deci la [x/5]

(Mai sus am notat cu [ u ], expresia / paranteza Gauss a lui u, partea intreaga a numarului real u.)

Se poate ca dupa exact 2011 pasi automatul sa afiseze numarul 2011?


Cu alte cuvinte, exista un sir x(n) de numere naturale cu proprietatile

x(0) = 1 ,

x(n+1) este un element al multimii { 5x(n), 2x(n), [x(n)/2], [x(n)/5] } pentru orice n natural nenul.

x(2011) = 2011 ?
Daca exista sa se dea explicit un exemplu.

Un posibil mod de a ajunge de la 1 la 2011 in cativa pasi este urmatorul:

1
- inmultire cu 5, operatie repetata de trei ori
125
- impartire cu rest la 2
62
- impartire (cu/fara) rest la 2
31
- inmultire cu 5
155
- impartire cu rest la 2
77
- inmultire cu 2, operatie repetata de trei ori
616
- impartire cu rest la 5
123
- inmultire cu 2, operatie repetata de patru ori
1968
- impartire cu rest la 5
393
- inmultire cu 2, operatie repetata de patru ori
6288
- impartire cu rest la 5
1257
- inmultire cu 2, operatie repetata de trei ori
10056
- impartire cu rest la 5
2011

Pentru a incheia problema si a vedea ca putem ajunge la 2011 din exact 2011 pasi , observam ca putem insera la inceput si la sfarsit "cat cuprinde" perechi de operatii cu rezultat neschimbat inainte si dupa aplicarea perechii de operatii, de exemplu (inmultire cu 2, impartire cu 2). La inceput putem de exemplu insera de mai multe ori 1 > 2 > 1 > 2 > ...

In acest mod ajungem la 2011 daca numarul de pasi de mai sus este impar.
Nu vreau sa-i numar, mai bine observ ca daca vrem sa schimbam paritatea plecand cu acelasi 1 (dupa un numar impar de pasi), putem insera la inceput secventa
1 > 5 > 2 > 1 (cu numar impar de pasi).

Nota:
Problema, propusa cum a fost cu numarul 2011, este foarte particulara, o problema pentru computer poate.

Problema generala, de a demonstra sau infirma faptul ca orice numar natural N se poate obtine prin cele patru operatii descrise plecand de la 1, este una foarte complicata. (Avem un fel de "sisteme dinamice" combinate cu aritmetica.)