[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 [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.
[obm-l] Re: [obm-l] Re: [obm-l] Tradução de Problema
Paulo, eu estava lendo o problema achando que ele iria pedir outra coisa, por isso minha dificuldade de interpretar o óbvio. Agora que consegui entender, agradeço pelas suas palavras. Encontrei um algoritmo muito simples, provavelmente o que a banca tinha em mente. Misture os dois baralhos, o que vamos ter são cartas (A|B) de forma que A é diferente de B e cada número aparece em exatamente duas cartas. Comece pela carta (1|X) aí encontre a carta (X|Y) e assim por diante até que se chegue a (Z|1). Formamos uma roda desses dominós, por exemplo: (1|5), (5|2), (2|91), (91|56), (56|1). Pegamos um dominó dos que não foram escolhidos e fazemos uma roda do mesmo jeito. No final vamos ter uma porção de rodas. Colocamos os dominós na mesa na ordem da roda: (1|5), (5|2), (2|91), (91|56), (56|1). Daí cada dois números iguais vão estar em posições opostas, portanto temos a construção pedida. Eduardo. From: Paulo Santa Rita [EMAIL PROTECTED] 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] = _ 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 é [EMAIL PROTECTED] = = 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]
