Principiul invarianților

Teorie

Principiul invarianților stă la baza unor strategii de rezolvare pentru anumite probleme. Aceste probleme descriu un context în care se petrec transformări repetate asupra unei situații (stări) sau, se acționează cu câteva operații diverse (arbitrar alese) asupra acesteia. Dacă aceste transformări păstrează la fiecare etapă “ceva” neschimbat, sau periodic regăsim aceeași caracteristică (proprietate, relație) înseamnă că avem un invariant. În acest caz ne putem raporta la acest invariant pentru a analiza ce se întâmplă și a determina soluția, starea finală, respectiv ce se obține după etapele de un anumit rang.

Soluție favorabilă vom avea dacă rezultatul sau starea finală respectă proprietatea (caracteristica), în caz contrar deducem că succesiunea de transformări nu poate conduce la un astfel de rezultat (o astfel de stare).

Problemele de acest tip încep de cele mai multe ori prin a descrie o stare inițială. Apoi se precizează modul în care se acționează asupra ei. Poate fi o anumită operație care se repetă de mai multe ori, sau pot fi câteva variante de operații care pot acționa (alegerea uneia îi aparține celui care acționează) asupra acestei stări. După care se poate cere (de exemplu) să precizăm:

\(\bullet\) starea finală (un rezultat final);

\(\bullet\) dacă poate fi stare finală o anumită situație (precizată în enunț);

\(\bullet\) cine (dacă sunt cel puțin doi care operează) va ajunge la o stare finală favorabilă;

\(\bullet\) descrierea strategiei necesare (în cazul unor operații diferite) care să permită unuia dintre cei care operează să obțină starea finală favorabilă.

În alte probleme avem descrisă o transformare care se produce prin acțiunea repetată (de \(n\) ori, sau de o infinitate de ori), sau se descriu câteva operații diferite pentru a căror acțiune se optează.
La astfel de probleme se poate solicita:

\(\bullet\) starea inițială, dacă se cunoaște cea finală și natura operațiilor
care s-au făcut;

\(\bullet\) starea \(k_2\) dacă se cunoaște starea \(k_1\) (iar transformarea trece prin \(n\) stări și \(k_1<n\));

\(\bullet\) să stabilim dacă putem obține o stare \(k_2\) dintr-o stare cunoscută \(k_1\).

Invarianții pot fi:

\(\bullet\) valoare constantă pentru anumite caracteristici cantitative (sume, diferențe, produse,\ldots );

\(\bullet\) paritatea rezultatelor obținute după fiecare transformare sau după un anumit număr de transformări, sau chiar paritatea rezultatului final;

\(\bullet\) relație de congruență (mod \(n\));

\(\bullet\) relație de recurență;

\(\bullet\) păstrarea unei anumite poziții față de un reper;

\(\bullet\) verificarea unei relații de către coordonatele punctelor (din plan);

\(\bullet\) un punct fix al unei configurații geometrice;

\(\bullet\) proprietate (geometrică).

Probleme rezolvate

Problema 1

Fie mulțimea \(A=\{1,2,3,\ldots ,169\}\). Putem scrie această mulțime ca reuniune de submulțimi disjuncte, cu cel puțin 3 elemente, astfel încât în fiecare submulțime, cel mai mare element să fie egal cu suma celorlalte elemente din submulțimea respectivă?

Soluție

Dacă partiționăm mulțimea \(A\), vom regăsi toate elementele ei redistribuite în diferite submulțimi. Suma tuturor acestor elemente este aceeași.
Cum
\[S=1+2+3+\ldots +169=(169\cdot 170):2=14365,\]
reținem că este impară.
Fiecare submulțime din partiție, care verifică relația dată, va avea suma elementelor sale egală cu dublul elementului cu valoare maximă — adică un număr par. Și atunci partiționarea mulțimii \(A\) are doar submulțimi cu suma elementelor număr par. Prin urmare \(S = 14365\) ar fi rezultatul unei adunări cu toți termenii numere pare, ceea ce este imposibil. Deci nu putem găsi pentru mulțimea \(A\) o astfel de partiție.

Problema 2

Fie mulțimile
\[A=\{n\in \mathbb{N}^*\mid n\le 10^{10}\}\]
și respectiv
\[B=\{x=n-s(n)\mid s(n)=\mbox{suma cifrelor numărului} \ n,\ n\in A\}.\]
Stabiliți dacă 3441052991 este element al mulțimii \(B\)?

Soluție

După cum știm, un număr natural și suma cifrelor sale sunt congruente modulo 9 (dau același rest la împărțirea cu 9). Astfel pentru orice \(n\) număr natural, \(n-s(n)=M_0\). Deci elementele mulțimii \(B\) sunt multipli de 9 și pentru că \(3441052991\ne M_0\) deducem că nu poate fi element al mulțimii \(B\).

Problema 3

Pe o tablă sunt scrise numerele \(1, 2, 3, \ldots , 2015\). La fiecare pas avem voie să ștergem oricare două numere, și în locul lor să scriem restul împărțirii sumei lor la 7. După câțiva pași, pe tablă rămân scrise două numere, din care unul este egal cu 765. Care este numărul al doilea?

Soluție

Cochetăm din nou cu suma acestor numere.
\[S=1+2+3+\ldots +2015=(2015\cdot 2016):2=2031120.\]

Operând cu împărțire la 7, evaluăm această sumă din acest punct de vedere al relației de congruență modulo 7 și observăm că
\[S=2031120-M_7.\]

Urmărim cum acționează transformarea descrisă. Suma \(S\) o mai putem scrie și
\[S=a+b+(S-a-b)\]
unde \(a\) și \(b\) sunt cele două numere pe care operăm. După primul pas, obținem:
\[S=r+(S-a-b)
\quad(1)\]
unde \(r\) este restul împărțirii lui \(a + b\) la 7 adică un număr natural mai mic decât 7 \((a+b=7k+r)\). Dacă urmărim relația (1) observăm că aceasta devine
\[S=r+(S-a-b)=(a+b)-7k+S-(a+b)=\\=S-7k=M_7.\]

Astfel am obținut invariantul: suma numerelor de pe tablă este mereu un multiplu de 7. Acum putem analiza finalul transformărilor. Avem două numere, din care unul este 765. Evident acesta este unul dintre numerele inițial scrise pe tablă. Celălalt va fi un \(r<7\). Ușor de determinat având în vedere că \((765+r)\equiv 0\pmod 7\). Deci al doilea număr este 5.

Problema 4

Pe o tablă sunt scrise la început numerele 11 și 13. Apoi se operează în mod repetat după cum urmează: se scrie un nou număr (diferit de cele existente) egal cu suma a două numere (arbitrar alese, după ce pe tablă vor fi cel puțin trei numere) scrise deja pe tablă.

a) Arătați că indiferent de câte ori se aplică operația, pe tablă nu poate fi scris numărul 86.

b) Este posibil ca după mai mulți pași, pe tablă să fie scris numărul 2015?

Soluție

Deci avem 11 și 13. După un prim pas mai apare și \(24=11+13\). Apoi mai poate să apară și \(35 = 24 +11= 2\cdot 11 + 13\) sau \(37 = 24 + 13 = 11 + 2\cdot 13\). La următorul pas poate fi scris unul dintre numerele 46, 48, 50, 59 și 61 \((59 = 3\cdot 11 + 2\cdot 13)\). și așa mai departe. În această situație ceea ce avem ca reper este faptul că un număr \(n\) scris pe tablă este dat de relația: \[n=x\cdot 11+y\cdot 13,\ x,y\in \mathbb{N}\]
(numărul scris pe tablă este suma dintre un multiplu de 11 și un multiplu de 13). Numărul 86 poate fi scris pe tablă dacă există numerele naturale \(x\) și \(y\) (\(x<7\), respectiv \(y<6\)) astfel încât
\[86=x\cdot 11+y\cdot 13.\]
\[86-2y=x\cdot 11+y\cdot 11\Leftrightarrow
2(43-y)=11(x+y)\]
iar \(43-y\ne M_{11}\) pentru \(y<6\).
Prin urmare nu vom avea pe tablă numărul 86.
Îl verificăm pe 2015.
\[2015=11\cdot x+13\cdot y\Leftrightarrow
11(183-x-y)=2(y-1)\]
și avem că \(y-1=M_8\), iar \(x\) și \(y\) au aceeași paritate. Rezolvăm ecuația (diofantică) și obținem soluții, (exemplu \(x = 169\) și \(y =12\)). Prin urmare numărul 2015 este posibil să fie scris pe tablă după un anumit număr de pași.

Problema 5

Inițial pe o tablă este scris numărul 1. Sunt permise următoarele operații: să fie înmulțit numărul cu 3, sau să rearanjăm cifrele numărului (dacă acesta are cel puțin 2 cifre). Este posibil ca după asemenea câteva operații să obținem numărul 999?

Soluție

După primul pas, se obține un multiplu de 3. La fel în continuare, vom avea multipli de 3. Chiar dacă operăm prin permutarea cifrelor, suma cifrelor este aceeași și înseamnă că după fiecare operație (indiferent care va fi aceasta) vom avea un \(M_3\). Acum urmărim dacă e posibil să ajungem la 999.
\[999=3\cdot 333=3\cdot 3\cdot 111=3\cdot 3\cdot 3\cdot 37.\]
Dar \(37\ne M_3\). Dacă provine de la un număr la care am permutat cifrele, acesta poate fi doar 73 care de asemenea nu este un \(M_3\). Astfel că de la 1 la 999 nu se poate ajunge prin operațiile descrise.

Problema 6

În parcul de joacă al pokemonilor există 43 pokemoni albaștri, 47 pokemoni galbeni și 51 pokemoni verzi. Când se “ciocnesc” doi pokemoni de culori diferite, ei își schimbă culorile în cea de a treia culoare. Este posibil ca la un moment dat în parc, toți pokemonii să fie de aceeași culoare?

Soluție

Analizăm ce se întâmplă după o ciocnire a pokemonilor. Dacă au aceeași culoare nu se modifică nimic. Dacă au culori diferite, automat cei doi pokemoni vor primi a treia culoare. Deci numărul de pokemoni cu această a treia culoare va crește cu 2 iar numărul pokemonilor de la celelalte două culori se va reduce pentru fiecare cu 1. E posibil să avem în parc pokemoni cu aceeași culoare dacă la un moment dat ajungem să avem același număr de pokemoni pe două culori diferite. Să urmărim această variantă favorabilă. Fie \(x\) numărul pokemonilor albaștri, \(y\) numărul pokemonilor galbeni și \(z\) numărul pokemonilor verzi, la un moment dat. După o ciocnire care implică modificări avem:
\[(x,y,z)\to (x-1,y-1,z+2).\]
Schimbarea pe aceeași culoare devine posibilă dacă \(x-1=y-1\) sau \(x-1=z+2\) sau \(y-1=z+2\) ceea ce conduce la \(x-y\) sau \(z-x+8\) (sau \(z-y+8\)) ceea ce înseamnă că diferența dintre numerele pokemonilor de culori diferite să fie 0 sau \(M_2\). Deoarece în cazul de față oricare diferență nu verifică această condiție, înseamnă că nu e posibil ca toți pokemonii să fie de aceeași culoare.

Probleme propuse

Problema 1, Problema 2, Problema 3, Problema 4, Problema 5, Problema 6, Problema 7, Problema 8, Problema 9, Problema 10, Problema 11, Problema 12, Problema 13, Problema 14, Problema 15, Problema 16, Problema 17, Problema 18, Problema 19, Problema 20, Problema 21, Problema 22, Problema 23, Problema 24, Problema 25, Problema 26, Problema 27, Problema 28, Problema 29, Problema 30.

Leave a Reply

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