Probleme

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.