(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.

Plecand de la aceasta observatie si de la faptul ca $N$ este mereu par propunem urmatoarea impartire a tablei si voi demonstra apoi ca indeplineste conditiile din enunt. Impartim tabla in benzi de latime $2$ (pentru a asigura paritatea ariilor). Apoi prima banda o lasam intreaga, iar pentru urmatoarele banda $i$ se va inmparti in $i-1$ si {$N-i+1$}. Astfel se vor creea $N-1$ regiuni. Se observa ca toate dreptunghiurile difera intre ele prin lungime deoarece se folosesc toate numerele de la $1$ la $N$ mai putin {$N/2$}.

Plecand de la aceasta observatie si de la faptul ca $N$ este mereu par propunem urmatoarea impartire a tablei si voi demonstra apoi ca indeplineste conditiile din enunt. Impartim tabla in benzi de latime $2$ (pentru a asigura paritatea ariilor). Apoi prima banda o lasam intreaga, iar pentru urmatoarele banda $i$ se va imparti in $i-1$ si {$N-i+1$}. Astfel se vor creea $N-1$ regiuni. Se observa ca toate dreptunghiurile difera intre ele prin lungime deoarece se folosesc toate numerele de la $1$ la $N$ mai putin {$N/2$}.

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.