Soluţii corecte: Zoltan Szabo.

Nota: Am primit mai multe solutii cu o idee de rezolvare corecta, dar care necesitau un numar mai mare de calcule.

Solutia autorului (schita): Pentru un numar mare de calcule N, este mai eficient sa se descopere permutarea (amestecarea) aplicata decat sa se realizeze anumite operatii pentru fiecare calcul in parte. Intuitiv, aceasta pentru ca, daca presupunem x numarul de calcule necesar pentru determinarea modului de amestecare, N+x ramane un numar mai mic decat yN, unde y este numarul de operatii pentru realizarea corecta a unui singur calcul (presupunem y mai mic decat x, fara a pierde din generalizare, constant indiferent de calcul). 

Pentru determinarea permutarii unul numar de pana la 10 cifre este necesara o singura operatie: Se calculeaza 1234567890 + 0 si se verifica rezultatul pe ecranul calculatorului. Cum toate cifrele sunt diferite, se determina in mod unic permutarea realizata de calculatorul ciudat.

Pentru determinarea permutarii unui numar de pana la 100 de cifre sunt necesare 2 operatii: Se calculeaza 11...122...233...990..00 + 0, in care fiecare cifra apare de 10 ori si se verifica rezultatul pe ecranul calculatorului. Pozitiile ocupate initial de 11..1 pot sa ia oricare dintre cele 10 pozitii ocupate de 1 in rezultat. Analog pentru fiecare cifra, sunt 10 pozitii posibile. Pentru a fi diferentiata pozitia exacta (unde apare primul 1, unde apare al doilea 1, etc.), se realizeaza calculul 123...0123...0..123...0 + 0 (pozitiile care anterior aveau aceeasi valoare sunt acum diferentiate prin valori diferite). Se verifica, intre pozitiile posibile de dupa prima adunare, locul cifrei corespunzatoare dupa a doua permutare. (Nota: a doua adunare poate sa fie intr-o forma putin diferita, daca este necesara eliminarea valorilor 00... la inceput de numar pentru ambele operatii, fapt ce ar duce la imposibilitatea determinarii exacte a pozitiei ocupate de fiecare 0)

Pe aceeasi idee, pentru un numar pana la 1000 sunt necesare 3 operatii, iar pentru un numar pana la 10000 (deci si solutia problemei, pentru 2020) sunt necesare 4 adunari.

In concluzie, sunt necesare N + 4 calcule, unde N este numarul de calcule pe care il aveti de efectuat cu calculatorul ciudat.

 

Zoltan Szabo da o solutie in care adunarea se face intre 2 numere diferite de 0, pe exact 2020 pozitii.

1. Pentru numere de 9 cifre este îndeajuns ca să folosim o singură operație.

Introducem operația 111111111+876543210

Trebuie să obținem rezultatul 987654321

Calculatorul va afișa un alt număr, o permutare a acestor cifre. De exemplu 849571236.

De aici deducem, că în loc de numerele de mai sus s-au adunat alte numere. Un număr are toate cifrele identice și nu este afectat, iar celălalt număr este 738460125.

Deci în loc de 876543210 calculatorul interpretează 738460125.

Numerotăm cifrele de la stânga la dreapta, astfel permutarea identică va fi (1 2 3 4 5 6 7 8 9)

Numărul nostru 738460125 a suferit modificări.

Prima cifră 7 ar trebui să fie pe poziția 2, a doua cifră este 3 dar ar trebui să fie pe poziția 6, etc. Cifrele le putem pune la pozițiile lor folosind permutarea  (2 6 1 5 3 9 8 7 4).

În concluzie numerele pe care vrem să le adunăm vor fi supuse amestecării cifrelor conform permutării (2 6 1 5 3 9 8 7 4) și așa se vor aduna, întrucât calculatorul aplică asupra cifrelor permutarea inversă  

(2 6 1 5 3 9 8 7 4)^-1=(3 1 5 9 4 2 8 7 6)

Rezultatul va fi cel corect.

Astfel 111111111 se va transforma pe baza permutării (2 6 1 5 3 9 8 7 4) în 111111111

876543210 se va transforma pe baza permutării (2 6 1 5 3 9 8 7 4) în 684057123.

Introducem suma 111111111+684057123, dar știm (am depistat) că regula de amestecare a cifrelor este permutarea (3 1 5 9 4 2 8 7 6), astfel numerele adunate vor fi 111111111 și 876543210 și se va afișa rezultatul corect 987654321.

Să observăm că în calcule nu avem numere pe care dacă le adunăm să fie depășire de 9, cea mai mare sumă este 8+1=9.

2. Pentru numere de 10 de cifre este îndeajuns să folosim 1 operație, însă pentru ca să nu avem depășire vom aduna numerele: 8765432100 + 1111111110 = 9876543210

Procedeul de calcul va fi la fel folosind permutări de 10 elemente.

Pentru numere de 2020 de cifre vom avea nevoie de 4 operații de adunare.

Pentru a putea nota cu ușurință un număr de 2020 de cifre, vom scrie o secvență de cifre între paranteze și un indice după paranteză ce reprezintă numărul de repetiții a secvenței. Un număr este deci a concatenare de secvențe multiple și cifre neperiodice.

Ex. (234)₃56(0)₄ corespunde numărului 234234234560000

Vom construi 4 adunări cu numere ce conțin cifrele periodic, cu perioadele de lungime 9, 8, 7 respectiv 5, astfel ca rezultatele celor 4 adunări să se obțină fără depășirea valorii 9.

Cel mai mic multiplu comun al acestor numere este cmmmc(9,8,7,5)=2520. Deci cele 4 numere acoperă 2520 de combinații distincte formate din 4 cifre luate din cele 4 numere de pe poziții identice.

Vom obține 4 măști:

1. Cifrele se repetă cu perioada 9:

(876543210)₂₂₄8765 + (1)₂₀₂₀ = (987654321)₂₂₄9876

2. Cifrele se repetă cu perioada 8:

(87654321)₂₅₂8765 + (1)₂₀₂₀ = (98765432)₂₅₂9876

3. Cifrele se repetă cu perioada 7:

(8765432)₂₈₈8765 + (1)₂₀₂₀ = (9876543)₂₈₈9876

4. Cifrele se repetă cu perioada 5:

(87654)₄₀₄ + (1)₂₀₂₀ = (98765)₄₀₄

În urma efectuării celor patru adunări, fiecare din cele 2020 de poziții va conține câte o cifră cunoscută. Vom considera amprenta unei poziții cvadruplul format din cifrele de pe acea poziție. Aceste amprente identifică în mod unic fiecare poziție a numerelor.

Astfel:

Poziție	Amprentă
1	(9,9,9,9)
2	(8,8,8,8)
3	(7,7,7,7)
4	(6,6,6,6)
5	(5,5,5,5)
6	(4,4,4,9)
7	(3,3,3,8)
8	(2,2,9,7)
9	(1,9,8,6)
10	(9,8,7,5)
...	...
2016	(1,2,3,9)
2017	(9,9,9,8)
2018	(8,8,8,7)
2019	(7,7,7,6)
2020	(6,6,6,5)

 

Astfel putem identifica permutarea P, care reprezintă regula calculatorului să pună o cifră de pe o anumită poziție inițială pe o poziție finală. Apoi calculăm P^-1, permutarea inversă cu scopul de a aplica numărului nostru înainte de calcule. Astfel când calculatorul va aplica amestecarea cifrelor conform permutării P, toate cifrele vor ajunge pe pozițiile lor inițiale și calculatorul va putea afișa rezultatul corect pe ecran.

Deci pașii pe care le vom efectua sunt:

1. Calculăm  (876543210)₂₂₄8765 + (1)₂₀₂₀ , care ar trebui să fie (987654321)₂₂₄9876

2. Calculăm  (87654321)₂₅₂8765 + (1)₂₀₂₀ , care ar trebui să fie (98765432)₂₅₂9876

3. Calculăm  (8765432)₂₈₈8765 + (1)₂₀₂₀ , care ar trebui să fie (9876543)₂₈₈9876

4. Calculăm  (87654)₄₀₄ + (1)₂₀₂₀ , care ar trebui să fie (98765)₄₀₄

5. Identificăm permutarea P, prin care calculatorul a amestecat cifrele

6. Calculăm permutarea inversă P^-1

7. Suntem pregătiți să calculăm orice operație matematică cu operanzi de 2020 de cifre, dar înainte să introducem în calculator, aplicăm amestecarea cifrelor cu permutarea P^-1. (Acestor numere calculatorul aplică amestecarea cifrelor cu permutarea P și ele vor ajunge pe pozițiile lor inițiale).

Rezolvitorul da alte 2 solutii folosind reprezentarea in baza 8, respectiv baza 7 pe care nu le enuntam aici din lipsa de spatiu:

Observăm, că 8*8*8*8=4096, putem acoperi unic plaja de valori folosindu-ne de baza 8.  

Întrucât 7*7*7*7=2401>2020, Problema se poate rezolva și folosindu-ne de proprietățile bazei 7.