[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Loteria Matemática / olimpiada
Caro Rafael:
Consegui fazer os itens (a) e (b).
Suponha que cada cartão é um subconjunto de 6 elementos de {1,2,3,...,36}.
Considere os seguintes cartões:
C1 = {1,2,3,4,5,6}
C2 = {5,6,7,8,9,10}
C3 = {9,10,11,12,13,14}
C4 = {1,2,7,8,13,14}
C5 = {15,16,17,18,19,20}
C6 = {19,20,21,22,23,24}
C7 = {23,24,25,26,27,28}
C8 = {15,16,21,22,27,28}
C9 = {29,30,31,32,33,34}
Forme os conjuntos:
A = C1 U C2 U C3 U C4
B = C5 U C6 U C7 U C8
Seja T um subconjunto qualquer de {1,2,...,36} com 6 elemnetos
Repare que cada elemento de A aparece em um ou dois dos cartões C1, C2, C3 e
C4 (3,4,11 and 12 em apenas um e os demais números em dois). Idem para B.
Se T intercepta A (B) em no máximo 2 elementos, então um dos cartões que
compõem A (B) é disjunto de T.
Para ver isso, você não precisa checar cada um dos C(14,2) = 91 pares de
números de A. Basta reparar que existem apenas 3 tipos diferentes de tais
pares:
1. Aqueles nos quais ambos os números aparecem em apenas um cartão (6 pares)
2. Aqueles nos quais um número aparece em um cartão e o outro em dois
cartões (40 pares)
3. Aqueles em que ambos os números aparecem em dois cartões (45 pares)
e fazer a verificação apenas para um par representativo de cada tipo.
Por exemplo, se T & A = {3,4} ("&" = interseção) ou T & A = {1,3} ou T & A =
{1,2} então T & C2 = conjunto vazio.
Idem para B.
Se T intercepta A e B em três ou mais elementos, então (como |T| = 6 ), T
intercepta cada um em exatamente 3 elementos ==> T é disjunto de C9.
Conclusão: um desses 9 cartões é um "vencedor".
***************
Para provar que 8 cartões são insuficientes para se ter certeza de ganhar,
basta mostrar que, dados 8 cartões quaisquer, é sempre possível encontrar um
subconjunto T de {1,2,...,36} com 6 elementos que intercepta cada um destes
8 cartões.
Suponha que os 8 cartões sejam dados.
Temos dois casos a considerar:
1. Existe um número em {1,2,...,36} que pertence a 3 (ou mais) cartões
distintos:
Nesse caso, tome este número e um número de cada um dos 5 cartões restantes
a fim de formar um conjunto T que intercepta cada cartão.
2. Quaisquer 3 cartões distintos têm interseção vazia:
Aqui a idéia é mostrar que existem 4 cartões distintos (por exemplo, C1, C2,
C3 e C4) tais que C1 & C2 é não vazia e que C3 & C4 é não vazia. Se este for
o caso, basta tomar um elemento de C1 & C2, um elemento de C3 & C4, e um
elemento de cada um dos cartões restantes C5, C6, C7 e C8 a fim de formar um
conjunto T, de 6 elementos, que intercepta cada cartão em pelo menos um
número, o que prova o resultado.
Inicialmente, é sempre possível achar C1 e C2 tais que C1 & C2 é não vazia,
uma vez que 8 cartões têm 8*6 = 48 posições que devem ser ocupadas por
números de um conjunto com apenas 36 elementos (e cada cartão com 6 números
distintos) Portanto, pelo princípio das gavetas, existe um número em
{1,2,...,36} que deve constar de dois cartões. Chame estes cartões de C1 e
C2.
Se, dentre os 6 cartões restantes, existirem dois com interseção não vazia,
então o resultado estará provado.
Caso contrário, teremos 6 cartões disjuntos, de forma que:
| C3 U C4 U C5 U C6 U C7 U C8 | = |C3| + |C4| + |C5| + |C6| + |C7| + |C8| =
6*6 = 36
Em outras palavras: C3 U C4 U ... U C8 = {1,2,...,36}.
Se existirem "i" e "j" ( 3 <= i < j <= 8 ) tais que C1 intercepta Ci e C2
intercepta Cj, então (após re-nomear os cartões) o resultado estará provado.
Por outro lado, se C1 & Ci = conjunto vazio ( 3 <= i <= 8 ), então cada Ci
deve interceptar C2. Além disso, como os 6 Ci ( 3 <= i <= 8) são disjuntos
dois a dois, cada um intercepta C2 num número (elemento) distinto. No
entanto, por hipótese, C1 intercepta C2 em pelo menos um número. Isso quer
dizer que, no final das contas, um dos Ci intercepta C1 ==> contradição.
Logo, existem cartões distintos Ci e Cj ( 3 <= i < j <= 8 ) tais que C1
intercepta Ci e C2 intercepta Cj e o resultado está provado.
Um abraço,
Claudio.
----- Original Message -----
From: "Rafael" <matduvidas@yahoo.com.br>
To: "OBM" <obm-l@mat.puc-rio.br>
Sent: Friday, January 24, 2003 7:28 PM
Subject: [obm-l] olimpiada
Não consigo resolver essa questão que me disseram que
foi aplicada pela OBM. Se alguém souber me explicar ou
se esta resposta já estiver em algum lugar da Internet
que não achei, agradeceria.
5 - O cartão da "Loteria Matemática" é um tabuleiro 6
x 6. O apostador marca 6 cruzes em seis casas do
cartão e envia ao concurso. O cartão oficial é
publicado no jornal, com seis cruzes marcadas que
indicam as seis casas perdedoras. O apostador ganha se
não marcou nenhuma cruz em uma casa perdedora.
a) Marcar e demonstrar que o jogador pode
preencher 9 cartões de modo que pelo menos um deles
seja ganhador.
b) Demonstrar que 8 cartões não são suficientes
para ter certeza de ganhar.
E se o tabuleiro for 10 x 10. O apostador marca 20
cruzes em 20 casas do cartão e envia ao concurso. O
cartão oficial é publicado no jornal, com 20 cruzes
marcadas que indicam as 20 casas perdedoras. O
apostador ganha se não marcou nenhuma cruz em uma casa
perdedora.
c) Marcar e demonstrar quantos cartões deve
preencher o jogador de modo que pelo menos um deles
seja ganhador.
d) Demonstrar quantos cartões não são suficientes
para ter certeza de ganhar.
Abraços,
Rafael.
__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com
=========================================================================
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>
=========================================================================
=========================================================================
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>
=========================================================================