Re: ITA 2002 - Problema 12 - foi mal - pensando bem da pra melhorar

["Eduardo Azevedo" <eduardo_az@xxxxxxxxxxxxx>]

Alias, agora, com o gráfico, pode-se dar uma solução mais geral.

Seja

R - Ralph
D - David
r - Rubinho

L - Trocas de liderança/seg lugar
s - trocas de seg/terc lugar

o hexágono pode ficar assim, com L e s no lugar das arestas, mostrando o
tipo de troca daquela aresta.

>                           RDr
>                      L             s
>                 DRr             RrD
>                     s                L
>                  DrR              rRD
>                      L              s
>                            rDR

Assim, pode-se ver as condições necessárias para cada ordem de chegada:

RDr:

L par >= 0 e s par >= 0

RrD:

L par >= 0 e s ímpar >=1
ou
L ímpar >=3 s par >=2

DRr:

L ímpar >= 1 e s par >=0
ou
L par >=2 e s ímpar >=3

DrR:

L e s ímpares >= 1
ou
L e s pares >= 2

rRD:

L e s ímpares >= 1
ou
L e s pares >= 2

rDR:

L par >=2 e s ímpar >=1
ou
L ímpar >=1 e s par >=2

----- Original Message -----
From: Eduardo Azevedo <eduardo_az@bridge.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Thursday, December 13, 2001 10:11 PM
Subject: Re: ITA 2002 - Problema 12 outra solução - grafos


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