Podemos resolver esse problema usando Teoria dos Grafos.
Criamos um conjunto X de v�ritices que representam os n�meros e um conjunto
Y de v�rtices que representam as cartas.
|X| = |Y| = 100.
Para cada v�rtice x em X, adicionamos uma aresta (x,y) para cada uma das
duas cartas y em que o n�mero x aparece.
Dessa forma criamos um grafo bipartido, ou bigrafo-X,Y. Um bigrafo-X,Y
significa que n�o h� arestas entre elementos do conjunto X ou entre
elementos do conjunto Y.
Assim queremos um casamento total entre os n�meros em X com as cartas em Y.
Um n�mero x casado com uma carta y significa que a carta y estar� com o
n�mero x voltado para cima.
Pelo Teorema de Hall, um bigrafo G tem um casamento que satura X se, e
somente se, |N(S)| >= |S| para todo subconjunto S de X
Um casamento que satura X � que casa todos seus elementos. � o que
procuramos.
N(S) � a vizinhan�a dos v�rtices em S.
Sendo S um subconjunto de X, considere o subgrafo induzido por S uni�o N(S).
O n�mero de arestas E ser� 2.|S|, pois cada n�mero em S se liga a duas
cartas em N(S)
Mas pelo "Primeiro Teorema da Teoria dos Grafos" temos
2.E = Soma{v em S U N(S)} d(v)
Onde d(v) � o n�mero de arestas incidentes a v
Ent�o, como S e N(S) s�o disjuntos:
4.|S| = [Soma{v em S} d(v)] + [Soma{v em N(S)}d(v)]
Como d(v) = 2 para todo v em S temos
4.|S| = 2.|S| + Soma{v em N(S)}d(v)
Soma{v em N(S)}d(v) = 2.|S|
Mas d(v) <= 2 para todo v em N(S), pois cada carta se liga ao no m�ximo dois
n�meros, ent�o
Soma{v em N(S)} 2 >= Soma{v em N(S)}d(v) = 2|S|
2.|N(S)| >= 2.|S|
|N(S)| >= |S|
Assim conseguimos a condi��o necess�rio no Teorema de Hall para provar que
existe um casamento que cubra todos os n�meros em X.
Isso vale para qquer quantidade de n�meros e dois baralhos, em particular
para 100 n�meros, o que resolve o problema proposto.
At� mais
Vinicius Fortuna
----- Original Message -----
From: "Paulo Santa Rita" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Wednesday, August 14, 2002 8:00 PM
Subject: [obm-l] Re: [obm-l] Tradu��o de Problema
> 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" <[EMAIL PROTECTED]>
> >Reply-To: [EMAIL PROTECTED]
> >To: <[EMAIL PROTECTED]>
> >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 � <[EMAIL PROTECTED]>
=========================================================================
