[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>
=========================================================================