(Categoria _Competitii_, autor(i) _Adrian Diaconu si Cosmin Negruseri_)

h2. Sah

h2. "Sah":problema/sah

Prima observatie ar fi ca pentru a ne asigura ca intr-o regiune numarul de casute albe este egal cu numarul de celule negre este suficient ca aria regiunii sa fie para.

Pentru a demonstra ca $N-1$ este numarul maxim de regiuni care se poate creea vom presupune ca se poate imparti tabla in $N$ regiuni. Vom considera ca se folosesc cele mai mici arii posibile, dar acestea trebuie sa fie toate pare. Suma ariilor va fi $2+4+6+..+2*N= 2*(N*(N+1)/2)=N*N+N$ ceea ce ar depasi tabla noastra.

h2. Plimbare

h2. "Plimbare":problema/plimbare

Evident ca o conditie necesara ca un graf turneu (asa se numesc grafurile ca cel mentionat in enunt in care exista exact un arc intre oricare doua noduri) sa aiba un circuit hamiltonean ar fi ca graful sa fie tare conex, daca nu ar fi tare conex atunci evident nu poate exista un circuit intre doua noduri aflate in doua componente tari conexe diferite. Aceasta conditie este si suficienta asa cum va reiesi din algoritmul pe care il vom explica mai jos.