Soluţii corecte: Viorel Manta, Aurel Ionescu, Zoltan Szabo.

  1. Viorel Manta, Aurel Ionescu:

 Începem cu N și observam că ultima sa cifră sa nu este zero.
Sa gasim primul zero din dreapta; sa presupunem ca este in pozitia a m-a. Apoi se adaugă N*10m (adică N deplasat peste m poziții) pentru a schimba această cifră, fără a afecta nimic la dreapta acestuia. Trecem sa găsim următorul zero, și adaugăm din nou N*10j pentru indicele j corespunzător potrivit. Cu fiecare iterație, zero se deplasează de la capătul din dreapta, în continuare spre stânga.
 Continuam, până cand cel mai din dreapta zero, este la cel puțin 2016 locuri la stânga (daca există). In final numarul nostru este T= K*102016 + P , unde P nu are zerouri . Efectuând scaderea T - K*102016 (unde  K*102016 = K*22016 * 52016)
ramanem cu P care este un multiplu de N=22016, fără zerouri în reprezentarea sa zecimală .

2. Zoltan Szabo:

Ne vom folosi de o proprietate de divizibilitate ale numerelor naturale la 2n.

Se poate demonstra uşor, despre un număr natural N:

a1. N este divizibil cu 2 dacă şi numai dacă ultima cifra a lui N se divide la 2.

a2. N este divizibil cu 22 dacă şi numai dacă ultimele 2 cifre ale lui N se divid la 22.

a3. N este divizibil cu 23 dacă şi numai dacă ultimele 3 cifre ale lui N se divid la 23.

ak. N este divizibil cu 2k dacă şi numai dacă ultimele k cifre ale lui N se divid la 2k.

a2016. N este divizibil cu 22016 dacă şi numai dacă ultimele 2016 cifre ale lui N se divid la 22016.

 

Vom considera problema generală: găsirea unui multiplu al lui 2N, unde N este număr natural nenul.

 Soluţia 1: (generare multiplu cu orice cifră nenulă)

Numărul 10k este format dintr-o cifră de 1 urmat de k cifre de 0. Deci pentru orice k>=N, adunarea lui 10k (care este un multiplu al lui 2k) la un alt număr natural, nu va afecta ultimele k cifre ale celui de al doilea număr.

Algoritmul de rezolvare va fi următorul:

Numărul D=2are ultima cifră un număr din mulţimea {2,4,6,8} deci diferită de 0.

Vom porni cu numărul M=D=2N. De la dreapta la stânga vom depista prima cifră de 0 în acest număr. Dacă nu există cifră 0, atunci problema are soluţie, altfel vom nota această poziţie cu c1. Construim numărul M1=M+D*10c1-1. (adică la M se adaugă numărul D=2N completat la dreapta cu c1-1 zerouri. Astfel primele c1-1 cifre ale lui M nu se modifică, iar cifra 0 de pe poziţia c1 se transformă din 0 în ultima cifră a lui D, diferită de 0).

M1 este multiplu de 2N pentru că este suma a doi multipli de 2N. În consecinţă numărul M1 va avea primele c1 cifre din dreapta diferite de 0.

În continuare vom căuta în acest număr M1 cea mai din dreapta cifră de 0. Dacă nu mai există cifră 0, problema are deja soluţie, altfel acestă cifră va fi pe poziţia c2, cu c2>c1. Construim numărul M2=M1+D*10c2-1 . Acest număr este de asemenea multiplu de 2N.

Apoi căutăm în M2 cea mai din dreapta cifră de 0. Dacă nu există cifră 0 în număr atunci problema este rezolvată, iar dacă există, aceasta va fi pe poziţia c3>c2.

Calculând în mod repetat conform procedeului descris mai sus, obţinem un şir de poziţii de cifre c1, c2, c3, …, ck. Acest şir va avea ultimul element ck<=N.

Algoritmul se poate termina în două feluri:

a. Nu există termen ck+1

Asta înseamnă că la calculul valorii lui Mk au dispărut toate cifrele de 0 din numărul Mk, deci s-a obţinut un multiplu valid, fără cifre de 0.

b. Termenul ck+1 indică o poziţie mai mare decât N

În acest caz nu se mai continuă cu procedeul descris anterior, ci toate cifrele de 0 existente în număr se pot înlocui de exemplu cu cifra 1. Fiecare înlocuire de cifră corespunde cu o adunare de forma X=Mk+10p, cu p>=N (10p este un număr natural format din cifra 1 şi cel puţin N cifre de 0, adică nu afectează ultimele N cifre din dreapta).

Mk este multiplu de 2 şi numărul 10p =2p*5p este de asemenea multiplu de 2 (p>=N). Deci am rezolvat problema.

 

Soluţia 2. (generare multiplu cu ajutorul a două cifre distincte)

Cu inducţie matematică putem demonstra că folosind două cifre de paritate distinctă, se poate construi un număr format din n cifre care să fie divizibil cu 2n.

De exemplu pentru cifrele 1 şi 2 avem.

Pentru n=1: numărul 2 este divizibil cu 2.

Pentru n=2: numărul 12 este divizibil cu 22, şi se obţine din numărul anterior, adăugând în faţa lui cifra 1.

Pentru n=3: numărul 112 este divizibil cu 23, şi se obţine din numărul anterior, adăugând în faţa lui cifra 1.

Pentru n=4: numărul 2112 este divizibil cu 24, şi se obţine din numărul anterior, adăugând în faţa lui cifra 2.

Pentru n=k admitem, că există un număr NK format din k cifre, divizibil cu 2k.

Demonstrăm, că există şi pentru n=k+1 un asemenea număr.

Numărul NK este divizibil cu 2k. Pentru a găsi numărul cerut, studiem divizibilitatea numărului la 2k+1.

Avem două cazuri:

a. numărul NK este divizibil atât cu 2k cât şi cu 2k+1

Cifra ce trebuie adăugată în faţa numărului poate fi doar 1 sau 2, ceea ce corespunde unei adunări cu 10k sau 2*10k.

Dintre numerele NK+1ok şi NK+2*10k doar acesta din urmă este divizibil cu 2k+1 (pentru că NK este divizibil cu 2k+1 iar 2*10k=2k+15k este de asemenea divizibil cu 2k+1).

Deci dacă numărul NK se divide la 2k+1, în faţa numărului se va adăuga cifra 2 ca cifră nouă.

b.  numărul NK este divizibil cu 2k dar nu este divizibil cu 2k+1

Cifra ce trebuie adăugată în faţa numărului poate fi doar 1 sau 2, ceea ce corespunde unei adunări cu 10k sau 2*10k.

Dintre numerele NK+1ok şi NK+2*10k doar primul număr este divizibil cu 2k+1, pentru că:

NK+10k=(2p-1)2k+2k5k=2k(2p+1+5k)=2k2M=2k+1M

Deci dacă numărul NK se divide la 2k+1, în faţa numărului se va adăuga cifra 1 ca cifră nouă.

 Acest algoritm funcţionează pentru orice cifră impară în locul cifrei 1 şi orice cifră pară în locul cifre