Principiul invariantului I

Teorie

Invariantul este o mărime, o relație sau o proprietate care rămâne neschimbată în urma aplicării unei transformări. O situație inițială este supusă în mod repetat unor transformări. De obicei se cere să se demonstreze că în urma acestor transformări nu se poate ajunge la o anumită formă.

Aceasta se poate face alegând caracteristica obiectului care a fost supus transformării, adică “invariantul”. Dacă în final obiectul nu posedă “invariantul” atunci el nu poate fi obținut în urma transformărilor descrise. Un exemplu simplu de invariant este paritatea.

Probleme rezolvate

Problema 1

Pe o tablă sunt scrise numerele \(1,2,3,\ldots ,2009\). Ștergem 3 numere la întâmplare și scriem suma lor. Repetăm operația până când pe tablă rămâne scris un singur număr.

a) Câte operații trebuie efectuate?

b) Acest număr este par sau impar? Justificați!

(Constantin Bărăscu, Concursul “La școala cu ceas”, 2009)

Soluție

Analizăm operația în funcție de paritatea numerelor. Dacă \(x,y,z\) sunt cele trei numere, atunci avem situațiile:

1) Toate cele trei numere \((x,y,z)\) sunt pare. Atunci suma lor \(x+y+z\) este pară, și numărul numerelor impare nu se modifică.

2) Două dintre numere sunt pare și al treilea impar, atunci suma lor este
\(x+y+z=\) impară (par + par + impar) și numărul numerelor impare rămâne același.

3) Două numere sunt impare și altul par. Suma lor este \(x+y+z\) este pară (impar + impar + par) și numărul numerelor impare scade cu doi.

4) Toate cele trei numere sunt impare. Suma lor \(x+y+z\) este impară.
Numărul numerelor impare scade cu doi. Șirul \(1,2,3,\ldots ,2009\) conține 1005 numere impare. După fiecare operație paritatea numărului numerelor impare nu se modifică (care este invariantul). După 1004 operații ultimul număr rămas este deci impar.

Problema 2

Se consideră numerele: \(2-\sqrt 3\), \(4\), \(5+\sqrt 3\), \(7\). După un pas, fiecare număr se înlocuiește cu media aritmetică a celorlalte trei.
Este posibil ca după un anumit număr de pași să obținem numerele: \(4-2\sqrt 3\), \(3\), \(2+2\sqrt 3\) și \(8\)? (Vasile Șerdean, Revista Matlap)

Soluție

Fie \(x,y,z,t\) numerele. După un pas le înlocuim cu numerele
\[\displaystyle\frac{y+z+t}{3},\quad \displaystyle\frac{x+z+t}{3},\quad \displaystyle\frac{x+y+t}{3},\quad \displaystyle\frac{x+y+z}{3}\]
care au suma \[\displaystyle\frac{y+z+t}{3}+\displaystyle\frac{x+z+t}{3}+\displaystyle\frac{x+y+t}{3}+\displaystyle\frac{x+y+z}{3}
=\\=\displaystyle\frac{3(x+y+z+t)}{3}=x+y+z+t.\]
În urma transformărilor făcute suma numerelor obținute este aceeași ca suma numerelor inițiale. Deci invariantul este suma numerelor.
La început suma numerelor este
\[2-\sqrt 3+4+5+\sqrt 3+7=18,\]
iar suma numerelor pe care dorim să le obținem este
\[4-2\sqrt 3+3+2+2\sqrt 3+8=17.\]
Deci nu putem obține numerele \(4-2\sqrt 3\), 3, \(2+2\sqrt 3\), 8 din cele inițiale.

Problema 3

Se consideră numerele \(\sqrt 5-2\), \(\sqrt 5+2\), \(7\). După un pas fiecare număr se înlocuiește cu media geometrică a celorlalte două numere. Este posibil ca după un anumit număr de pași să obținem numerele: \(3-\sqrt 5\), \(3+\sqrt 5\), \(2\)? (Vasile Șerdean, Revista Matlap)

Soluție

Fie \(x,y,z\) numerele (pozitive). După un pas le înlocuim cu \(\sqrt {yz}\), \(\sqrt {xz}\), \(\sqrt {xy}\). La început produsul numerelor este \(xyz\).
După un pas produsul lor este
\[\sqrt {yz}\cdot \sqrt {xz}\cdot \sqrt {xy}=\sqrt {x^2y^2z^2}=xyz.\]
În urma transformărilor făcute produsul numerelor obținute este același
cu produsul numerelor inițiale. Deci invariantul este produsul numerelor.
La început produsul numerelor este
\[sqrt 5-2)(\sqrt 5+2)\cdot 7=(5-4)\cdot 7=7,\]
iar pentru numerele ce vrem să le obținem produsul este
\[(3-\sqrt 5)(3+\sqrt 5)\cdot 2=(9-5)\cdot 2=4\cdot 2=8.\]
Deci nu putem obține numerele \(3-\sqrt 5\), \(3+\sqrt 5\), 2 din cele inițiale prin transformarea dată.

Problema 4

Considerăm mulțimea \(\{1,5,8\}\). La fiecare operație alegem două elemente \(x\) și \(y\) și le înlocuim cu \(\displaystyle\frac{x+y}{\sqrt 2}\) și \(\displaystyle\frac{x-y}{\sqrt 2}\). Prin această operație putem obține mulțimea: \(\{2,4,9\}\)? (Vasile Șerdean, Revista Matlap)

Soluție

Căutăm invariantul. Prin operația indicată nu se schimbă suma pătratelor elementelor mulțimii date:
\[\left(\displaystyle\frac{x+y}{\sqrt 2}\right)^2+\left(\displaystyle\frac{x-y}{\sqrt 2}\right)^2
=\displaystyle\frac{x^2+2xy+y^2}{2}+\displaystyle\frac{x^2-2xy+y^2}{2}
=\\=\displaystyle\frac{2(x^2+y^2)}{2}=x^2+y^2.\]
La mulțimea inițială suma pătratelor elementelor este:
\[1^2+5^2+8^2=90,\]
iar la cea care dorim să ajungem, suma pătratelor elementelor este:
\[2^2+4^2+9^2=101.\]
Deci nu putem obține mulțimea \(\{2,4,9\}\).

Problema 5

Pe o tablă sunt scrise numerele: \(2\), \(5\), \(9\). Se stabilește să se șteargă de pe tablă numerele \(x\) și \(y\) și în locul lor să se scrie numerele \(\displaystyle\frac{24x-7y}{25}\) și \(\displaystyle\frac{7x+24y}{25}\). Prin aceste operații pot să apară pe tablă numerele \(1\), \(6\), \(8\)? (Vasile Șerdean, Revista Matlap)

Soluție

Căutăm invariantul. Prin operația dată nu se schimbă suma pătratelor numerelor scrise pe tablă:
\[\left(\displaystyle\frac{24x-7y}{25}\right)^2+\left(\displaystyle\frac{7x+24y}{25}\right)^2
=\displaystyle\frac{576x^2-336xy+49y^2}{625}
+\\+\displaystyle\frac{49x^2+576y^2+336xy}{625}
=\displaystyle\frac{625(x^2+y^2)}{625}=x^2+y^2.\]
La tripletul inițial de numere suma pătratelor este
\[2^2+5^2+9^2=4+25+81=110,\]
iar la cel care dorim să ajungem, suma pătratelor este
\[1^2+6^2+8^2=1+36+64=101.\]
Deci nu se poate obține tripletul cerut.

Problema 6

Fie \(M=\{1,2,\ldots ,2007,2008\}\) mulțimea numerelor naturale nenule mai mici sau egale cu \(2008\). Mulțimea \(M\) se modifică succesiv, înlocuind câteva elemente ale sale cu restul sumei lor la împărțirea cu 29.
Dacă la un moment dat avem că \(M=\{x,2007\}\), să se determine \(x\).(Mihai Chiș, Concursul “Traian Lalescu”, 2008)

Soluție

Suma elementelor lui \(M\) este
\[1+2+3+\ldots +2007+2008=\displaystyle\frac{2008\cdot 2009}{2}\]
\[=1004\cdot 2009=2017036=2017008+28=29\cdot 69552+28=\\=\displaystyle M29+28.\]
Înlocuind câteva elemente din \(M\) cu restul împărțirii acestora
la 29, restul împărțirii sumei elementelor lui \(M\) la 29, nu se modifică,
rămâne invariant. Dacă la un anumit moment se ajunge la \(\{x,2007\}\), \(x\) fiind rezultatul înlocuirii unui grup de elemente cu restul împărțirii la 29 al sumei acestora, atunci \(x\in \{0,1,\ldots ,28\}\).
Din \(2007+x=M29+28\) și \(2007=M29+6\) obținem: \(M29+6+x=M29+28\Rightarrow x=28-6.\) Deci \(x=22\).

Problema 7

Considerăm numerele: \(1,2,3,\ldots ,2010,2011\). Alegem două numere \(x\) și \(y\) din șir și le înlocuim cu
\[z=\displaystyle\frac{1}{\displaystyle\frac{1}{x}+\displaystyle\frac{1}{y}+\displaystyle\frac{1}{xy}}.\]

Demonstrați că indiferent cum considerăm perechile \((x,y)\), după \(2010\) pași se obține întotdeauna același număr. Aflați acest număr.

Soluție

Din \(z=\displaystyle\frac{1}{\displaystyle\frac{1}{x}+\displaystyle\frac{1}{y}+\displaystyle\frac{1}{xy}}\Rightarrow
\displaystyle\frac{1}{x}+\displaystyle\frac{1}{y}+\displaystyle\frac{1}{xy}=\displaystyle\frac{1}{z}\Leftrightarrow\)
\[\displaystyle\frac{1}{x}+\displaystyle\frac{1}{y}+\displaystyle\frac{1}{xy}+1=1+\displaystyle\frac{1}{z}\Leftrightarrow
\left(1+\displaystyle\frac{1}{x}\right)\left(1+\displaystyle\frac{1}{y}\right)=1+\displaystyle\frac{1}{z}.\]
În general dacă notăm cu \(x_1,x_2,\ldots ,x_n\) numerele existente la un moment dat, expresia
\[P=\left(1+\displaystyle\frac{1}{x_1}\right)\left(1+\displaystyle\frac{1}{x_2}\right)\ldots
\left(1+\displaystyle\frac{1}{x_n}\right)
\quad\mbox{este invariantă.}\]
În cazul nostru
\[P=\left(1+\displaystyle\frac{1}{1}\right)\left(1+\displaystyle\frac{1}{2}\right)\left(1+\displaystyle\frac{1}{3}\right)\ldots
\left(1+\displaystyle\frac{1}{2011}\right)
=\\=\displaystyle\frac{2}{1}\cdot \displaystyle\frac{3}{2}\cdot \displaystyle\frac{4}{3}\cdot \ldots \cdot \displaystyle\frac{2012}{2011}=2012.\]
Dacă \(u\) este ultimul număr atunci \(1+\displaystyle\frac{1}{u}=2012\)
de unde \(\displaystyle\frac{1}{u}=2011\) și deci \(u=\displaystyle\frac{1}{2011}\).

Problema 8

Considerăm numerele \(\displaystyle\frac{1}{2},\displaystyle\frac{1}{3},\displaystyle\frac{1}{4},\ldots ,\displaystyle\frac{1}{2011}\). Alegem două numere \(x\) și \(y\) și le înlocuim cu numărul \(z=\sqrt {x^2+y^2-x^2y^2}\).
Arătați că după \(2010\) pași de acest fel se ajunge la același număr.

Soluție

Din \(z=\sqrt {x^2+y^2-x^2y^2}\Rightarrow z^2=x^2+y^2-x^2y^2\Rightarrow\)
\[1-z^2=1-(x^2+y^2-x^2y^2)\Leftrightarrow 1-z^2=1-x^2-y^2+x^2y^2\Leftrightarrow\]
\[1-z^2=1-x^2-y^2(1-x^2)\Leftrightarrow 1-z^2=(1-x^2)(1-y^2).\]
Dacă notăm cu \(a_1,a_2,\ldots ,a_n\) numerele existente la un anumit moment, produsul
\[P=(1-a_1^2)(1-a_2^2)\ldots (1-a_n^2)
\quad\mbox{este invariant.}\]
Dacă \(u\) este ultimul număr, atunci
\[1-u^2=\left(1-\displaystyle\frac{1}{2^2}\right)\left(1-\displaystyle\frac{1}{3^2}\right)\ldots
\left(1-\displaystyle\frac{1}{2011^2}\right)\]
\[=\left(\displaystyle\frac{2^2-1^2}{2^2}\right)\left(\displaystyle\frac{3^2-1^2}{3^2}\right)\ldots
\left(\displaystyle\frac{2011^2-1^2}{2011^2}\right)\]
\[=\left[\displaystyle\frac{(2-1)(2+1)}{2^2}\right]\cdot
\left[\displaystyle\frac{(3-1)(3+1)}{3\cdot 3}\right]\ldots
\left[\displaystyle\frac{(2011-1)(2011+1)}{2011^2}\right]\]
\[=\displaystyle\frac{1\cdot 3}{2\cdot 2}\cdot \displaystyle\frac{2\cdot 4}{3\cdot 3}\cdot \ldots \cdot
\displaystyle\frac{2010\cdot 2012}{2011\cdot 2011}\]
\[=\displaystyle\frac{(1\cdot 2\cdot 3\ldots 2010)(3\cdot 4\cdot 5\ldots 2010\cdot 2011\cdot 2012)}
{(2\cdot 3\ldots 2010\cdot 2011)(2\cdot 3\ldots 2011)}\]
\[=\displaystyle\frac{1}{2011}\cdot \displaystyle\frac{2012}{2}=\displaystyle\frac{1006}{2011}
\quad\mbox{deci}\quad
1-u^2=\displaystyle\frac{1006}{2011}\Rightarrow\]
\[u^2=1-\displaystyle\frac{1006}{2011}\Rightarrow
u^2=\displaystyle\frac{1005}{2011}\Rightarrow
u=\sqrt {\displaystyle\frac{1005}{2011}}.\]

Problema 9

Considerăm șirul \(1,2,3,\ldots ,89,90\). Ștergem două numere din șir \(x\) și \(y\) și scriem numărul \(x+y-1\) în loc. Ce număr rămâne după \(89\) de operații?

Soluție

Căutăm un invariant. Suma numerelor din șir este:
\[S=1+2+\ldots +90=\displaystyle\frac{90\cdot 91}{2}=45\cdot 91=4095.\]
Considerăm diferența dintre suma numerelor și numărul lor. Fie \(I=S-n\). Să vedem cum se modifică această diferență.
Mai putem scrie
\[I=S+(x+y)-(x+y)-n.\]
După ce ștergem două numere și le înlocuim cu \(x+y-1\) obținem:
\[I=S-(x+y)-(n-1)+x+y-1\Rightarrow I=S-n\]
deci valoarea lui \(I\) nu se modifică, este un invariant.
Dacă inițial am avut
\[I=S-n=4095-90=4005,\]
după 89 de operații \(I\) va fi tot 4005. Ultimul număr este \(I+1=4006\).

Problema 10

Se consideră un cub \(ABCDA’B’C’D’\). În fiecare din vârfurile \(A,B,D\) și \(A’\) se scrie numărul \(1\), iar în fiecare din vârfurile \(C,C’,B’\) și \(D’\) se scrie numărul \(0\). Numim “operație” faptul că mărim sau micșorăm cu același număr numerele pe de aceeași muchie. Este posibil ca după un număr finit de operații să obținem în fiecare vârf \(2009\)? (Marius Perianu, Etapa locală, Vâlcea, 2009)

Soluție

Să vedem care este invariantul. Notăm cu \(x\) suma numerelor din vârfurile \(A,C,B’,D’\). Deci la început \(x=1+0+0+0=1\).
Fie \(y\) suma numerelor din vârfurile \(A’,C’,B,D\). La început \(y=1+0+1+1=3\). Avem \(y-x=2\). După fiecare operație \(y-x\) nu se modifică. Acesta este invariantul. Dacă ar fi posibil să obținem în fiecare vârf 2009, atunci \(y-x=0(\ne 2)\) deci nu este posibil.

Probleme propuse

Problema 1, Problema 2, Problema 3, Problema 4, Poblema 5, Problema 6Problema 7, Problema 8, Problema 9, Problema 10, Poblema 11, Problema 12.

Leave a Reply

Your email address will not be published. Required fields are marked *