Probleme

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.