De ce contează?
Ai o grămadă de bile albe și negre într-un sac. Scoți câte două: dacă sunt la fel, le arunci și pui o bilă albă înapoi; dacă sunt diferite, pui o bilă neagră. Pare haos — la fiecare pas sacul arată altfel. Dar dacă te uiți DOAR la numărul de bile negre, observi ceva care nu se schimbă cu adevărat. Acel ceva îți spune ce culoare are ultima bilă rămasă, fără să joci tot jocul.
Tiparul
Unele procese fac mulți pași și par imprevizibile. Tentația e să le simulezi: să joci fiecare mutare până la final. Dar de multe ori întrebarea nu e despre drum, ci despre destinație — „ce rămâne la final?". Atunci nu drumul contează, ci o mărime care se păstrează indiferent de mutările alese: un invariant.
Un invariant e o mărime care nu se schimbă (sau se schimbă previzibil) la fiecare pas. Cel mai des întâlnit la clasa ta este paritatea — faptul că un număr este par sau impar. Dacă găsești un invariant, răspunsul final depinde doar de el, nu de ordinea pașilor.
Citește cele trei situații și hotărăște pentru care ai nevoie de un invariant și pentru care chiar trebuie să simulezi pas cu pas. (1) Ai 100000 de bile; la fiecare pas scoți două și pui una după o regulă; te întreabă ce culoare are ultima bilă. (2) Ai un vector de 8 numere și ești întrebat care e starea lui exactă după 5 mutări descrise în enunț. (3) Repeți o operație de un miliard de ori și ești întrebat doar dacă rezultatul final e par sau impar.
Oprește-te. Care e observația care face naivul să devină rapid? Formuleaz-o în gând, apoi verifică.