Candale Silviu (silviu) La concursul Mate Info UBB, ediția 2021 a fost dat următorul exercițiu:
Fie \(b_nb_{n-1}…b_0\) reprezentarea binară a numărului natural \(B\), \(2021 ≤ B ≤ 2021^{2021}\). Care dintre următoarele afirmații sunt adevărate?
A. Dacă valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este zero, atunci \(B\) este divizibil cu \(3\)
B. Dacă valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă cu \(3\), atunci \(B\) este divizibil cu \(3\)
C. \(B\) este divizibil cu \(3\) dacă suma cifrelor binare este divizibilă cu \(3\), dar nu cu \(9\)
D. Dacă \(B\) este divizibil cu \(3\), atunci valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă cu \(3\)
Răspunsul corect este: A, B, D.
Varianta C. se elimină imediat, deoarece reprezentarea binară a lui 3 este 11, iar suma cifrelor binare este 2, nedivizibil cu 3.
Pentru a demonstra că afirmațiile A., B. și D. sunt adevărate vom demonstra următoarea afirmație, mai generală.
Teoremă: Fie \(N\) un număr natural a cărui reprezentare în baza \(B\) este \(b_nb_{n-1}…b_0\). Numărul \(N\) este divizibil cu \(B+1\) dacă și numai dacă expresia \(E = b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă \(B+1\).
Pentru a demonstra teorema de mai sus, vom demonstra mai întâi următoarea lemă:
Lemă: Fie \(P\) un număr natural. Atunci \(P^{2k}\) este de forma \(X \cdot (P+1)+1\), iar \(P^{2k+1}\) este de forma \(Y \cdot (P+1)-1\)
Demonstrația lemei se face prin inducție. Mai întâi să observăm că \(P^{0} = 1 = 0 \cdot (P+1) + 1\), iar \(P^{1} = P = 1 \cdot (P+1) – 1\).
Dacă \(P^{2k} = X \cdot (P+1)+1\), atunci \(P^{2k+1} = P \cdot P^{2p} \\= P \cdot (X \cdot (P+1)+1) \\= P \cdot X \cdot (P+1)+P \\= P \cdot X \cdot (P+1)+P + 1 – 1 \\= (P \cdot X+1)\cdot(P+1)-1 \\= Y \cdot (P+1) -1\)
Similar, dacă \(P^{2k+1} = Y \cdot (P+1)-1\), atunci \(P^{2k+2} = P \cdot P^{2k+1} \\= P \cdot (Y \cdot (P+1) -1) \\= P \cdot Y \cdot (P + 1) – P \\= P \cdot Y \cdot (P + 1) – P – 1 + 1 \\= P \cdot Y \cdot (P + 1) – (P + 1) + 1 \\= (P \cdot Y -1) \cdot (P + 1) + 1 \\= X \cdot (P+1) + 1\)
Demonstrația teoremei Dacă \(b_nb_{n-1}…b_0\) este reprezentarea în baza \(B\) a lui \(N\), atunci
$$N=b_0 \cdot B^0 + b_1 \cdot B^1 + b_2 \cdot B^2 + b_3 \cdot B^3 + … + b_n \cdot B^n$$
Deoarece puterile lui \(B\) sunt de forma precizată în lemă, obținem:
$$\begin{aligned} N &= b_0 \cdot ((B+1) \cdot f_0 + 1) + b_1 \cdot ((B+1) \cdot f_1 – 1) + b_2 \cdot ((B+1) \cdot f_2 + 1) + b_3 \cdot ((B+1) \cdot f_3 – 1) + \cdots + b_n \cdot ((B+1) \cdot f_n + (-1)^n) \\
& = ((B+1) \cdot b_0 \cdot f_0 + b_0) + ((B+1) \cdot b_1 \cdot f_1 – b_1) + ((B+1) \cdot b_2 \cdot f_2 + b_2) + ((B+1) \cdot b_3 \cdot f_3 – b_3) + \cdots + ((B+1) \cdot b_n \cdot f_n + (-1)^n \cdot b_n)\\
& = (B+1) \cdot b_0 \cdot f_0 + (B+1) \cdot b_1 \cdot f_1 + (B+1) \cdot b_2 \cdot f_2 + (B+1) \cdot b_3 \cdot f_3 + \cdots + (B+1) \cdot b_n \cdot f_n + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
& = (B+1) \cdot ( b_0 \cdot f_0 + \cdot f_1 + b_2 \cdot f_2 + \cdot b_3 \cdot f_3 + \cdots + \cdot b_n \cdot f_n) + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
& = (B+1) \cdot M + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
\end{aligned}$$
Deoarece \((B+1) \cdot M\) este divizibil cu \(B+1\), deducem că \(N\) este divizibil cu \(B+1\) dacă și numai dacă \(b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\) este divizibil cu \(B+1\)!
Observații:
Exercițiul de mai sus este un caz particular al teoremei, în care \(B = 2\).
Expresia \(E\) poate fi scrisă și \(E = (b_0 + b_2 + …) – (b_1 + b_3 + …)\) – diferența dintre suma cifrelor de rang par și suma cifrelor de rang impar. Dacă \(B=10\), proprietatea de mai sus este “Criteriul de divizibilitate cu 11”.