Probleme

Fie o matrice de $n$ linii și $n$ coloane. Un număr de elemente $k \ge 1$ din matrice sunt impare, restul fiind pare. Câte submulțimi nevide cu elemente putem construi, astfel încât suma elementelor unei submulțimi să fie pară, dacă $n=4$ și $k=2$?

a) $512$; b) $32768$; c) $16384$; d) $16$; e) $256$; f) $32767$.

Două numere naturale distincte, fiecare având exact $3$ cifre, sunt considerate partenere dacă primele două cifre ale primului număr sunt egale cu ultimele două cifre ale celui de-al doilea număr, în aceeași ordine. Indicați numărul perechilor de numere partenere cu exact $3$ cifre în care primul număr din pereche este strict mai mic decât al doilea.

a) $8100$; b) $3996$; c) $4104$; d) $4005$; e) $8091$; f) $4095$.

Fie un șir S format din literele a și b, grupate ca blocuri consecutive după următoarea regulă: 4 de a, apoi 7 de b, apoi 5 de a, apoi 6 de b, apoi 8 de a, apoi 4 de b, apoi 6 de a, apoi 9 de b, adică șirul format după regula descrisă arată astfel: S = aaaabbbbbbbaaaaabbbbbbaaaaaaaabbbbaaaaaabbbbbbbbb. Un subșir al lui S este numit valid dacă conține același număr de caractere a și b și toate caracterele a sunt consecutive și toate caracterele b sunt consecutive (de exemplu subșirurile de forma aaaabbbb, bbbbaaaa, aaabbb, ab, etc. sunt valide). Câte subșiruri valide sunt în S?

a) $34$; b) $34!$; c) $26$; d) $2^{17}$; e) $17$; f) $37$.

Considerăm un graf neorientat complet cu nodurile $\{1,2,\dots,10\}$. Alegem exact $9$ muchii astfel încât subgraful format are următoarele proprietăți: (1) este conex; (2) nu conține niciun ciclu; și (3) nodurile $1$, $2$, $3$ și $4$ au gradul $1$ în subgraful format. Câte astfel de alegeri distincte putem face pentru ca subgraful rezultat să îndeplinească toate cele trei condiții?

a) $6^8$; b) $4!\cdot 6^4$; c) $10^8$; d) $7^8$; e) $10\cdot 6^7$; f) $6^7$.

La un festival de dans participă $n$ fete și $m$ băieți. Pentru demonstrațiile de dans planificate se formează $k$ perechi, alcătuite fiecare dintr-o fată și un băiat. Să se calculeze toate posibilitățile de formare a perechilor, dacă $n=7$, $m=5$, $k=3$.

a) 2100; b) 35; c) 60; d) 210; e) 2880; f) 700.

Pentru mulțimea $\{1, 2, 3, \ldots, n\}$ se generează printr-un program toate permutările în care nu există numere vecine alăturate. Două numere $a$ și $b$ sunt vecine dacă $|a-b|=1$ (de exemplu 3 și 4 sunt vecine, 2 și 1 sunt vecine). Știind că pentru $n=5$ au fost generate 14 permutări distincte în care nu există numere vecine, câte permutări se vor genera pentru $n=6$?

a) 72; b) 56; c) 144; d) 90; e) 89; f) 120.

Se dă o matrice cu 3 linii și 3 coloane. Pornim din celula de start (1,1) și vrem să ajungem în celula destinație (3,3), respectând următoarele reguli. Din orice celulă (i,j) ne putem deplasa înainte către orice altă celulă (x,y), cu i<=x, j<=y și perechea (i,j) diferită de perechea (x,y). Pe parcursul deplasării se acceptă să ne întoarcem cel mult o dată dintr-o celulă (i,j) către orice altă celulă (x,y), cu x<=i, y<=j, iar perechea (i,j) este diferită de perechea (x,y). De exemplu, din celula (2,2) putem merge înainte către (2,3), (3,2) sau (3,3), și ne putem întoarce la (1,2), (2,1) sau (1,1). Putem alege să ne întoarcem inclusiv când ajungem în celula (3,3). În câte feluri putem ajunge din celula start către cea destinație?

a) 1024; b) 700; c) 2096; d) 2418; e) 2048; f) 260.

În câte moduri se poate colora următorul graf neorientat folosind 4 culori astfel încât 2 noduri adiacente să nu aibă aceeași culoare? [Figura: graf cu 8 noduri — patru noduri în colțurile unui pătrat exterior și patru noduri în colțurile unui pătrat interior. Muchii: cele 4 laturi ale pătratului exterior, cele 4 laturi ale pătratului interior, cele 4 muchii care leagă fiecare colț exterior de colțul interior corespunzător și cele 2 diagonale ale pătratului interior (X-ul din centru). În total 14 muchii.]

a) 288; b) 696; c) 625; d) 24!; e) 120; f) 24.

Un graf de tip scară are 2n noduri și este reprezentat ca în figură. [Figura: graf „scară" — nodurile x1,…,xn pe un rând, y1,…,yn pe rândul de jos; muchii: xi—x(i+1), yi—y(i+1) pentru 1≤i<n și xi—yi pentru 1≤i≤n.] Dacă n=11, în câte moduri putem alege n dintre muchiile acestuia, astfel încât oricare două dintre ele să nu aibă capete comune?

a) 377; b) 55; c) 75; d) 98; e) 144; f) 110.

Fie un tablou bidimensional M cu l linii și c coloane și un întreg pozitiv k. Valorile pentru elementele din tablou se calculează astfel: M[i][j]=(i+j) mod k, unde x mod y calculează restul împărțirii lui x la y, iar 0<=i<l, 0<=j<c. Câte perechi de elemente care au produsul egal cu suma se găsesc în M? Considerați că l=c=24 și k=6.

a) 9120; b) 384; c) 13824; d) 6912; e) 768; f) 4560.

Se consideră o hartă sub forma unei matrice 4x4. Dacă cineva pleacă de pe poziția (1,1) și vrea să ajungă în celula (4,4), se poate muta doar pe linii sau coloane cu numere mai mari și poate sări oricât de multe în ambele direcții, deci poate ajunge inclusiv direct din (1,1) în (4,4). În câte moduri distincte poate face acest lucru?

a) 76; b) 128; c) 256; d) 63; e) 252; f) 64.

Fie un arbore cu 10 noduri, numerotate de la 1 la 10 și vectorul său de tați v={0,1,1,2,2,3,3,x,y,z}. Câți vectori de tați valizi și distincți se pot forma dând valori lui x, y și z?

a) 700; b) 567; c) 720; d) 686; e) 729; f) 648.

Se dau $m_1$ greutăți de $k_1$ kg fiecare și $m_2$ greutăți de $k_2$ kg fiecare. Cel mai bun candidat la un concurs a scris un program corect care stabilește modurile în care poate fi echilibrată o balanță având pe talerul din stânga o greutate $X$ dată și afișează numărul de soluții posibile. Greutățile pot fi puse pe ambele talere. Programul citește la rulare numerele naturale $m_1$ $k_1$ $m_2$ $k_2$ $X$ în această ordine. Ce afișează programul pentru trei rulări succesive: rulare 1: 5 2 5 1 4, rulare 2: 5 2 5 1 11, rulare 3: 5 2 5 1 20?

a) 10 5 0; b) 20 7 0; c) 20 7 1; d) 10 10 0; e) 10 7 0; f) 20 5 0.

Se consideră șirul $1\ 2\ 3\ 4\ 5\ 6$. În câte moduri se pot aranja elementele șirului astfel încât în șirurile rezultate niciunul dintre elemente să nu se afle pe poziția sa inițială?

a) $\dfrac{6!}{1!}-\dfrac{6!}{2!}+\dfrac{6!}{3!}-\dfrac{6!}{4!}+\dfrac{6!}{5!}-\dfrac{6!}{6!}$; b) $6!$; c) $\dfrac{6!}{0!}-\dfrac{6!}{1!}+\dfrac{6!}{2!}-\dfrac{6!}{3!}+\dfrac{6!}{4!}-\dfrac{6!}{5!}+\dfrac{6!}{6!}$; d) $\dfrac{6!}{1!}+\dfrac{6!}{2!}-\dfrac{6!}{3!}+\dfrac{6!}{4!}-\dfrac{6!}{5!}+\dfrac{6!}{6!}$; e) $6!-5!$; f) $6!-4!$.

Fie un graf neorientat cu $n$ vârfuri, pe care vrem să le împărțim în 3 mulțimi disjuncte nenule (dacă $V$ este mulțimea vârfurilor, fie $V_1, V_2, V_3$ cele trei mulțimi disjuncte, $V_1\subset V$, $V_2\subset V$, $V_3\subset V$, $V_1\cap V_2=\emptyset$, $V_1\cap V_3=\emptyset$, $V_2\cap V_3=\emptyset$). Știind că vârfurile din aceeași mulțime nu pot avea muchii între ele, care este numărul maxim de grafuri care se pot construi respectând aceste condiții pentru $n=2022$?

a) $2^{4088484}$; b) $2^{681414}$; c) $2^{2043231}$; d) $2^{1362828}$; e) $2^{4086462}$; f) $2^{2022}$.

Fie o matrice cu $n$ linii și $m$ coloane. În câte moduri se poate ajunge din colțul stânga-sus (de coordonate $1$ și $1$) în cel din dreapta-jos (de coordonate $n$ și $m$), dacă ne putem deplasa, la fiecare pas, câte o poziție doar pe verticală (în sus sau jos) sau orizontală (în dreapta sau stânga), iar numărul de pași realizați trebuie să fie minim? Se știe că $n=11$ și $m=8$.

a) $524288$ moduri; b) $176$ moduri; c) $19448$ moduri; d) $131072$ moduri; e) $88$ moduri; f) $9724$ moduri.

Pentru a genera submulțimile unei mulțimi $M=\{x_1,x_2,\ldots,x_n\}$ cu $n=10$ elemente se folosește metoda backtracking. Câte submulțimi cu cardinal impar se generează, submulțimi care conțin numai unul dintre elementele $x_1$ și $x_3$ și nu conțin elementul $x_2$?

a) $510$; b) $128$; c) $511$; d) $255$; e) $256$; f) $127$.