Clasele 9-10 lecția 25 - 1 apr 2015

Premierea concursului de teme

Vezi Clasamentul temelor și Incidentul Teddy Niță. După cum spuneau părinții pe când era legal să-ți bați copiii, pe mine mă doare mai tare decât pe voi. Dacă considerați că eliminările sunt greșite, este ultima ocazie să mă convingeți cu argumente.

• Premiul 1: Anastasia Zloteanu
• Premiul 2: Andreea Zaharia

Probleme de ONI din anii trecuți

Vom urma notele din 18 martie. Vom folosi problemele ca punct de plecare pentru câteva noțiuni ușoare. Nu vom preda mai mult de o oră -- trebuie să vorbim și de ONI care bate la ușă. :-)

Codificări

Vezi lecția de la clasele 11-12.

Combinări cu repetiție

În câte moduri pot alege k elemente dintr-un set de n, ținând cont că am voie să aleg un element de mai multe ori? Cu alte cuvinte, se dă un set de n obiecte diferite, iar fiecare obiect are un număr infinit de copii identice. În câte moduri pot alege o colecție de k obiecte?

Exemplu de problemă: în câte moduri pot să așez n = 5 cărămizi în k = 3 lăzi? Cărămizile sunt identice.

Pentru rezolvare, să găsim întâi un mod de a codifica soluțiile. Codificăm o soluție prin n cifre între 1 și k. De exemplu, (2, 1, 2, 3, 1) înseamnă că punem prima cărămidă în lada 2, a doua cărămidă în lada 1, a treia cărămidă în lada 2, a patra cărămidă în lada 3, a cincea cărămidă în lada 1. Deoarece cărămizile sunt identice, soluția (2, 1, 2, 3, 1) este identică cu soluția (1, 1, 2, 2, 3), căci rezultatul este același: avem două cărămizi în prima ladă, două în a doua și una singură în a treia. Așadar, soluțiile canonice sunt cele în care numerele lăzilor sunt ordonate crescător.

Câte soluții unice există? Să ne închipuim un robot care depozitează automat cărămizile dintr-o soluție ordonată, cum ar fi (1, 1, 2, 2, 3). Robotul pornește din fața primei lăzi. La fiecare pas, el poate face două acțiuni:

1. Depozitează o cărămidă în lada curentă. Notăm această acțiune cu caracterul '.' (punct).
2. Avansează la lada următoare. Notăm această acțiune cu '/' (slash).

Iată câteva exemple de soluții canonice și reprezentările lor în limbajul robotului.

(1, 1, 2, 2, 3) <---> ../../.
(1, 1, 1, 1, 1) <---> .....//
(1, 3, 3, 3, 3) <---> .//....
(2, 2, 2, 3, 3) <---> /.../..

Deoarece robotul depozitează exact n cărămizi și avansează de k - 1 ori, șirul de caractere va avea mereu n + k - 1 simboluri, din care n vor fi punct și k - 1 slash. Mai mult, orice combinație de puncte și slashuri corespunde în mod bijectiv unei soluții canonice (de ce?). De aceea, numărul de combinări cu repetiție este

$C_{R}(n,k)=C(n+k-1,k-1)=C(n+k-1,n)$

Analogia cu robotul este interesantă pentru că ne dă și o metodă exhaustivă de a genera toate combinările cu repetiție prin reducerea la combinări obișnuite (fără repetiție).

Menționăm în treacăt și o altă rezolvare. Putem reprezenta o soluție prin cantitățile de cărămizi depuse în fiecare ladă. Exemplul de mai sus se codifică cu (2, 2, 1). Desigur, este necesar ca suma valorilor să fie n (5, în exemplul dat). Cantitatea depusă în prima ladă poate fi între 0 și k inclusiv, iar pentru fiecare din aceste valori numărul de posibilități pentru lăzile 2...k se poate calcula recurent.

Probleme

• Am trei cutii de dulciuri: fursecuri, pișcoturi și biscuiți. În câte moduri pot alege 5 dulciuri?
• În câte moduri pot să pun n cărămizi în k lăzi, astfel încât fiecare ladă să conțină cel puțin o cărămidă?
• Câte soluții naturale are ecuația $a+b+c=17$? Indiciu: a, b și c sunt lăzile, iar 17 sunt cărămizile. Verificați prin metoda naivă.
• Câte soluții naturale are inecuația $a+b+c\leq 17$? Indiciu: mai adăugați o variabilă x care să preia diferența până la 17.
• Câți termeni are expresia $(a+b+c+d)^{30}$, după ce desfacem parantezele și simplificăm?

Permutări cu repetiție

Fie o colecție de obiecte din care unele se repetă. Astfel, există $n_{1}$ obiecte de tipul $t_{1}$, $n_{2}$ obiecte de tipul $t_{2}$, ..., $n_{k}$ obiecte de tipul $t_{k}$, iar $n_{1}+n_{2}+...n_{k}=n$. Câte permutări distincte ale celor n elemente există?

Fie o permutare dată a celor n obiecte. Din ea putem obține $n_{1}!\cdot n_{2}!\cdot ...\cdot n_{k}!$ permutări identice, căci obiectele din fiecare grupă i pot fi permutate în $n_{i}!$ moduri, independent de celalalte grupe. Așadar, numărul de permutări cu repetiție este:

$P_{R}(n)={\frac {n!}{n_{1}!\cdot n_{2}!\cdot ...\cdot n_{k}!}}$

Probleme

• Câte cuvinte distincte putem obține prin permutarea literelor cuvântului banana?
• Dacă dezvoltăm expresia $(a+b+c+d)^{30}$, care este coeficientul termenului $a^{14}bc^{2}d^{13}$?