Questões resolvidas de Análise Combinatória

Vamos resolver, passo a passo, algumas questões de vestibulares e competições de matemática sobre Análise Combinatória. Não faz a mínima ideia do que seja isso? Confira meu post anterior: Analisando a análise combinatória.

Fuvest-SP

O jogo da sena consiste no sorteio de 6 números distintos, escolhidos ao acaso, entre os números 1, 2, ..., até 50. Uma aposta consiste na escolha (pelo apostador) de 6 números distintos entre os 50 possíveis, sendo premiadas aquelas que acertarem 4 (quadra), 5 (quina) ou todos os 6 (sena) números sorteados.

Um apostador, que dispõe de muito dinheiro para jogar, escolhe 20 números e faz todos os 38.700 jogos possíveis de serem realizados com esses 20 números. Realizado o sorteio, ele verifica que todos os 6 números sorteados estão entre os 20 que ele escolheu. Além de uma aposta premiada com a sena:

a) Quantas apostas premiadas com a quina esse apostador conseguiu?
b) Quantas apostas premiadas com a quadra ele conseguiu?

A questão a) é simples: para 5 números da aposta temos a combinação dos 6 números sorteados tomados de 5 a 5 e para o último podemos escolher qualquer um dos 20 - 6 = 14 restantes. Pelo princípio multiplicativo, nossa resposta será:

$$ \binom{6}{5} \times 14 = 6 \times 14 = \mathbf{84} $$

A b) é parecida, mas agora temos 4 números da aposta para a combinação dos 6 números sorteados tomados de 4 a 4. Concorda que os 2 números restantes serão uma combinação dos 14 restantes tomados de 2 a 2? Portanto:

$$ \binom{6}{4} \times \binom{14}{2} = 15 \times 91 = \mathbf{1365} $$

OBM - 2007

Um número de quatro dígitos é dito peroba se possui pelo menos dois dígitos vizinhos com a mesma paridade. Quantos números perobas existem?

A) 8999
B) 8874
C) 7875
D) 8000
E) 7750

Há muitos casos nos quais um número é peroba. Por exemplo:

par-par-par-ímpar
par-par-ímpar-ímpar
par-ímpar-ímpar-ímpar
par-par-par-par
ímpar-ímpar-ímpar-ímpar

Então não é mais fácil descobrir quantos números não são peroba e subtrair do total de números de 4 dígitos (9000)? Vejamos quais casos são esses e calcular quantos números se enquadram neles:

par-ímpar-par-ímpar: 4 * 5 * 5 * 5 = 500 números (note que 0 não é um primeiro algarismo válido)
ímpar-par-ímpar-par: 5 * 5 * 5 * 5 = 625 números

Logo, existem 9000 - 1125 = 7875 números peroba. Alternativa c, portanto.

OBM - 2008

Arnaldo, Bernaldo, Cernaldo e Dernaldo baralharam as 52 cartas de um baralho e distribuíram 13 cartas para cada um. Arnaldo ficou surpreso: "Que estranho, não tenho nenhuma carta de espadas". Qual a probabilidade de Bernaldo também não ter cartas de espadas?

Precisamos calcular a probabilidade de Bernaldo não ter cartas de espadas, dentre todas as possibilidades de distribuição se Arnaldo não tem cartas de espadas. Primeiro vamos ver o que acontece se Arnaldo não tiver cartas de espada:

Para Arnaldo temos uma combinação de 39 elementos tomados de 13 a 13, para Bernaldo também (ele pode receber uma das 13 cartas de espada), para Cernaldo uma combinação de 26 elementos tomados de 13 a 13, e para Dernaldo só sobra uma possibilidade. Assim:

$$ A = \binom{39}{13} \times \binom{39}{13} \times \binom{26}{13} $$

Agora vamos supor que Bernaldo também não tenha cartas de espadas. Assim, para Arnaldo temos uma combinação de 39 elementos tomados de 13 a 13, para Bernaldo uma combinação de 26 elementos tomados de 13 a 13, para Cernaldo uma combinação de 26 elementos tomados de 13 a 13 e para Dernaldo há apenas uma possibilidade. Pelo princípio multiplicativo:

$$ B = \binom{39}{13} \times \binom{26}{13} \times \binom{26}{13} $$

Agora basta calcular B/A, que realizando os cálculos e simplificando nos dá a resposta:

$$ \frac{B}{A} = \frac{26!26!}{13!39!} $$

Unitau-SP

Sendo n ≠ 0, o(s) valor(es) de n tal que

$$ \frac{(n + 1)! - n!}{(n - 1)!} = 7n $$

é(são):

a) 7.
b) 0 e 7.
c) 0 e 10.
d) 1.
e) 0 e 2.

Uma questão puramente algébrica que aborda o conceito de fatorial. Lembra da definição? n! = n * (n - 1) * (n - 2) * ... * 1. Dessa definição concluímos que n! = n * (n - 1)!, concorda? Vamos tentar utilizar esse fato para simplificar a expressão acima:

$$ \begin{align*}
\frac{n!(n + 1) - n!}{(n - 1)!} &= 7n \\
\frac{n!(n + 1 - 1)}{(n - 1)!} &= 7n \\
n!n &= 7n(n - 1)! \\
n(n - 1)! &= 7(n - 1)! \\
n &= 7
\end{align*} $$

Assim, concluímos que a alternativa correta é a).

UFSC

Sobre uma reta são marcados 7 pontos, e sobre uma outra reta, paralela à primeira, 3 pontos. Qual é o número de triângulos com vértices em três desses pontos?

O problema equivale a descobrir quantas combinações de 10 pontos tomados de 3 a 3 podemos formar, tomando o cuidado de excluir as combinações de três pontos tomados na mesma reta. Assim, nossa resposta é:

$$ \binom{10}{3} - \binom{7}{3} - \binom{3}{3} = \mathbf{84}$$

Resolução dos problemas do post sobre Análise Combinatória

Lembra-se do meu post sobre análise combinatória? Não se preocupe, não me esqueci das questões que propus. Vamos lá:

1 - Este aqui é bem direto. Temos 5 possibilidades para a primeira letra, 4 para a segunda, 3 para a terceira, 2 para a quarta e 1 para a quinta. Logo, 5! = 120.

2 - Se o número é maior do que 1000, podemos formar números de 4 ou 5 dígitos com os dígitos 3, 4, 6, 8, 9. Assim, temos 5 possibilidades para o primeiro dígito, 4 para o segundo, 3 para o terceiro, 2 para o quarto e 2 para o quinto. Por que 2 para o quinto? Simples: pode ser um algarismo ou nada. Logo, temos 5 * 4 * 3 * 2 * 2 = 2 * 5! = 240.

3 -

a) Ok, normalmente teríamos uma permutação simples de 6 elementos, equivalente a 6! = 720 anagramas. Mas aí precisamos considerar que a troca de elementos iguais constitui uma repetição, como lembra o enunciado. Concorda que, dos 720 anagramas, temos um número x de anagramas únicos multiplicados pelas permutações das letras que se repetem? Ilustrando:

"banana" => "banana"

O que eu fiz foi trocar os 'n' de lugar. Note que isso equivale a uma permutação de 2 elementos. O mesmo raciocínio aplica-se aos 'a', pois as repetições equivalem a uma permutação de 3 elementos, e 3! = 6. Logo, temos:

720 = x * repetições de a * repetições de n
720 = x * 2! * 3!
x = 720/2!3!
x = 720/12 = 60 anagramas

b) Seguindo o raciocínio acima, é fácil ver que, dados n elementos com repetição do elemento a1 n1 vezes, a2 n2 vezes, ..., ak nk vezes, o total de permutações é dado por:

n!/(n1!n2!...nk!)

4 -

a) Fácil, 6 * 6 * 6 * 6 * 6 * 6 = 6^6 elementos.
b) Generalizando, uma permutação com repetição de n elementos é dada por n^n.

5 - Normalmente teríamos 5! = 120 agrupamentos distintos, mas concordam que os dois agrupamentos abaixo são equivalentes?

Ou seja, simplesmente rotacionar os elementos não muda nada. Note que rotacionar significa mover a criança da posição A para a B, da B para a C... e assim sucessivamente. Em nosso caso, podemos rotacionar 5 vezes até as crianças voltarem à posição inicial. Sabendo que:

120 = x * repetições

Sendo x o número de modos únicos de dispor as crianças, temos:

120 = x * 5
x = 120/5 = 24

Note que isso equivale a 4!, ou seja, (5 - 1)!. De fato, dados n elementos, o número de permutações circulares é (n - 1)!.

6 - A análise combinatória pode surgir em oportunidades inusitadas como esta, reforçando a importância do tópico. Bem, primeiro vamos fatorar 2800 e ver o que acontece:

2800 = 2 * 1400 = 2² * 700 = 2³ * 350 = 2^4 * 175 = 2^4 * 5 * 35 = 2^4 * 5² * 7

Isso nos garante que todo divisor de 2800 tem a forma 2^m * 5^n * 7^o, com as condições:

0 <= m <= 4
0 <= n <= 2
0 <= o <= 1

Portanto, temos 5 possibilidades para o primeiro expoente m, 3 para o expoente n e 2 para o expoente o (não se esqueça de contar o 0). Portanto, temos 5 * 3 * 2 = 30 divisores.