Simulado de Combinatória

Prévia do material em texto

DRAFT
Estudante:
Colégio:
Data: / / 2017
Simulado 10 - NIII’vel 2 - Combinato’ria - PrincIII’pio da Casa dos Pombos
i) Resolva cada questão em folha separada de modo claro e organizado.
ii) Os primeiros dois problemas certos valem 4 pontos (divididos igualmente entre os subitens existentes), os
demais valem 2.
iii) Não é permitido qualquer tipo de consulta.
Nota
Problema 1. Define-se como “par de meias” o conjunto com duas meias da mesma cor. Uma gaveta contém 100
meias vermelhas, 80 verdes, 60 azuis e 40 pretas. Paulo, para não acordar seu irmão, entra no quarto com as luzes
apagadas e pega meias aleatoriamente nessa gaveta, sem devolvê-las.
a) Qual o número mı́nimo de meias que precisam ser retiradas para garantir a existência de ao menos 1 par de
meias?
b) Qual o número mı́nimo de meias que precisam ser retiradas para garantir a existência de ao menos 10 pares de
meias da mesma cor?
c) Qual o número mı́nimo de meias que precisam ser retiradas para garantir a existência de ao menos 2 pares de
meias?
d) Qual o número mı́nimo de meias que precisam ser retiradas para garantir a existência de ao menos 10 pares de
meias?
Problema 2. Nomeie um conjunto de discos da seguinte maneira:
• um disco com o número 1;
• dois discos com o número 2;
• três discos com o número 3;
• e assim por diante até termos cinquenta discos com o número 50.
Coloque todos esses discos numerados numa caixa de modo aleatório e comece a retirá-los depois de misturados.
a) Quantos discos há na caixa?
b) Qual o número mı́nimo de retiradas que garantem ao menos 5 discos com o mesmo número?
Problema 3. Seja S um subconjunto de A = {1, 2, 3 . . . , 50} tal que não há par de elementos distintos em S cuja soma
seja divisı́vel por 7. Qual o número máximo de elementos de S?
Professor Tiago Miranda | 2
Respostas e Soluc, o’‘’ es.
Problema 1. Define-se como “par de meias” o conjunto com duas meias da mesma cor. Uma gaveta contém 100
meias vermelhas, 80 verdes, 60 azuis e 40 pretas. Paulo, para não acordar seu irmão, entra no quarto com as luzes
apagadas e pega meias aleatoriamente nessa gaveta, sem devolvê-las.
a) Qual o número mı́nimo de meias que precisam ser retiradas para garantir a existência de ao menos 1 par de
meias?
b) Qual o número mı́nimo de meias que precisam ser retiradas para garantir a existência de ao menos 10 pares de
meias da mesma cor?
c) Qual o número mı́nimo de meias que precisam ser retiradas para garantir a existência de ao menos 2 pares de
meias?
d) Qual o número mı́nimo de meias que precisam ser retiradas para garantir a existência de ao menos 10 pares de
meias?
Soluc, a’‘’ o para o Problema 1. (AIME [modificado])
a) Para retirar uma par, deve-se imaginar o pior cenário, tal que seriam retiradas uma de cada tipo nas quatro
primeiras pegadas e aı́ precisaria de uma adicional para garantir o par, ou seja 5 meias.
b) Agora, no pior cenário para obter 10 pares de mesma cor, usando o raciocı́nio anterior, você tiraria 19 de cada
tipo, mais uma para o par (independentemente na cor), ou seja, 4 · 19 + 1 = 77 meias.
c) Usando a letra (a), temos 5 meias para o primeiro par. Assim, a 6a meia pode ser da cor do mesmo par que
já temos, daı́ garantirı́amos ter todas as cores com um pé de meia, e a 7a meia garantirá mais uma repetição.
Portanto, precisa retirar 7 meias para garantir dois pares.
d) Perceba que, no pior cenário, Paulo retirará a partir da 5a meia, sempre a mesma cor (por exemplo, vermelha,
nas outras 18 retiradas) até conseguir o décimo par, isto resulta em 5 + 18 = 23 retiradas. Se retirar alguma meia
diferente de vermelha, esta formará par com alguma das iniciais, reduzindo o número de tentativas. Assim, o
quantidade mı́nima que garante os dez pares de meias solicitados é 23.
Problema 2. Nomeie um conjunto de discos da seguinte maneira:
• um disco com o número 1;
• dois discos com o número 2;
• três discos com o número 3;
• e assim por diante até termos cinquenta discos com o número 50.
Coloque todos esses discos numerados numa caixa de modo aleatório e comece a retirá-los depois de misturados.
a) Quantos discos há na caixa?
b) Qual o número mı́nimo de retiradas que garantem ao menos 5 discos com o mesmo número?
Soluc, a’‘’ o para o Problema 2. (AIME [modificado])
a) Basta procedermos com a soma
1 + 2 + 3 + . . . + 50 =
(1 + 50) · 50
2
= 51 · 25 = 1275 discos.
b) O pior cenário é começar retirando todos os que não completam 5 repetições, ou seja, os discos de 1 até 4,
totalizando 1 + 2 + 3 + 4 = 10 discos. Depois, de 5 até 50 pode acontecer de saı́rem 4 de cada tipo, resultando
em 4 · (50 − 5 + 1) = 186. Agora, o próximo disco repetirá algum dos anteriores, garantindo o quinto disco de
algum tipo entre 5 e 50. Assim, o número mı́nimo de retiradas que garantem cinco discos com mesmo número é
10 + 184 + 1 = 195.
Professor Tiago Miranda | 3
Problema 3. Seja S um subconjunto de A = {1, 2, 3 . . . , 50} tal que não há par de elementos distintos em S cuja soma
seja divisı́vel por 7. Qual o número máximo de elementos de S?
Soluc, a’‘’ o para o Problema 3. Particione A em sete subconjuntos Ai‘s, 0 6 i 6 6, tais que todos os elementos de
Ai são congruentes a i módulo 7. Assim, S só pode ter um elemento de A0, e se algum elemento de Ai pertence a S,
então todos os elementos também podem pertencer. Além disso, S não podem ter concomitantemente elementos de
A1 e A6, ou A2 e A5, ou A3 e A4. Como |A1| = 8 e cada um dos outros subconjuntos têm cardinalidade 7, o máximo
número de elementos de S terá um elemento de A0, todos de A1 (ou de A6), todos de A2 (ou de A5), todos de A3
(ou de A4), resultando em
máx|S| = 1 + 8 + 7 + 7 = 23 elementos.
� � � � � � � � � �
Elaborado pelo professor:
Tiago Miranda