Re: ITA 2002 - Problema 12 outra solu��o - grafos

["Eduardo Azevedo" <eduardo_az@xxxxxxxxxxxxx>]

Seja
Ralph - R
DAvid - D
Rub - r

Podemos fazer um grafo com as ordena��es, em que cada aresta representa uma
troca.

Ser� um hex�gono:


                          RDr
                     /              \
                DRr             RrD
                    |                 |
                 DrR              rRD
                     \                /
                           rDR

-Voltar a uma posi��o envolve um n�mero par de trocas, seja dando a volta (6
trocas) ou indo e voltando n v�rtices (n para ir, n para voltar).

-A posi��o inicial foi RDr, no topo do hex�gono.

-Houve um n�mero �mpar de trocas.

-Como Barrichelo terminou colado em David, ou terminou em RDr (no topo) ou
em DrR (� esquerda em baixo).

-Terminar voltando a RDr � imposs�vel, pois implica em um n�mero par de
trocas.

-Terminar em DrR tamb�m. Indo pela esquerda s�o duas trocas, e pela direita
s�o 4. Qualquer movimento de ida e volta � uma posi��o tem um n�mero par de
trocas. Logo o total � par e essa op��o � imposs�vel.



OBS:

O ITA deu muitos dados.

Bastava saber que o n�mero TOTAL de trocas era �mpar.