Rezolvare A.1

Nu parcurgeți acest articol înainte de rezolvarea problemei!

Enunț:

Se consideră subalgoritmul alg(x, b) cu parametrii de intrare două numere naturale x și b (1 ≤ x ≤ 1000, 1 < b ≤ 10).

Subalgoritm alg(x, b):
    s ← 0
    CâtTimp x > 0 execută
        s ← s + x MOD b
        x ← x DIV b
    SfCâtTimp
    returnează s MOD (b - 1) = 0
SfSubalgoritm

Precizați efectul acestui subalgoritm.

A. calculează suma cifrelor reprezentării în baza b a numărului natural x
B. verifică dacă suma cifrelor reprezentării în baza b - 1 a numărului x este divizibilă cu b - 1
C. verifică dacă numărul natural x este divizibil cu b - 1
D. verifică dacă suma cifrelor reprezentării în baza b a numărului x este divizibilă cu b - 1

Soluție

Răspuns corect: C, D

Justificare:

Reprezentarea în baza b a unui număr natural x se face prin împărțiri succesive la b. Resturile (x MOD b) reprezintă cifrele reprezentării.

Subalgoritmul determină suma acestor cifre și la final returnează rezultatul expresiei s MOD (b-1) = 0, care este TRUE sau FALSE, după cum s este sau nu divizibil cu b-1, deci varianta C este corectă.

Să demonstrăm că și varianta D este corectă.

Vom demonstra următoarea

Proprietate:
Fie două numere naturale x, și b > 1. Restul împărțirii la b-1 a lui x este egal cu restul împărțirii la b-1 a sumei cifrelor reprezentării lui x în baza b.

Demonstrație:

Fie \( x = \overline{a_k \cdots a_2 a_1 a_0}_{(b)} \) reprezentarea lui x în baza b , adică \( x = a_0 \cdot b^0 + a_1 \cdot b^1 + a_2 \cdot b^2 + \cdots + a_k \cdot b^k \). Rezultă:

adunăm și scădem \(a_1\), \(a_2\), …, \(a_k\): \( x = a_0 \cdot b^0 + a_1 \cdot b^1 – a_1 + a_1 + a_2 \cdot b^2 – a_2 + a_2 + \cdots + a_k \cdot b^k – a_k + a_k\)
regrupăm termenii: \( x = a_1 \cdot b^1 – a_1 + a_2 \cdot b^2 – a_2 + \cdots + a_k \cdot b^k – a_ k + a_0 + a_1 + a_2 + \cdots + a_k \)
dăm factor comun pe \(a_1\), \(a_2\), …, \(a_k\): \( x = a_1 \cdot (b – 1) + a_2 \cdot (b^2 – 1) + \cdots + a_k \cdot (b^k – 1) + a_0 + a_1 + a_2 + \cdots + a_k \)

Aplicăm formula \( a^n-1 = (a-1)(a^{k-1} + a^{k-2} + \dots + a^1 + 1)\):

\( x = a_1 \cdot (b – 1) + a_2 \cdot (b – 1) \cdot (b + 1) + \cdots + a_k \cdot (b – 1) \cdot (b^{k-1} + \cdots + b + 1) + a_0 + a_1 + a_2 + \cdots + a_k \)
dăm factor comun pe \(b-1\): \( x = (b-1) \cdot (a_1 + a_2 \cdot (b + 1) + \cdots + a_k \cdot (b^{k-1} + \cdots + b + 1)) + a_0 + a_1 + a_2 + \cdots + a_k \)

Deoarece \( (b-1) \cdot (a_1 + a_2 \cdot (b + 1) + \cdots + a_k \cdot (b^{k-1} + \cdots + b + 1)) = (b-1) \cdot M \) este multiplu al lui \(b-1\), deducem că restul împărțirii lui x la \(b-1\) este egal cu restul împărțirii lui \( S = a_0 + a_1 + a_2 + \cdots + a_k\) la \(b-1\) – ceea ce trebuia demonstrat.

Consecințe:

Restul împărțirii unui număr la 9 este egal cu restul împărțirii sumei cifrelor sale la 9.
Un număr natural este divizibil cu 9 dacă și numai dacă suma cifrelor sale este divizibilă cu 9.
Suma de control a unui număr natural \(x\) este: \(\begin{cases}0 & \text{, daca } x = 0\\ 9 & \text{, daca } x \text{ este multiplu neul al lui } 9 \\ x \% 9 & \text{, altfel} \end{cases}\)

Cifra de control a unui număr natural se determină calculând suma cifrelor numărului, apoi suma cifrelor sumei și așa
mai departe până când suma obținută reprezintă un număr cu o singură cifră. De exemplu, cifra de control a numărului
182 este 2 (1 + 8 + 2 = 11, 1 + 1 = 2).