[obm-l] Re: [obm-l] Tradução de Problema

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

Ola Duda e demais colegas
desta lista ... OBM-L

O que precisa ser mostrado é exatamente o que pede o enunciado do problema : 
as cem cartas sobre a mesa com os numeros de 1 a 100 visiveis, sem faltar 
nenhum deles ...

Em que consiste o problema ?

Nao e evidente que - INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM GRAFADOS 
NOS DOIS BARALHOS - seja possivel exibir os 100 numeros, sem que haja 
omissao de algum numero. A parte matematica ( algoritmica )da questao 
consiste precisamente em mostrar que uma tal exibicao sempre é possivel.

Uma parafrase do problema pode ser : Mostre como isabel pode escolher cada 
carta, determinando qual numero ficara por cima e qual ficara por baixo, de 
forma que no final da centesima escolha as faces visiveis exponham os 100 
numeros naturais.

Uma sintaxe adequada pode ser :

Sejam A e B os baralhos. Ao escolher uma carta de um dos baralhos ( digamos, 
do baralho A ) teremos um par (V,I) em que V e o numero que ficara pra cima 
( visicel ) e I o numero que ficara pra baixo ( invisivel ).O Mesmo vale 
para o baralho B.

O inicio de um algoritmo pode ser :

1) Escolha a carta do baralho A onde esta o numero 1. Seja X o numero que 
acompanha 1 no baralho A. Colocamos a carta na forma (1,X).
2) Procure a carta do baralho B que tem o numero X. Seja Y o numero que 
acompanha o numero X no baralho B. Colocamos esta carta na forma (X,Y)
3) Y=1 ?
Se nao, procure no baralho A ...

E assim sucessivamente. Voce deve mostrar que o algoritmo descrito permite - 
INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM GRAFADOS NOS DOIS BARALHOS - 
exibir as 100 cartas com  os 100 numeros visiveis, sem que nenhum seja 
omitido.

Eu nao parei para analisar se o algoritmo acima funciona. Estou apenas 
explicando o que e problematico e o que o problema requer. Muito 
provavelmente ha um algoritmo otimo para a questao, que e trivial.

Um abraco a Todos
Paulo Santa Rita
4,1958,140802

>From: "Eduardo Casagrande Stabel" <dudasta@terra.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>Subject: [obm-l] Tradução de Problema
>Date: Wed, 14 Aug 2002 18:15:53 -0300
>
>Olá pessoal da lista,
>
>alguém sabe como eu devo interpretar o seguinte problema?
>
>Isabel tem dois baralhos, cada um com 50 cartas.  Em cada um dos baralhos
>estão escritos os números de 1 a 100 (em cada carta estão escritos dois
>números, um em cada face da carta).  Por um defeito de fabricação, a
>distribuição dos números nas cartas não é a mesma nos dois baralhos (por
>exemplo, em um dos baralhos o 1 aparece na mesma carta do 2; no outro, o 1
>aparece com o 76). Mostre como Isabel deve fazer para que, ao colocar as 
>100
>cartas sobre uma mesa, as faces voltadas para cima mostrem todos os números
>de 1 a 100.
>
>Eu não entendi o que precisa ser mostrado, para mim não está nada claro sob
>que condições ela pode colocar as cartas na mesa, alguém sabe?
>
>Valeu!
>Eduardo.
>Porto Alegre, RS.
>
>PS. caiu na obm de 2000, fase 3, níveis 1 e 2.
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>O administrador desta lista é <nicolau@mat.puc-rio.br>
>=========================================================================




_________________________________________________________________
Tenha você também um MSN Hotmail, o maior webmail do mundo: 
http://www.hotmail.com/br

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================