[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Re: [obm-l] Re: [obm-l] Tradução de Problema
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" <p_ssr@hotmail.com>
To: <obm-l@mat.puc-rio.br>
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" <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>
=========================================================================