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.