Lista de probleme 46

Spunem că un cuvânt este valid dacă el este format doar cu litere din mulțimea {a,b,c,d} și literele a și b nu sunt alăturate. De exemplu, cuvintele aaaa, acdca sunt valide, dar abbc și baabd nu sunt. Să se determine numărul cuvintelor valide de lungime n. Pentru că acest număr este foarte mare, se va afișa rezultatul modulo 777013.

Definim un număr natural ca fiind bun dacă toate cifrele impare se află înaintea celor pare. De exemplu, numerele 13424, 400, 1357 sunt bune, pe când 34010 nu este. Dându-se un număr natural nenul n, să se determine câte numere bune de n cifre există.

Carmen, piticul de gradina vrea sa meargă în vizita la piticul Tulosba. Pentru a ajunge la Tulosba, Carmen trebuie sa meargă printr-o rețea de N galerii, fiecare alcătuită din M sectoare.

Rețeaua poate fi reprezentată printr-un tablou cu N linii, numerotate de la 1 la N și M coloane, numerotate de la 1 la N. Carmen ocupă sectorul 1 al galeriei 1. Tulosba ocupă sectorul M al galeriei 1.

La galeria n se termina rețeaua și începe gradina unde sunt niște copii răi care vor sa-l spargă pe Carmen cu bâtele de Baseball.

Dacă sectorul curent a lui Carmen este (i,j), atunci se poate deplasa:

• La dreapta, ajungând în sectorul (i,j+1) .
• Pe diagonala la dreapta în sus, ajungând în sectorul (i-1,j+1).
• Pe diagonala la dreapta în jos, ajungând în sectorul (i+1,j+1).

Sa se afișeze în câte moduri poate Carmen sa ajungă la Tulosba.

Se dă un număr N și un număr S. Să se determine câte numere de N cifre au suma cifrelor S.

Se dă un tablou tridimensional, de dimensiune $n$ x $n$ x $n$, fiecare element reprezentând o camera. $m$ dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele $(i,j,k)$ te poți deplasa in camerele de coordonate $(i+1,j,k)$, $(i,j+1,k)$ și $(i,j,k+1)$.
În câte moduri modulo $1234567$ poți ajunge din camera $(1,1,1)$ în camera $(n,n,n)$, fără a trece prin camere blocate?

Într-un depozit au fost așezate cutii identice, una după alta, eventual suprapuse, astfel încât numărul maxim de cutii suprapuse într-o stivă este N, iar între două stive cu același număr de cutii să existe cel puțin una cu mai multe cutii decât oricare dintre cele două. Considerăm că o stivă poate fi formată dintr-o singură cutie.

Avem la dispoziție oricâți căței și oricâte pisici, câte așezări ale acestora în linie dreaptă de lungime n există astfel incât să nu avem o pisică între 2 căței și configurația să înceapă cu un câine și să se termine cu o pisică? Răspunsul se afișează modulo ${10}^9+7$.

La balul din acest an participă n băieți și n fete, numerotați de la 1 la n. Compatibilitățile dintre aceștia pot fi reprezentate sub forma unui graf bipartit. Fie mat matricea de adiacentă. Atunci, băiatul i se poate cupla cu fata j doar dacă sunt compatibili, adică mat[i][j] = 1. Aflați numărul de moduri de a forma cele n cupluri.

Să se determine numărul de submulțimi nevide ale mulțimii {1, 2,..., n} cu proprietatea că oricare două elemente dintr-o submulțime au diferența în modul strict mai mare decât 1.

În câte moduri se poate obține suma n aruncând cu zarul (În câte moduri poți să îl scrii pe n ca sumă de valori mai mici sau egale cu 6).