Plecand de la aceasta observatie si de la faptul ca $N$ este mereu par propunem urmatoarea impartirea 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$.
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

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.
Astfel pentru graful nostru vom determina componentele tari conexe, si vom cauta un circuit hamiltonean in cea mai mare dintre acestea. De acum ne vom concentra doar asupra nodurilor acestei componente. Evident ca aceasta componenta conexa contine cel putin un circuit, pentru a determina unul facem o cautare in adancime, si trebuie sa gasim la un moment dat o muchie de intoarcere (pentru ca altfel componenta nu ar fi tare conexa). Vom imparti nodurile din aceasta componenta in patru multimi: $A$ multimea nodurilor din circuit, $B$ multimea nodurilor din afara circuitului pentru care exista si arce orientate de la noduri din circuit la ele, si arce orientate de la ele la noduri din circuit, $C$ multimea nodurilor din afara circuitului pentru care exista numai arce ce pornesc din circuit inspre noduri, si $D$ multimea nodurilor pentru care toate arcele intre ele si noduri din circuit sunt orientate de la ele inspre circuit. Puteti observa ca nodurile din multimea $B$ pot fi inserate tot timpul in circuit undeva inlocuind un arc intre doua noduri ale circuitului cu doua arce de la un nod al circuitului la nodul multimii $B$ si apoi la alt nod din circuit. Inserarea unui astfel de nod dureaza maxim $O(n)$ pasi, alti $O(n)$ pasi ar fi necesari pentru modificarea multimilor $B, C, D $ pentru ca circuitul s-a schimbat. Dupa ce nu ne mai ramane nici un nod in $B$. Ramanem doar cu noduri de tip $C$ sau $D$. Orice nod din multimea $C$ va avea cel putin un arc orientat spre alt nod din multimea $D$ pentru ca altfel nu am fi intr-o componenta tare conexa. Acum aceste doua noduri legate printr-o muchie dinspre $C$ inspre $D$ pot fi inserate in circuit. Astfel am aratat o cale practica de a mari lungimea circuitului pana cand epuizam toate nodurile.