Plínio, Estrada - Problemas Resolvidos de Combinatória
Plínio, Estrada - Problemas Resolvidos de Combinatória
Plínio, Estrada - Problemas Resolvidos de Combinatória
J;
VV* CIÊNCIA MODERNA
Problemas Resolvidos de Combinatória - 2a Edição
FICHA CATALOGRÁFICA
Parte I Problemas 1
Combinatória básica 3
Princípio da Inclusão e Exclusão 26
Funções geradoras e partições 30
Princípio da Casa dos Pombos 35
Probabilidade 37
Parte II Resoluções 45
Combinatória básica 47
Princípio da Inclusão e Exclusão 130
Funções geradoras e partições 149
Princípio da Casa dos Pombos 172
Probabilidade 178
Referências Bibliográficas 203
Prefácio
Este livro de problemas de combinatória, com soluções, foi escrito com o objetivo
principal de servir de complementação a textos básicos de Matemática Discreta
adotados na graduação. De forma particular, tivemos em mente o livro Introdução
à Análise Combinatória, publicado pela Editora Ciência Moderna1, do qual o
primeiro autor deste livro é um dos co-autores e que tem sido adotado por várias
universidades além da Unicamp. Vale destacar que muitos dos problemas aqui
apresentados poderão servir aos professores do ensino médio e principalmente
na preparação para o exame de vestibular. O texto inclui questões que, em sua
maioria, podem ser resolvidas apenas com ferramentas vistas em cursos iniciais de
Matemática Discreta. Incluímos muitas questões relacionadas a aplicações sim
ples dos Princípios Aditivo e Multiplicativo. Em muitos problemas fazemos uso
do Princípio da Inclusão e Exclusão nos quais, por exemplo, obtemos fórmulas
explícitas para a função 0 de Euler e para o número de funções sobrejetoras
f : A —> B. Funções geradoras são usadas em várias ocasiões, tendo como im
portante e simples aplicação a demonstração da existência e unicidade da re
presentação de um inteiro em uma base qualquer b (b inteiro > 2). Outras in
teressantes aplicações envolvem o conceito de partições de um inteiro. Incluímos,
também, questões sobre probabilidade, que são pouco exploradas em textos de
Matemática Discreta. O Princípio da Casa dos Pombos, que nos permite obter
informações relacionadas a questões de existência, é utilizado em vários proble
mas.
Nesta segunda edição, além de várias correções, decidimos separar os proble
mas por grupos com o objetivo de facilitar, aos leitores, a localização de questões
de seu interesse. A um professor do ensino médio, por exemplo, a localização de
questões de seu particular interesse será facilitada pelo conjunto que chamamos
“Combinatória básica”, em que são encontrados 129 problemas daquele nível.
São 22 problemas envolvendo o uso do Princípio da Inclusão e Exclusão. So
bre funções geradoras e partições, são apresentados 20 problemas. Questões de
xistência que envolvem o Princípio da Casa dos Pombos estão contidas nos 9
roblemas daquele grupo. Finalmente, no grupo de probabilidade, são dados 29
roblemas.
Seria interessante mencionar que 1800 exemplares do livro “Introdução à
Lnálise Combinatória”, mencionado acima, e para o qual este foi escrito com
i objetivo de servir de complementação, foram adquiridos pelo IMPA (Instituto
le Matemática Pura e Aplicada) para distribuição aos alunos classificados nas
Olimpíadas Brasileiras de Matemática das Escolas Públicas e que participam do
5rograma de Iniciação Científica.
Agradecimentos
l.’
Parte I
Problemas
Parte I. Problemas - Combinatória básica 3
Combinatória básica
1. Há 5 estradas distintas ligando as cidades A e B, 3 distintas ligando B e C
e 2 distintas ligando AeC, diretamente.
(a) a primeira carta seja um valete e a segunda não seja uma dama?
(b) a primeira carta seja de copas e a segunda não seja um rei?
6. Quantas coleções não vazias de letras podem ser formadas com n A’s, n
B’s, n C’s e n D's?
9. 7 moças e 5 rapazes vão jogar vôlei. De quantas maneiras eles podem ser
divididos em 2 grupos de 6 jogadores cada, de modo que os rapazes não
fiquem todos no mesmo grupo?
10. (a) Encontre o número de retângulos que podem ser formados num tabu
leiro de xadrez 8x8, isto é, o número de retângulos da forma i x j, para
i e j inteiros tais que l<i<8el<j<8 (desconsidere simetrias do
tabuleiro de xadrez ou, em outras palavras, considere-o fixo em relação
àquele que efetua a contagem dos retângulos).
(b) Generalize o resultado do item anterior paia um tabuleiro de xadrez
m x n (na verdade, um retângulo quadriculado m x n cujas casas são
alternadas nas cores preta e branca).
11. Maria tem 7 livros diferentes e Alberto tem 9 livros diferentes. De quantas
maneiras Maria e Alberto podem trocar 3 livros entre si?
12. De quantas maneiras 8 contas distintas podem ser colocadas num cordão
elástico de modo a formar uma pulseira?
(a) Qual o número total de seleções não vazias que podem ser feitas a
partir das letras de tal expressão?
(b) A partir dessas mesmas letras, quantas seleções de 3 letras podem ser
feitas?
Parte I. Problemas - Combinatória básica 5
(a) Quantas seleções de 4 letras podem ser feitas a partir de suas letras?
(b) Quantas permutações de 4 letras podem ser feitas a partir de suas
letras?
(a) Quantas permutações podem ser feitas com suas letras, de modo que
consoantes e vogais se alternem?
(b) Quantas permutações de 4 letras podem ser feitas sem que as 3 letras
o apareçam juntas?
30. De quantas maneiras 18 objetos distintos podem ser divididos entre 5 pes
soas de modo que:
(a) 4 pessoas fiquem com 4 objetos cada e uma fique com 2 objetos?
(b) 3 pessoas recebam 4 objetos cada e as outras duas recebam 3 cada
uma?
31. Considerando que haja 14 tipos de objetos e 2 objetos de cada tipo, encontre
o total de seleções nas quais pelo menos um objeto é selecionado.
Parte I. Problemas - Combinatória básica 7
32. Havendo 20 tipos de objetos e 9 objetos de cada tipo, mostre que o número
total de seleções distintas não vazias que podem ser feitas é igual a
99.999.999.999.999.999.999 (um número com vinte algarismos iguais a 9).
35. Em quantos dos números menores do que um milhão não ocorrem números
idênticos pareados (isto é, não aparecem os blocos 11, 22 etc.)?
(a) De quantas maneiras podemos nele dispor uma torre branca e uma
torre preta de modo que cada uma esteja em condições de atacar a
outra? - ■ ; ,
Problemas Resolvidos de Combinatória
(Sugestão: Para resolver este exercício, é muito útil que se trabalhe com um
labuh iro de xadrez de maneira concreta, executando movimentos com as
peças a fim de compreender as situações em questão)
45. Considere um aparelho para tocar CDs (Compact Disk Plaver) com espa- .,
para 6 CDs. A bandeja que os armazena tem formato circular, sendo qu< c
espaços para os CDs são círculos de mesmo raio cujos centros se encom u.
igualmente espaçados na circunferência única que os contêm. Dispondo <i<
80 CDs distintos, responda o que segue:
coluna 1
linha 0 -------- * ]
/ coluna 2
// coluna 3
linha 1-------- - 1 1
linha 2-------- - J 2 1 coluna 4
linha 3--------- - J 3 3 1 coluna 5
linha 4 - j 4 6 4 1
linha 5--------- * 1J 5 10 10 5 1
que cada número do Triângulo é igual à soma dos dois situados ime
diatamente acima dele (à exceção dos números iguais a 1), estime o
mínimo de adições necessárias ao cálculo de (^).
(b) Generalize o item anterior, encontrando o mínimo de adições necessá
rias ao cálculo de (£).
(a) Tomemos duas moedas distintas que se podem mover apenas diagonal
mente pelo retângulo. Assumamos que, dada uma certa posição inicial
dessas duas moedas em casas do retângulo, todas as posições que re-
sultarem de movimentos diagonais das moedas sejam equivalentes à
posição inicial. Por exemplo, na figura abaixo, as duas configurações
são equivalentes:
Figura 2: Retângulo 8x8 com duas moedas distintas, movendo-se para uma
posição equivalente à inicial.
+ ...
+ n3,
para n > 3.
POLÔNIA
ALEMANHA
RER
L TCHECA
Fsiov;
,AusnaA
(a) Dispondo de m cores diferentes (m > 5), de quantos modos esse mapa
pode ser completamente colorido de tal maneira que países fronteiriços
não sejam pintados da mesma cor?
(b) Satisfazendo as condições do item (a), qual o menor valor de m que
permite colorir o mapa? Quantas são as maneiras de colorir o mapa
nesse caso?
73. Encontrar o número de triângulos que podem ser formados pelos vértices
de um polígono regular de n lados:
(a) não havendo nenhum tipo de restrições sobre os lados dos triângulos;
(b) se os lados do polígono não puderem ser lados dos triângulos.
(a) RADAR;
16 Problemas Resolvidos de Combinatória
(b) AGRAVAM.
78. Uma roda-gigante possui 9 bancos de dois lugares cada um. De quantos
modos 16 crianças podem ocupar 8 de seus bancos, ficando duas em cada
banco?
79. Na figura que vem em seguida, os pontos A e C devem ser unidos por uma
escada, e o segmento BC é perpendicular ao segmento AB. A distância
entre A e B é igual a 6 metros e a distância entre B e C é igual a 2
metros. Sabendo que cada degrau deve ter 25 centímetros de altura e que
a largura de cada degrau deve ser um inteiro múltiplo de 40 centímetros,
de quantas maneiras a escada pode ser construída, considerando-se que o
primeiro degrau deva começar em A e que o último degrau deva terminar
em C?
C
A B
83. A fila do caixa: m-rk pessoas encontram-se na fila do cinema para comprar
seus ingressos, sendo que m delas possuem 10 reais e k possuem 5 reais. O
ingresso custa 5 reais, e o caixa não dispõe de nenhum dinheiro inicialmente.
Isso significa que algumas filas são “ruins” no sentido de que em alguns
pontos o caixa pode ficar sem troco, e outras são “boas”, no sentido de que
o caixa sempre disporá de troco para distribuir aos cinéfilos. Quantas são,
desse modo, as filas “boas” (suponha que m < A:)?
8G. 5 rapazes e 5 moças devem posar para uma fotografia, ocupando õ degraus
de uma escadaria. Supondo que cada degrau deva conter exatamente duas
pessoas, responda:
(a) Do quantas maneiras isso pode ser feito sem nenhuma restrição?
(b) De quantas maneiras isso pode ser feito de modo que em cada degrau
fique um rapaz e uma moça?
S7. De quantas maneiras uni grupo <le 7 pessoas pode ser agraciado com quatro
prêmios diferentes: (todos os prêmios devem ser distribuídos)
88. Tem-se um conjunto de m + n+p objetos, dos quais m são iguais entre si, n
são também iguais entre si (porém distintos dos anteriores), e os p restantes
são todos distintos entre si e dos anteriores. Calcule o número de coleções
não vazias que podemos formar com esses objetos.
89. No quadro abaixo, de quantas maneiras é possível formar a palavra COM
BINATÓRIA partindo-se de um C e indo sempre para a direita ou para
baixo?
C
cO
COM
C OMB
C OM B I
C OMB I N
C O M B I NA
C OMB I NA T
COMBINATÓ
COMB INATÓR
COMBINATÓRI
COMBINATÓRIA
(a)
(Sugestão: considere a identidade i ■ í! = (i + 1)! — il.)
(b) E"=l jrfiy.
(Sugestão: encontre uma igualdade análoga à da sugestão do item an
terior.)
Parte I. Problemas - Combinatória básica 19
98. (a) De quantas maneiras 7 casais podem sentar-se em torno de uma mesa
circular contendo 14 lugares, de modo que não sentem juntos 2 homens
e que cada homem sente ao lado de sua esposa?
(b) De quantos modos 6 casais podem sentar-se em uma roda-gigante com
12 bancos de 2 lugares cada um, de modo a ficarem sempre juntos
marido e mulher?
99. Um homem possui 14 amigos, sendo 6 mulheres e 8 homens; sua esposa pos
sui também 14 amigos, sendo 8 mulheres e 6 homens. De quantas maneiras
20 Problemas Resolvidos de Combinatória
-O- (n — p + 1)
n 0, sendo n,p G N tais que n > p > 1.
E (?)
101. (a) Formam-se as combinações de 8 elementos dos objetos ai, a2, ■ ■ ai2>
escrevendo-se os objetos, em cada uma delas, em ordem crescente de
índices. Em quantas dessas combinações a$ aparece e não ocupa o
terceiro lugar?
(b) Formam-se as combinações de p elementos dos objetos ai, 02, •••>
an (p < n), escrevendo-se os objetos, em cada uma delas, em ordem
crescente de índices. Em quantas dessas combinações ai aparece e não
ocupa o j-ésimo lugar (j < i < n)?
(c) Formam-se as combinações de p elementos dos objetos ai, (Z2, ...,
an (p < n), escrevendo-se os objetos, em cada uma delas, em ordem
crescente de índices. Quantas são as combinações em que o elemento
a, ocupa a j-ésima posição para os casos i > j, i = j e i < j?
102. (a) Dado um polígono convexo de n lados, qual o número máximo de
pontos dc intersecção de suas diagonais?
(b) Dados n pontos de um plano, 3 a 3 não colineares, qual o número
máximo de intersecções das retas formadas por esses pontos, excluindo-
se as intersecções ocorridas nos próprios pontos dados?
103. Têm-se 13 pontos cuja maioria pertence a uma reta r e os restantes se
situam sobre uma paralela a r, denominada s. Tendo esses pontos como
vértices, constróem-se todos os triângulos e quadriláteros possíveis. A razão
entre o número de quadriláteros, não necessariamente convexos, e o número
de triângulos é yj. Qual o número de pontos de cada uma das retas?
104. Suponha que os números inteiros de 1 a 9.999.999 tenham sido escritos
em colunas de tal forma que em cada coluna figurem todos os números
Parte I. Problemas - Combinatória básica 21
formados por um certo conjunto de 7 dígitos (observe que 1.457 pode ser
visto como 0.001.457). Por exemplo, 3.447.645 pertence à mesma coluna do
número 4.745.634, pois o multiconjunto de ambos os números é o mesmo,
mas não pertence à coluna de 5.744.624, pois seus dígitos são distintos dos
deste número. Quantas foram as colunas escritas?
Wl [(:}•©] ■■[(.:>)•(:)]■
para n > 1.
2n »
UM i M 2)+-+ r r
a 4- b
i=0 x \ /
k
para a>keb>k — 1.
22 Problemas Resolvidos de Combinatória
(a) (»)+2(")+3Q)+.••+«(");
(b) (5)+3(í)+5®+- + (2n+l)C);
(c) 1.2®+2-3©+3-4(J)+... + (n-l).nC).
111. Num prédio de seis andares, há 10 pessoas no térreo, prontas para tomar
um elevador que ali se encontra. Admitindo que o elevador possua capaci
dade para apenas 8 pessoas, de quantas maneiras podemos lotá-lo e nele
transportar as pessoas escolhidas, descarregando-as da seguinte maneira:
duas no primeiro andar, uma no segundo, nenhuma no terceiro, uma no
quarto, três no quinto e uma no sexto?
112. Considere uma série de 21 lançamentos de um dado comum de 6 faces. De
quantas maneiras distintas pode ocorrer que a face i apareça i vezes, para
i = 1,2,... ,6.
113. Uma sala de aula possui kr alunos. Uma professora tem elaborados k temas
distintos para trabalho, e deseja dividir a classe em k grupos de r estudantes
cada um. Determine o número de divisões possíveis se:
m 4- n — 1\
n—1 /
C=i)C m + n — p — 1\
. n-p-1 ) +
m + p — 1\ ín — p — 1\
/ p \/m+n—p—2
n-p-1 + ...
+
. P~ 1 An-P-V’
sendo m, n,p G N tais que m + n> 1, n — p> 1.
(b) Através de propriedades dos números binomiais, realize alterações no
resultado do item (a) a fim de provar que:
+
P
vn-’\
'm — n + p
J\n — pJ
para 0 < x± ... < Xk-i < zjt, com a?i, ..., Xk-i, Xk inteiros não negativos.
140. (a) De quantos modos 5 casais podem sentar-se ao redor de uma mesa
circular com número exato de cadeiras de tal forma que marido e
mulher não fiquem juntos?
(b) Generalize o problema para n casais.
141. “Chamamos de função </> de Euler à função que atribui a cada inteiro posi
tivo m o número de inteiros positivos menores do que ou iguais ame rela
tivamente primos com m. ” 7
cSendo a e b valores reais e n um número natural, a fórmula do Binômio de Newton é dada
por:
(a + fe)" = ]T
i=0
(l + zm)n = 1 +
sendo m,n E N.
(b) Considere as seguintes funções de x: f(x) = (1 4- x 4- x2 +---- |- xn)3 e
p(x) = (14-a:4-x24----- l-z71-1)3. Prove, por argumentos combinatórios,
que o coeficiente de x2n+1 em f(x) coincide com o coeficiente de x2n~2
em g(x). Encontre este coeficiente.
155. (a) De quantas maneiras podemos selecionar 275 balas de seis tipos dis
tintos, se cada tipo se apresentar em pacotes de 25 balas cada um, e
devendo as seleções constarem de um a quatro pacotes de cada tipo?
(b) De quantas maneiras podemos dividir 13 livros idênticos de Matemáti
ca, 10 idênticos de Português e 17 idênticos de História entre 2 alunos,
se cada um deve ficar com 20 livros, dos quais pelo menos 2 de cada
matéria?
156. Utilizando a identidade (1 — x2)n = (1 — z)n(l 4- a;)n, prove a fórmula
seguinte:
1=0 \ / \
162. (a) Mostre que o número de partições do inteiro n em três partes é igual
ao número de partições de 2n em três partes menores do que n.
8Denominamos partição de um inteiro n um conjunto de inteiros positivos cuja soma é igual
a n.
9Também chamado “Gráfico de uma partição”, consiste em se dispor pontos no plano,
colocando-se em cada linha, em ordem não crescente, um número de pontos igual a cada uma
das partes que compõem o número particionado em questão. Para maiores esclarecimentos sobre
o assunto, consulte o Capítulo 5 de [13].
10Dizemos que uma partição é autoconjugada se ela é igual à sua conjugada.
32 Problemas Resolvidos de Combinatória
167. (a) Encontre a função geradora para an, o número de triângulos incongru
entes de lados inteiros e perímetro n.
(b) Encontre a função geradora para òn, o número de partições de n em
três partes, nenhuma das quais maior do que a soma das outras duas.
168. No Exercício 164 (item (c)), vemos que o total de maneiras de se dis
tribuírem n objetos distintos em k caixas idênticas sem que nenhuma fique
vazia é denotado por S(n, k), e denominado número de Stirling de segunda
espécie. Este número também pode ser interpretado como o número de
partições de um conjunto de cardinalidade n em exatamente k partes. As
sim, é imediato que S(n, k) conta o total de partições de um conjunto
de n elementos, que é denotado por Bn, e chamado número de Bell.
para n > k.
(b) Encontre uma forma sucinta da função geradora exponencial para
S(n, k), supondo k fixo, isto é, encontre uma simplificação para:
oo n
n=0
(c) Com base no item anterior, encontre uma expressão simplificada para
a função geradora exponencial de Bn.
bn, se n é ímpar
an —
bn 4- tn+i, se n é par.
173. Dada a informação de que um ser humano possui, no máximo, 300.000 fios
de cabelo, e de que a cidade de São Paulo, por um censo recente, tem uma
população de 10.788.682 habitantes, encontre o maior número natural n
que torne a seguinte afirmação verdadeira: há n pessoas em São Paulo com
o mesmo número de fios de cabelo.
a----P
Q
<±.
nq
Parte I. Problemas - Probabilidade 37
Probabilidade
183. (a) A partir dos elementos do conjunto A = {1,2,3,..., n}, obtemos uma
r-seqüência. Supondo que r < n, encontre a probabilidade de que cada
termo de A apareça no máximo uma vez em tal seqüência.
(b) Supondo que a probabilidade de que uma dada pessoa faça aniversário
num dia qualquer do ano seja (um ano possui 365 dias), qual o
menor valor de r que torna a seguinte afirmação verdadeira: a proba
bilidade de que, num grupo de r pessoas, duas façam aniversário no
mesmo dia é maior do que ou igual a
184. Para a Copa do Mundo de Futebol, 24 países, dentre os quais Brasil, Ar
gentina, Alemanha e Itália, são divididos em 6 grupos distintos, contendo
4 equipes cada um. Encontre a probabilidade de que ocorram os seguintes
2 eventos simultaneamente: Brasil e Argentina caiam num mesmo grupo
e Alemanha e Itália caiam também juntos num outro grupo. Encontre
também a probabilidade de que as quatro equipes diferenciadas caiam to
das num mesmo grupo e compare este resultado com o anterior.
13
Galileu Galilei (1564-1642), cientista italiano.
38 Problemas Resolvidos de Combinatória
185. (a) Certa loteria possui 100.000 bilhetes diferentes (a saber, os que marcam
números compreendidos entre 00000 e 99999), dos quais somente um é
premiado em extrações semanais. Um jogador inveterado arrisca todas
as quatro semanas de um mês, comprando um bilhete em cada uma
delas. Seu filho, um jovem estudante, aconselha-o a comprar quatro
bilhetes somente uma semana por mês, pois isto ampliaria suas chances
de ganhar. Tem razão o filho?
(b) Considere que certa loteria possui N bilhetes diferentes, dos quais
somente um é premiado, em extrações periódicas. O jogador A compra
um bilhete em cada um de n períodos, e o jogador B compra n bilhetes
num único período. Assim, como generalização do item anterior, prove
que o jogador B é o que tem a maior chance de ganhar um prêmio
(2 < n < N)?
186. Escolhe-se, aleatoriamente, um elemento do conjunto {n G N|1 < n < 500}.
Qual a probabilidade de que este número não seja divisível por 2, nem por
3, nem por 5?
187. Uma caixa contém 2n bolas distintas, das quais a são vermelhas e b são
azuis, com a+b = 2n. Uma bola é retirada da caixa, ao acaso, e recolocada.
Em seguida, uma outra é retirada ao acaso. Calcule a probabilidade p de
que as duas bolas sejam da mesma cor. Mostre que tal probabilidade é
mínima para a = b = n. Sob tais condições, qual é o valor de p?
188. 6 dados de cores distintas são lançados simultaneamente. Calcule a pro
babilidade de que:
(a) todas as faces contenham valores diferentes;
(b) todas as faces contenham o mesmo valor;
(c) 3 faces contenham um mesmo valor, sendo os valores das outras 3
distintos deste e distintos entre si;
(d) 3 faces contenham um mesmo valor, duas outras contenham um outro
valor, e a restante contenha um valor distinto dos 2 anteriores.
189. 6 dados idênticos são lançados simultaneamente. Calcule a probabilidade
de que:
190. Consideremos uma urna contendo n bolas distintas, das quais ny > 1 são
brancas e ri2 > 1 são pretas, com n = rii + n.2. Toma-se, ao acaso, uma
amostra de r bolas, com r < e r < ri2- Qual a probabilidade de que
exatamente k das bolas selecionadas sejam brancas, se 0 < k < r.
193. Uma urna contém 6 bolas brancas, 6 bolas pretas e 6 bolas vermelhas.
Sacam-se 9 bolas desta urna, desconsiderando-se a ordem das bolas reti
radas.
(a) Supondo-se que bolas de mesma cor sejam indistinguíveis, qual a pro
babilidade de se extraírem 3 bolas de cada cor se não houver reposição?
(b) Supondo-se que bolas de mesma cor sejam indistinguíveis, qual a pro
babilidade de se extraírem 3 bolas de cada cor se houver reposição?
(c) Supondo-se que as 18 bolas sejam distintas entre si, assemelhando-se
somente em relação às cores, encontre as probabilidades, sem e com
reposição, de se extraírem 3 bolas de cada cor.
194. No jogo da SENA, são sorteadas 6 dezenas distintas dentre 01, 02, ...,
48. Um apostador escolhe 6 dessas 48 dezenas, sendo premiado se forem
sorteadas 4 (quadra), 5 (quina) ou 6 (sena) das dezenas por ele escolhidas.
195. No jogo da QUINA, são sorteadas 5 dezenas dentre 01, 02, ..., 80. Um
apostador escolhe 8 dezenas, sendo premiado se 3 (terno), 4 (quadra) ou
5 (quina) das dezenas sorteadas encontrarem-se entre as 8 originalmente
escolhidas. Determine a probabilidade de que um apostador faça:
(a) um terno;
(b) uma quadra;
(c) a quina.
196. Num estacionamento há 14 vagas em fila, das quais 10 estão ocupadas por
carros distintos e 4 estão desocupadas.
201. Suponha que um ano possua 365 dias para encontrar o menor valor de n
que satisfaz a seguinte afirmação: a probabilidade de que pelo menos uma
dentre n pessoas aniversarie hoje é maior do que
202. Um relé é um dispositivo magnético que controla a passagem da corrente
elétrica entre dois terminais: quando ele se fecha, passa corrente elétrica
entre os terminais; caso contrário, não há passagem de corrente. Na figura
abaixo, cada relé é representado por um número de 1 a 6:
1
A B
207. Um certo matemático14 sempre leva consigo duas caixas de fósforos, uma
em cada bolso. Toda vez que ele deseja fumar, toma um palito de uma das
duas caixas, a qual é escolhida aleatoriamente. Inicialmente, cada caixa
contém exatamente n palitos, os quais vão sendo, sucessivamente, consumi
dos. Como o matemático é distraído e fuma muito, há um momento em que
ele tira uma das caixas de um dos bolsos e percebe-a vazia. Neste momento,
qual a probabilidade de que a outra caixa contenha exatos k palitos?
209. Numa eleição dividida em 2 turnos, 5 candidatos (C*i, C2, C3, C4 e C5)
disputam a Prefeitura de uma cidade. Pesquisas realizadas por fontes con
fiáveis revelam que a probabilidade de Ci ganhar o primeiro turno da eleição
é igual à probabilidade de C2 ganhá-lo. A probabilidade de C3 ganhar é um
terço desta probabilidade, enquanto a probabilidade de C4 ganhar é igual
à de C5 ganhar, correspondendo ao dobro da probabilidade de C3 ganhar.
14Segundo Feller, W. ([5]), o matemático polonês H. Steinhaus, tendo convivido com o também
polonês S. Banach, elaborou uma versão parecida deste bem-humorado problema, aludindo aos
hábitos de fumante de Banach.
Parte II
Resoluções
Parte II. Resoluções - Combinatória básica 47
Combinatória básica
1. (a) Há duas opções: ir de A até C passando por B ou ir de A até C
diretamente. Passando por B, há 5 possíveis rotas de A a B e, para
cada uma destas, 3 possíveis rotas ligando B eC. Assim, pelo Princípio
Multiplicativo, existem 5 • 3 = 15 possíveis rotas. Diretamente, por
sua vez, há 2 possíveis caminhos ligando A e C. Então, pelo Princípio
Aditivo, temos 15 4- 2 = 17 rotas possíveis ligando A e C.
(b) Como existem 17 caminhos para ir de A até C, devem existir, também,
17 caminhos para ir de C até A, pois cada rota pode ser percorrida
em ambos os sentidos. Logo, pelo Princípio Multiplicativo, existem
17 ■ 17 = 289 rotas diferentes.
(c) Do total de 289 rotas de (b), apenas 4 não passam pela cidade B
nenhuma vez, pois há 2 opções para ir de A a C, sem passar por B, e
2 para voltai' de C até A, sem passar por B. Assim, há 289 — 4 = 285
rotas que passam por B, ao menos uma vez.
(d) Faremos uma análise caso a caso:
i. Rotas que vão de A a C e voltam a A, sem passar por B;
Neste caso, há duas possibilidades para ir de A a C e somente
uma para voltar de C até A, já que não se pode passar duas vezes
pela mesma estrada. Logo, há duas possíveis rotas.
ii. Rotas que vão de A a C, passando por B, e voltam a A, sem
passar por B;
Para ir de A até (7, são 15 possíveis rotas (item (a)) e, para voltar
a A, são 2 possibilidades. Há, então, 15 • 2 = 30 possíveis rotas
nessas condições.
iii. Rotas que vão de A a C, sem passar por B, e voltam a A passando
por B;
Caso simétrico ao anterior, tendo também 30 possibilidades como
resposta.
iv. Rotas que vão de A a C e voltam a A, passando por B na ida e
na volta.
Como já foi visto na resolução do item (a), existem 15 caminhos
ligando A e C. Para voltar a A passando por B, há duas possibi
lidades até B e 4 possibilidades de B até A (não podemos passar
pelas mesmas estradas utilizadas no caminho de ida até A). Assim,
há 2-4 = 8 possíveis rotas para voltar até A. Logo, são 15-8 = 120
as possíveis rotas.
48 Problemas Resolvidos de Combinatória
Pela análise dos itens i. a iv., dentre as rotas enumeradas em (b), temos
que 2+30+30+120 = 182 não passam duas vezes pela mesma estrada.
3. (a) Como a primeira e a última posições devem ser preenchidas com vo
gais, há 5 opções para cada uma delas. Para as posições centrais
(segunda e terceira), existem 23 opções para cada uma, já que se pode
preenchê-las com qualquer letra do alfabeto. Portanto, o número total
de anagramas é 5 • 23 • 23 • 5 = 52 • 232.
(b) A resolução deste item emprega raciocínio análogo ao do item anterior,
exceto que as posições centrais só permitem o uso de consoantes. Logo,
são 18 opções para a segunda posição e 18 para a terceira. Assim, o
número de anagramas passa a ser 52 ■ 182.
4. Para escolher uma maçã ou uma banana, Severino tem 16+13 = 29 opções.
Já para escolher uma maçã e uma banana, ele tem 16 opções de maçã e 13
de banana. Então, são 16 ■ 13 = 208 maneiras distintas de se realizar tal
escolha.
104 vezes em cada uma das 5 casas. De fato, fixando-se 5 em qualquer casa,
há 10 possíveis preenchimentos para as outras 4 casas. Logo, a resposta ao
problema será 5 • 104 = 50.000, como já sabíamos.
6. Para se compor uma coleção, pode-se tomar de 0 a n A’s, de 0 a n B's, de
0 a n C’s e de 0 a n D's. Logo, há n 4-1 opções para cada letra. Então,
pode-se formar (n 4- l)4 coleções distintas com as 4 letras dadas. Porém,
como se pedem apenas as coleções não vazias, deve-se retirar o caso em que
isso ocorre, isto é, o caso em que não se escolhe nenhuma letra. Assim, a
resposta é (n 4-1)4 — 1.
7. Pode-se visualizar tais produtos na forma 3a • 4b • 5C • 6d • 7e, com 0 < a, d < 1,
0 < 5, c<2e0<e<3. Assim, por exemplo, 3-5-6 seria o caso em que
a — c = d — 1 e ò = e = 0. Assim, temos 2 possibilidades para a e d (0
ou 1), 3 para b e c (0, 1 ou 2) e 4 para e (0, 1, 2 ou 3), donde o número
de possibilidades se torna 22 • 32 • 4 = 144. No entanto, este número inclui
o caso em que a = ò = c = d = e = 0, que não deve ser considerado, e os
seguintes casos também inconvenientes, por haver necessidade de se ter um
produto com pelo menos dois fatores:
10. (a) Observe o seguinte tabuleiro de xadrez, que exemplifica a notação que
será empregada nesta resolução:
(b) Para este item, abordaremos uma solução mais simples do que a do
item anterior. Sabemos que um retângulo é definido a partir do mo
mento em que se determinam seus quatro lados. As linhas do tabuleiro
m x n que contêm os quatro vértices podem ser escolhidas de (m^1)
maneiras, enquanto as colunas de m x n que os contêm podem ser es
colhidas de ("2!) maneiras. Uma vez escolhidas, observe que se define
um único retângulo. Assim, (:m+1)(n+1) = corresponde
à resposta procurada. Aplicando esta fórmula para m = n = 8, obte
mos, também, o valor 1.296, coincidindo com a resposta de (a).
1GDada uma Progressão Aritmética de n termos, sendo ai seu primeiro termo e an seu
n-ésinio termo, a soma de seus n termos iniciais Sn é obtida por meio da fórmula:
(qi + an)n
Sn =
2
Parte II. Resoluções - Combinatória básica 53
11. Maria pode ficar com quaisquer 3 dos 9 livros de Alberto, ou seja, ela tem
(3) = 84 opções. Analogamente, Alberto tem (3) = 35 opções. Assim, há
84 • 35 = 2.940 possíveis trocas de 3 livros entre Maria e Alberto.
15. (a) Dentre as 12 pessoas, devem ser escolhidas as 6 que receberão, cada
uma, um livro. Isso pode ser feito de (g2) = 924 maneiras. Agora,
pode-se arranjar os livros entre essas 6 pessoas, considerando que há
repetições, de 3TT = 60 maneiras. Então, há 924 • 60 = 55.440 possi
bilidades distintas de se fazer a distribuição.
(b) Além dos casos contados em (a), denotando-se os livros pelas letras A
(3 cópias), B (2 cópias) e C (1 cópia), temos os casos correspondentes
aos itens abaixo. Os hífens separam os livros que serão recebidos por
cada pessoa e observe que, além de selecionarmos dentre as 12 pessoas
aquelas que receberão um ou mais livros, temos ainda que permutar
as pessoas que vão receber os livros determinados em cada caso:
i. AB-A-A-B-C]
(?) ■ § = 47.520.
Exemplificando: nesse caso, uma pessoa recebe uma cópia do livro
A e outra do livro B, duas pessoas recebem uma cópia do livro
A cada uma, outra pessoa recebe uma cópia do livro B e outra
recebe uma cópia do livro C. Então, (g2) servirá para escolher as
cinco pessoas contempladas e || decidirá qual pessoa ficará com
cada bloco de livros (observe que há duas cópias de A repetidas).
ii. AC-A-A-B-B-,
(12) . 5! = 23.760.
iii. BC-A-A-A-B;
(?) ' 31 = 15.840.
iv. AB-AB-A-C-,
(\2) • || = 5.940.
v. AB-AC-A-B-,
(\2) • 4! = 11.880.
vi. AB-BC-A-A;
(12) • || = 5.940.
vii. AB-AB-AC;
(3) ’ S = 660-
viii. ABC-A-A-B-,
(4) • U = 5.940.
ix. ABC-AB-A.
ft2) -3! = 1.320.
Agora, somando-se os resultados encontrados nos itens i. a ix. ao do
item (a), obtemos 174.240 como resposta. Sem utilizarmos aquele
Parte II. Resoluções - Combinatória básica 55
(a) 0-4-5;
© ■ © ' (!) • 3! = 1.512.
Observe que, como o número de letras a em cada caixa é bem deter
minado, basta que contemos o número de escolhas possíveis entre as 9
letras restantes, que são distintas duas a duas. Ao final, multiplicamos
por 3!, considerando que A, B e C são caixas distintas.
(b) 0-3-6;
© ■ © ■ © ■ 3! = 504.
(c) 1-2-5;
©©•©•31 = 756.
(d) 1-3-5;
©■©•d)'3! = 3.024.
(e) 1-4-4;
© ■ © ' © ' 3 = 2.268.
(f) 2-2-5;
©•©.(!). 3 = 1.890.
(g) 2-3-4;
©•©©■31 = 7.560.
(h) 3-3-3.
© • © • © = 1-512.
Somando os valores encontrados nos itens anteriores, obtemos 19.026 possí
veis alocações das 18 letras nas caixas. Como uma dessas alocações é a
originalmente estabelecida, e estamos interessados apenas no número de
trocas possíveis da letras, temos 19.025 como resposta do problema.
19. A palavra tem 10 letras e, portanto, podemos imaginar 10 posições a serem
preenchidas por 5 consoantes (das quais duas são letras C repetidas), já que,
uma vez preenchidas, as posições das vogais ficam determinadas. Logo,
são (g0) = 252 possibilidades de escolha dos espaços para as consoantes.
Em seguida, devemos permutar tais letras, com repetição, o que nos dá
252 • |j = 15.120 possibilidades.
20. Devemos primeiramente selecionar 2 livros dentre 10. Em seguida, 2 livros
dentre os 8 restantes e, assim, sucessivamente. Ainda, como as parcelas
de dois livros são indistintas (as caixas são idênticas), devemos dividir o
resultado final pela permutação do número de parcelas existentes, obtendo
um total de disposições possíveis igual a:
(© ■ © • © ■ © • © = 945
Parte II. Resoluções - Combinatória básica 57
22. (a) Não podemos escolher quatro letras distintas, visto que só se dispõe
de três letras distintas (P, O e R). Logo, temos os seguintes casos:
i. duas letras iguais e duas outras distintas entre si;
Temos apenas que escolher as duas letras iguais, pois, como só há
três letras distintas, as outras duas já estarão determinadas. São,
portanto, 3 opções.
ii. duas letras iguais e outras duas iguais entre si.
Podemos imaginar que vamos deixar de escolher exatamente um
tipo de letra, obtendo, desse modo, 3 opções também.
Assim, são 6 as seleções possíveis de se fazerem.
(b) Cada um dos casos do item i. de (a) nos fornece 12 permutações e cada
um dos casos do item ii. de (a) nos fornece 6. Logo, temos um total
de 3 • 12 + 3 • 6 = 54 permutações possíveis.
23. (a) Trata-se de uma palavra de 11 letras, das quais 5 são vogais e 6 são
consoantes. Para que seja possível obter a configuração proposta no
enunciado da questão, devemos invariavelmente preencher a primeira
posição com uma consoante. Sendo assim, os espaços a serem ocupa
dos por vogais ou consoantes já ficam determinados, bastando que per-
mutemos vogais e consoantes em Suas posições, aplicando, em seguida,
o Princípio Fundamental da Contagem: ? = 900 (lembre-se
de que há repetições). Portanto, 900 são as maneiras possíveis de se
realizarem as permutações propostas.
(b) Vamos dividir o problema em casos para calcular, antes, o número de
seleções de quatro letras que podem ser feitas:
i. quatro letras distintas entre si;
Dispomos de duas letras l, duas letras i, duas letras ò, duas letras
58 Problemas Resolvidos de Combinatória
27. (a) Procederemos primeiro com a justificativa de que cada soma só pode
ocorrer de uma única maneira. Note que os números das faces formam
uma seqüência crescente de números, na qual cada elemento é uma
unidade maior do que o dobro do elemento anterior. Com isso, é
possível concluir que cada soma é única. Quanto ao número de somas
possíveis no lançamento dos dois dados, uma vez sabendo que cada
60 Problemas Resolvidos de Combinatória
© W © (4!p
12! 12!
©■«.■©
12!
' (4!)3 “
© © ©©
(12!)4
“ (4!)12 ‘
(12!)4 12! 9! 6!
“ (4!)12 •1
9! ■ 3! ’ 6! • 3! ‘ 3! ■ 3!
(12!) 5
= (4!)12 ■ (3!)4
0©©C”)-0 0-
5! 18! • 14! • 10! • 6! • 3!
“ 3! ■ 2! ' 14! • 4! • 10! • 4! • 6! • 4! • 3! • 3! - 0! • 3!
10 • 18!
= 128.648.520.000.
- (4!)3 • (3!)2
34. (a) Os números menores do que um milhão são aqueles que contêm um
número de dígitos menor do que ou igual a seis. Com seis dígitos,
temos duas opções para o preenchimento de cada casa decimal (8 ou
9). Logo, são 26 números posíveis de serem formados. Com cinco
dígitos, conseqüentemente, são 25 opções. Prosseguindo o raciocínio,
temos 26 + 25 + 24 + 23 + 22 + 2 = = 126 números possíveis18.
(b) Agora, utilizando os dígitos 7, 8 e 9, podemos simplesmente repetir o
raciocínio do item (a) lembrando que, para cada casa a ser preenchida,
temos agora uma opção a mais (o algarismo 7). Desta forma, temos
36 + 35 + 34 + 33 + 32 + 3 = 1.092 números possíveis de serem formados
neste caso.
(c) Aqui, o fato de podermos preencher casas com o dígito 0 apresenta um
complicador ao nosso problema. De fato, para um número de 6 dígitos,
por exemplo, não podemos preencher sua primeira casa com 0, pois isto
nos daria um número de 5 dígitos. Logo, nesse caso, teremos apenas
duas opções para a primeira casa (8 e 9), sendo que para as 5 casas
restantes há 3 opções, pois nelas o dígito 0 pode ser empregado. Assim,
são 2 • 35 os números de 6 dígitos possíveis. Repetindo o raciocínio
para números de 5 dígitos, temos 2 ■ 34 números possíveis. Logo, são
2 -354-2 -34+ 2-33+ 2-32+ 2- 34-2 = 728 os números menores do que
um milhão e que contêm apenas os dígitos 0, 8 e 9 em sua composição.
35. Vamos considerar os números de 6 dígitos ou menos. Quanto aos que têm
6 dígitos, temos 9 opções para preencher sua primeira casa (não se pode
utilizar 0), 9 para a segunda (não se pode usar o dígito utilizado na casa
18Lembre-se de que, dada uma Progressão Geométrica de primeiro termo ai e razão q, a soma
Sn de seus n primeiros termos é igual a:
ai(gn - 1)
Sn =
4-1
64 Problemas Resolvidos de Combinatória
Fpl |T| I TI
B c c E E|
F A A |Q
C A A F|
IF A A C
C A A F|
|E C C B
E F F PJ
39. (a) Sabemos que, ao se dividir um número inteiro por 3, o resto da divisão
é igual a 0, 1 ou 2. Assim, cada um dos números envolvidos no proble
ma assume uma das 3 formas: 3Â;, 3k 4- 1 ou 3fc 4- 2. Ademais, é
conveniente observar que, de 1 a 100, temos 33 números da primeira
forma, 34 números da segunda forma e 33 números da terceira forma.
Logo, temos as seguintes possibilidades de obter soma múltipla de 3:
i. tomar 3 números da forma 3k;
Nesse caso, temos (333) = 5.456 escolhas possíveis.
ii. tomar 3 números da forma 3k + 1;
Agora, são (334) = 5.984 as opções.
iii. tomar 3 números da forma 3k 4- 2;
Analogamente, as opções ocorrem em número de (333) = 5.456.
iv. tomar um número de cada uma das 3 formas.
Agora, são 33 • 34 • 33 = 37.026 as opções de escolha.
Portanto, somando os resultados obtidos, temos um total de 53.922
seleções possíveis.
(b) De certa maneira, este item é mais simples do que o anterior, uma vez
que, dentre 3n números naturais consecutivos, sempre há n elementos
da forma 3k, n da forma 3k 4- 1 e n da forma 3k 4- 2. Analogamente,
os casos em que temos de dividir o problema são os mesmos do item
(a), exceto que aqui estamos trabalhando com valores incógnitos:
i. tomar 3 números da forma 3k;
Nesse caso, temos (3) escolhas possíveis.
68 Problemas Resolvidos de Combinatória
40. De cada uma das m parcelas, temos que selecionar n objetos. Pelo Princípio
Fundamental da Contagem temos, pois:
írq + r\ / (r — l)q 4- (r — 1) ? +1
U+1A Ç+1 <7+1
(rq + r)!_______________ ((r - l)q + (r - 1))!
(q 4- 1)! • ((r - l)q + (r - 1))! (q 4- 1)! • ((r - 2)q 4- (r - 2))!
(q + 1)! (rq + r)!
‘ (q + 1)! • 0! “ ((q + l)!)r ’
CHICM)*•(";') n—1
2
n! n! (n- 1)!
=> 5
41-(n —4)1 = 2! • (n - 2)! + n 2! ■ (n —3)1
5n(n — l)(n — 2)(n — 3) n(n — 1) ( n(n — l)(n — 2)
24 “ 2 +
+ 2
5(n-2)(n-3) , .
-------- J2-------- -l + (n-2)
=> 5(n2 - 5n + 6) = 12(n - 1)
=> 5n2 — 37n + 42 = 0,
43. (a) Para maior praticidade, vamos dividir o problema em três casos:
i. nenhum coelho preto se entoca;
Temos que contar os casos em que só há coelhos brancos nas tocas.
Podemos variar o número de coelhos brancos que estão entocados
de 0 a 7 e, como as tocas são consideradas distintas, basta que
escolhamos as tocas que serão ocupadas pelos coelhos brancos.
Assim:
(M)— 29
© - ©=512-9-1=502
é o número de maneiras de se entocarem os coelhos neste caso. (
Só como exemplo, (9) conta o número de configurações em que
exatamente 3 coelhos brancos estão entocados, isto é, escolhe as 3
tocas a serem por eles ocupadas.
ii. exatamente um coelho preto se entoca;
Agora, são sempre 9 as possibilidades de alocar o coelho preto.
Parte II. Resoluções - Combinatória básica 71
•©’•©
maneiras diferentes.
9 28 = 9-255 = 2.295
9-8
km:)—©]-
possibilidades.
9 ■ 8 • 27 = 72 • 128 = 9.216
casos.
ii. há um coelho preto entocado.
Observando atentamente a resolução dos itens anteriores, fica fácil
intuir que temos, neste caso:
<•*'>© + (n + 1) Q (n + l)2n
possibilidades.
Assim, considerando a subdivisão em casos realizada, temos um total
de 2n+1 — l + (n+l)2n = (n+l+2)2n — 1 = (n+3)2n —1 possibilidades.
44. Facilitaremos muito nosso problema se o dividirmos em casos:
(a) paralelepípedos com três arestas distintas;
Fixemos nosso olhar sobre uma das seis faces do paralelepípedo, esco
lhendo-a como base. Uma vez feito isso, temos 10 opções de tamanho
para um dos lados dessa face (qualquer natural entre 1 e 10), 9 opções
para o outro lado (já que as arestas do sólido devem ter tamanhos
distintos) e 8 opções para a altura do sólido. Portanto, 10 • 9 • 8 = 720
é o número de sólidos possíveis. Observe, no entanto, que estamos
contando 6 vezes cada um dos sólidos com 3 arestas distintas. A ilus
tração que vem a seguir exemplifica 6 sólidos idênticos que, dentre os
720, estariam sendo considerados distintos:
3
2
1
—
2
V
3
4
45. (a) Primeiramente, temos que escolher os 6 CDs que ocuparão a bandeja
do aparelho. Como dispomos de 80 CDs diferentes, são (86°) as pos
sibilidades para isso. Uma vez tendo escolhido os CDs, precisamos
escolher em qual espaço cada um deles vai ficar. Como os espaços são
todos numerados, são 6! as maneiras de se permutarem os 6 CDs nos
mesmos. Portanto, (86°) • 6! = - 6! = fgf = 216.360.144.000 é a
resposta ao nosso problema. De fato, poderiamos tê-lo resolvido sim
plesmente escolhendo qual CD ficaria na posição 1 (80 opções), qual
ficaria na posição 2 (79 opções) e, assim, sucessivamente, obtendo um
total de 80 • 79 • 78 • 77 • 76 • 75 maneiras, que corresponde ao mesmo
valor calculado anteriormente.
(b) A resolução que empregamos no item anterior agora se fará assaz útil
à que empregaremos neste. Assim como naquele item, escolhemos os
6 CDs que ocuparão a bandeja e, em seguida, precisamos dispô-los na
mesma. Devido ao fato de os espaços destinados aos CDs serem indis
tinguíveis, teremos que utilizar o conceito de permutações circulares,
que já fora empregado num exercício precedente. Isto porque rotações
da bandeja em torno do seu centro conduzem a configurações idênticas
dos CDs. Assim, podemos permutar de (6 — 1)! = 5! maneiras os CDs
escolhidos. Logo, o número de maneiras de se escolherem e colocarem
6 CDs na bandeja é igual a (86°) • 5! = 36.060.024.000.
46. Primeiro, vamos calcular o total de números em que não figuram 2 dígitos
iguais consecutivos. Para a primeira posição, temos 9 opções de preenchi
mento (não podemos fazê-lo com 0), para a segunda, são também 9 as
opções (só não podemos utilizar o dígito anterior). Assim, sucessivamente,
obtemos 96 números. Ademais, não é difícil ver que o total de números com
6 algarismos é igual a 9 ■ 105. Portanto, 9 ■ 105 — 96 = 368.559 é a resposta
procurada.
47. Sendo importante quais números ocuparão cada linha, precisamos distribuir
os 20 números em quatro grupos de 5 números cada, desprezando a ordem
em que as linhas aparecem. Isso equivale ao problema de distribuir 20 obje
tos entre 4 caixas idênticas de tal modo que cada uma fique com exatamente
74 Problemas Resolvidos de Combinatória
50. (a) É importante observar que pode haver várias maneiras de se argumen
tar em exercícios como este, de forma que a demonstração que aqui
faremos é apenas uma delas. Suponhamos que se tenha um conjunto
com n elementos distintos dos quais desejamos selecionar k. Suponha
mos, ainda, que, em tal seleção, importe somente qual é o primeiro
elemento selecionado. Assim, tendo escolhido os k elementos de (£)
maneiras, temos k possibilidades para o primeiro elemento escolhido,
justamente o que exprime o primeiro membro da identidade. Por outro
lado, podemos fazer esta mesma seleção da seguinte maneira: escolhe
mos o primeiro elemento dentre os n existentes e, em seguida, es
colhemos os outros k — 1 elementos dentre os n — 1 restantes, que é
justamente o que ‘conta’ o segundo membro da igualdade acima.
(b) Observe que, sem = 1, recaímos na fórmula do item (a). Então, de
certa maneira, este item é uma generalização daquele, de tal modo
que poderiamos repetir o raciocínio lá empregado. Entretanto, a fim
76 Problemas Resolvidos de Combinatória
2n 4- 4 2n 2n .(2n\ Â í 2n \ ( 2n \
4-4 +6 +4 4- ,
n 4- 2 n 4- 2 n 4-1 \ nJ \n—Xj \n — 2)
52. (a) Temos (12) opções de escolha para as 7 pessoas que ocuparão uma das
mesas, ficando as pessoas da outra mesa já determinadas. Em seguida,
devemos utilizar permutações circulares para acomodar as pessoas nas
mesas. Logo, são (12) • (7 — 1)!• (5 — 1)! = 13.685.760 as possibilidades.
(b) Agora, temos também (12) opções de escolha para as 7 pessoas que
ocuparão a mesa redonda, ficando as outras 5 já determinadas. Uti
lizando, então, permutações circulares na mesa e permutações simples
no banco, temos (72) ■ (7 — 1)! • 5! = 68.428.800 maneiras de acomodar
as pessoas.
55. (a) A engenhosidade da resolução que proporemos reside num simples as
pecto de visualização do retângulo quadriculado da figura exibida no
enunciado da questão. Imaginemos que ele seja um tabuleiro de xadrez
Parte II. Resoluções - Combinatória básica 79
(b) Cálculo de i.
Parte II. Resoluções - Combinatória básica 81
57. (a) Como as repetições são permitidas, temos 6 opções de letras para ocu
par cada uma das cinco posições da seqüência. Logo, são 65 = 7.776
seqüências possíveis.
(b) Agora, como não se permitem repetições, temos 6 opções de preenchi
mento para a primeira posição, 5 para a segunda (não podemos utilizar
a letra que preencheu a primeira posição), e assim por diante, obtendo
6 ■ 5 • 4 • 3 • 2 = 720 possíveis seqüências.
(c) Podemos escolher uma das 5 posições para ser ocupada pela letra C e,
em seguida, preencher as demais a partir das letras restantes. Temos,
então, 5 • 5 • 4 • 3 • 2 = 600 possíveis seqüências.
(d) Este item não pode ser resolvido como o item (c), pois se assim fizermos
estaremos contando casos repetidos (isso ocorre porque as repetições
de letras são permitidas). Podemos contar o número de seqüências
que não contêm a letra C e, em seguida, subtrair esse valor do total
encontrado em (a). O número de seqüências que não contêm C é igual
a 55 e, portanto, 7.776 — 55 = 4.651 é o total de seqüências procurado.
58. (a) Como todos os carros são distintos, temos 20! maneiras de colocar os
carros no estacionamento. Se considerarmos indistinguíveis os carros
de mesma cor, podemos utilizar permutações com repetições para obter
um total de = 99.768.240 disposições diferentes.
(b) Uma vez determinados os grupos de vagas para cada cor de carros,
basta permutarmos os carros de cada cor em seu grupo, obtendo um
total de 7! -5! -8! = 24.385.536.000 configurações diferentes. Para o caso
de só haver necessidade de que carros de mesma cor fiquem juntos, só
precisamos multiplicar o valor encontrado anteriormente por 3!. Logo,
3! • 7! • 5! • 8! = 146.313.216.000 é o número procurado.
82 Problemas Resolvidos de Combinatória
59. (a) Basta que permutemos as 10 pedras nos espaços a elas destinados para
descobrir o número de maneiras. Como são 10 as pedras distintas,
temos 10! = 3.628.800 maneiras de cravejar as pedras na moldura do
quadro.
(b) Agora, o fato de rotacionarmos o espelho em torno de seu centro con
duz a configurações equivalentes, o que sugere o uso de permutações
circulares (observe que isso não vale para o item anterior, pois um
quadro, mesmo que circular, tem uma posição preestabelecida). As
sim, são (10 — 1)! = 9! = 362.880 cravejamentos possíveis.
(c) Como já explicamos no Exercício 12, além de aplicarmos permutações
circulares para montar o colar, devemos dividir o resultado final por 2,
dado que colares idênticos podem ser obtidos ao rotacionarmos cada
um deles em torno de um eixo diametral. Logo, são = 181.440
colares possíveis.
60. (a) Uma interpretação para a identidade é a de que, dada uma coleção de
n objetos distintos, o número de maneiras de selecionarmos k objetos é
igual ao número de maneiras de selecionarmos n — k objetos. Mas isto
é evidente, uma vez que, para cada escolha de k objetos, deixamos de
selecionar n — k. Em outras palavras, podemos tanto contar os grupos
de objetos escolhidos como contar os grupos de objetos não escolhidos.
(b) O primeiro membro da igualdade conta o número de seleções de k
objetos dentre n distintos. Podemos fazer essa mesma conta, porém,
fixando um dado elemento dentre os n existentes, e dividindo as sele
ções em dois grupos: o daquelas em que o dado elemento não é sele
cionado (consideradas em pois basta que escolhamos k elemen
tos dentre os n— 1 restantes) e o daquelas em que o dado elemento é se
lecionado (como já temos um elemento selecionado, basta que escolha
mos k — 1 dentre os n — 1 restantes). Assim, concluímos que vale
a identidade do enunciado, pois ambos os seus membros ‘contam’ o
mesmo tipo de seleções.
61. Suponhamos que existam dois conjuntos, denotados por A e B, tais que
|A| = |B| = n e, além disso, que os 2n elementos de A U B sejam distintos
entre si. Assim, considerando a seleção de n elementos quaisquer, é claro
que dispomos de (2^) opções de escolha. Por outro lado, podemos efetuar a
mesma escolha, tomando a elementos de A e b elementos de B de tal modo
que a 4- b = n, ou seja, b = n — a. Nesse caso, temos (”) (n2a) escolhas
possíveis para cada valor de a. Note, porém, que, para contarmos todas
as seleções consideradas por (2”), é preciso que variemos a de 0 a n (com
Parte II. Resoluções - Combinatória básica 83
Ê(X:.HXMX:.)
chegando ao resultado a que aspirávamos. Uma vez provada essa identidade,
note finalmente que, como, para cada a, temos (”) = (n”a) (Exercício 60),
segue que:
2
CX(XC)
62. (a) Note que:
f Pn \ = (pn)!
\pn — n) nl(pn — n)!
pn(pn — 1)!
n(n — l)!(pn — n)l
(pn - 1)1
= P (n — l)!(pn — n)!
número que sabemos ser inteiro, donde nossa demonstração está con
cluída.
(X)G)©-»»
Parte II. Resoluções - Combinatória básica 85
33 -479.001.600.
(2°+21+22)(3o+31+32+33+34)(5°+51+52+53)(7<)+71) = 1.057.056.
69. (a) Podemos considerai1 cada casal como um bloco único, uma vez que
marido e mulher não podem se sentar separadamente. Assim, dispo
mos de 6 blocos que podem ser permutados. Além disso, as ordens
marido-mulher e mulher-marido dentro de cada bloco devem ser leva
das em conta. Assim, o número de maneiras de se disporem os casais
nas cadeiras é igual a 6! • 26 = 720 • 64 = 46.080.
88 Problemas Resolvidos de Combinatória
(b) Novamente, podemos considerar blocos formados por cada casal. As
sim, teremos 11 posições a serem ocupadas por 6 casais. Ademais,
importa também a ordem em que se encontram marido e mulher den
tro de cada bloco. Portanto, são (11 • 10 • 9 • 8 • 7 • 6) ■ 26 = 21.288.960
as configurações possíveis.
Uma outra maneira de resolver o exercício seria pensar que dispomos
de 11 objetos, sendo 6 casais e 5 cadeiras idênticas. Assim, utilizando o
conceito de permutações com repetições, teremos • 26 = 21.288.960
disposições diferentes, como já havíamos calculado.
70. (a) Temos 3 casos a considerar:
i. cada país é colorido de uma cor distinta;
São m(rn — l)(m — 2)(m — 3)(m — 4) maneiras distintas.
ii. a cor usada para colorir a Alemanha é igual à usada para colorir
a Eslováquia, e as cores da Polônia e da Áustria são distintas, ou
vice-versa;
Temos m opções de cor para a Rep. Tcheca, m — 1 opções para
colorir os dois países opostos de mesma cor, e (m — 2)(m — 3)
opções para colorir os dois países opostos de cores distintas. Logo,
considerando as duas possibilidades, há 2m(m — l)(m. — 2)(m — 3)
maneiras distintas.
iii. a cor usada para colorir a Alemanha é igual à usada para a Eslová
quia, e a usada para colorir a Polônia é igual à usada para a
Áustria.
Temos m opções para colorir a Rep. Tcheca, m — 1 opções para
colorir um dos pares de países opostos e m — 2 para colorir o
outro par de países opostos. Logo, são — !}{rn — 2) maneiras
distintas.
Somando os resultados obtidos, chegamos a um total de:
m(m — l)(m — 2)(m — 3)(m — 4) 4- 2m(m — — 2}(m — 3)4-
m(m — — 2) =
= m(m — l)(m — 2)[(m — 3)(m — 4) + 2(m — 3) 4-1]
= m(m — l)(m — 2)(m2 — 5m 4- 7)
maneiras diferentes de colorir o mapa.
(b) Como vimos no item iii. de (a), são necessárias pelo menos 3 cores
para colorir o mapa. Ainda pela resolução lá empregada, temos um
total de 3(3 — 1)(3 — 2) = 6 maneiras distintas de colorir o mapa nesse
caso.
Parte II. Resoluções - Combinatória básica 89
z=o x 7
donde o coeficiente de xm em (1 4- x)n é (£). Por outro lado, temos
também que:
’n-p p
(l + xr-p(l+:r)p
e>] ■
Para encontrarmos o coeficiente de xm na expansão acima, devemos
estabelecer a condição i 4- j = m em relação ao seu segundo membro.
Assim, o termo que multiplica é igual a:
n—p
m ,
m
fc=0 x
m — kj \fc/
como queríamos.
72. (a) Para resolvermos este problema, torna-se muito útil uma divisão em
casos:
i. planos que não contêm nenhum ponto de Pi;
Neste item se mostra a importância da observação do enunciado
de que, se 4 pontos de P são coplanares, então eles são pontos de
90 Problemas Resolvidos de Combinatória
74. (a) Como nas seleções não importa a ordem dos números, podemos iniciá-
las pelo número menor. Assim, tomando qualquer número compreen
dido entre 1 e 91, existe um único número entre 1 e 100 que possui
nove unidades além dele. Assim, o número de seleções é igual a 91.
(b) De acordo com o item anterior, há 91 pares de números compreendi
dos entre 1 e 100 cuja diferença é exatamente 9. Prosseguindo com o
raciocínio, há 92 pares cuja diferença é exatamente 8. Assim, sucessi
vamente, até 99 pares cuja diferença é exatamente 1. Logo, a resposta
ao problema é 91 + 92 + • • • + 99 = 855.
Procedendo de outra maneira, podemos notar que, para cada número
compreendido entre 1 e 91, existem 9 números entre 1 e 100 que pos
suem de uma a 9 unidades além do número inicial. Daí por diante,
temos: 92 apresenta apenas 8 números maiores do que ele nas mes
mas condições; 93 apresenta apenas 7 números maiores do que ele
nas condições do enunciado. Seguindo com este raciocínio, o número
possível de seleções é igual a91-9 + 8 + 7-|------- F 1 = 855, coincidindo
com o resultado anterior.
(a) 4-1-1-1;
Temos (43) opções de escolha para as cartas do primeiro naipe e 13
92 Problemas Resolvidos de Combinatória
76. Vamos distribuir uma fruta por vez. Com relação às maçãs, estamos in
teressados em saber o número de soluções inteiras positivas da equação
xi + X2 + X3 + X4 = 10. Assim, há = (3) = 84 distribuições
possíveis, pelo Exercício 25. Analogamente, há (Jz}) = (3) = 20 dis
tribuições possíveis para as laranjas e (4Zj) = (3) = 56 para as pêras.
Logo, temos 84 • 20 • 56 = 94.080 distribuições possíveis das frutas nas qua
tro caixas.
77. (a) Note que, para obtermos um desarranjo de RADAR, a letra D não
pode ocupar a posição central. Além disso, ocupando a letra D qual
quer uma das outras 4 posições, a palavra está determinada. Por
exemplo, se a letra D ocupar a primeira posição, então os 2 A’s devem
ficar nas posições terceira e quinta, restando as outras duas posições
para os R’s. Assim, são 4 os desarranjos possíveis.
(b) Na palavra AGRAVAM, temos 3 A’s e outras 4 consoantes distintas.
Para obtermos um desarranjo de AGRAVAM, as posições de 3 das 4
consoantes devem ser ocupadas por A’s. Por conseguinte, a posição
de uma das consoantes deve ser ocupada por outra consoante (distinta
dela, obviamente). Assim, temos 4 opções de escolha para a consoante
cuja posição será ocupada por outra consoante, e 3 opções de escolha
para a letra que ocupará tal posição. Feito isso, já determinamos as
posições dos 3 A’s e de uma das consoantes. Quanto às outras 3,
podemos permutá-las nas posições anteriormente ocupadas por A’s de
Parte II. Resoluções - Combinatória básica 93
79. Como BC mede 2 metros e cada degrau mede 25 centímetros, é claro que
a escada deve ter 8 degraus. Como o primeiro degrau começa em A e o
último termina em C, basta que decidamos os pontos em que começarão os
outros 7 degraus. Como estes devem ter largura múltipla de 40 centímetros,
podemos dividir o segmento AB em = 15 segmentos de 40 centímetros
cada um. Determinamos, então, 14 pontos no segmento AB (observe que
não contamos os pontos A e B, pois já sabemos que o primeiro degrau
deve começar em A e que o último não deve começar em C). Como temos
que construir mais 7 degraus, basta que selecionemos 7 desses 14 pontos,
determinando os tamanhos de cada degrau da escada e, por conseguinte, a
própria escada. Assim, a resposta é igual a (*? ) = 3.432 possíveis escadas.
00000000.
82. Fixando um dos cavaleiros da Távola Redonda, digamos, Sir Lancelot, pode
mos reduzir nosso problema a outros em que os cavaleiros em questão podem
ser vistos como se estivessem em fila. Temos dois casos a considerar:
(a) seleções que contêm Sir Lancelot;
Os dois vizinhos imediatos de Sir Lancelot são-lhe considerados ini
migos. Logo, para efetuarmos uma escolha compatível de cavaleiros,
devemos selecionar 4 dentre os 9 restantes com a restrição de que não
Parte II. Resoluções - Combinatória básica 95
83. Denotemos por c as pessoas que dispõem de 5 reais e por d as que dispõem de
10 reais. Sem = 2efc = 3, então somente as filas cdccd, cdcdc, ccdcd, ccddc
e cccdd são “boas”, sendo as 5 filas restantes consideradas “ruins” (a saber,
as filas ddccc, dcdcc, dccdc, dcccd e cddcc). Observe, então, que as filas
“boas” devem começar por c e, além disso, para cada ponto das mesmas,
o número de c’s já atendidos pelo caixa deve ser maior do que ou igual
ao número de d’s já atendidos. Em outras palavras, se considerarmos as
seqüências de m d's e k c’s até determinada posição, devemos ter um número
96 Problemas Resolvidos de Combinatória
ccdcdcddcdd ccdccd
dddcdcdccdcc ccdccd
84. (a) A primeira criança pode ficar com um número de rosas variando de
0 a 12 (13 opções), um número de margaridas variando de 0 a 13 (14
opções) e um número de lírios variando de 0 a 10 (11 opções). Logo,
as crianças podem dividir as flores de 13 • 14 • 11 = 2.002 maneiras dis
tintas. Observe que, distribuindo-se as flores para a primeira criança,
o número de flores da segunda fica automaticamente determinado.
Agora, impondo a condição de que cada criança fique com ao menos
três flores de cada tipo, temos 7 opções de distribuição para as rosas
(a primeira criança pode receber de 3 a 9 rosas), 8 opções para as mar
garidas e 5 opções para os lírios. Assim, temos 7 • 8 • 5 = 280 opções
de distribuição nesse caso.
(b) Basta que generalizemos o raciocínio empregado no item anterior. Sem
restrições sobre as quantias de flores, temos (ni 4-1) (n? +1) • • • (n* 4-1)
distribuições possíveis. Com as restrições impostas sobre as quantias
de cada flor, temos (ni — 2si 4- l)(n2 — 2s2 4- 1) • • • (n* — 2sfc 4- 1)
distribuições. De fato, tomemos como exemplo a distribuição das flores
do tipo 1. Como cada criança deve receber pelo menos $i flores desse
tipo, a primeira criança deverá receber um número de flores variando
de si a m — $i. Logo, temos n\ — si — (sj — 1) = ni — 2si 4-1 opções
de distribuição para este tipo de flor. O mesmo raciocínio se aplica à
distribuição dos demais tipos de flores, validando a nossa fórmula.
85. Inicialmente, devemos decidir quantas bandeiras serão colocadas em cada
mastro, considerando-as, num primeiro momento, idênticas. Em seguida,
basta multiplicar o resultado encontrado por nl, arranjando as bandeiras nos
mastros. O número de maneiras de se determinar a quantidade de bandeiras
por mastro corresponde ao número de soluções inteiras não negativas da
equação xi 4------ FZfc = n (já que podemos ter mastros vazios), que sabemos
corresponder a (. n+fc-l . ’ Pe^° Exercício 25. Logo, a resposta ao problema é
k-1 1)
n^7
A (n+fc-1)!
) ~ (fc-l)l '
86. (a) Podemos proceder selecionando 2 pessoas dentre as 10 para ocuparem
o primeiro degrau, 2 dentre as 8 restantes para ocuparem o segundo,
98 Problemas Resolvidos de Combinatória
25(2°)©G)(2)G)= 3-628'800
maneiras distintas.
(b) Neste caso, podemos permutar os rapazes, um em cada degrau, de
5! maneiras, o mesmo valendo para a permutação das moças. Além
disso, devemos também considerar a ordem dos casais em cada degrau,
obtendo um total de 5! ■ 5! • 25 = 460.800 maneiras distintas.
87. (a) Basta que escolhamos quais vão ser as quatro pessoas que receberão,
cada uma, um prêmio, escolhendo qual prêmio cada uma ganhará em
seguida. Desse modo, (J) • 4! = 840 é a resposta desejada.
(b) Agora, basta que decidamos a quem cada prêmio será destinado. As
sim, cada um dos quatro prêmios pode agraciar qualquer uma das sete
pessoas, donde são 74 = 2.401 as possíveis premiações.
(c) Temos 7 opções de escolha da pessoa que receberá o primeiro prêmio.
Uma vez escolhida, dâmo-la o prêmio, e obtemos um problema análogo
ao do item anterior: distribuir 3 prêmios dentre 6 pessoas, cada uma
podendo receber qualquer número de prêmios. Temos, desse modo,
7 • 63 = 1.512 possíveis premiações.
88. Dentre os m objetos iguais entre si, temos m+1 possíveis escolhas (podemos
tomar de 0 a m objetos). Analogamente, temos n + 1 opções de escolha para
os outros n objetos iguais entre si. Com relação a cada um dos p objetos
diferentes, temos duas opções para cada um deles: escolhê-lo, ou não o
escolher. Assim, temos 2P possíveis escolhas para tais objetos. Portanto,
lembrando de retirar o caso em que nenhum objeto é escolhido, obtemos
2p(m + l)(n + 1) — 1 coleções.
89. Primeiramente, observemos que todas as vezes que formamos a palavra
COMBINATÓRIA, finalizamos no A situado no canto inferior direito do
quadro exibido no enunciado. Assim, podemos analisar as construções de
maneira inversa, partindo desse A e voltando ao C inicial. Note, então, que,
antes desse A, pode ter vindo o I situado acima dele ou o I situado ao seu
lado esquerdo. Estando num dos I’s, notamos que também há duas possi
bilidades para a letra R que o precedeu. Prosseguindo com este raciocínio,
como a palavra em questão possui 12 letras, tivemos 11 passos para voltar
do seu A final até o seu C inicial, donde se têm 211 = 2.048 possíveis
maneireis de se formar a palavra COMBINATÓRIA.
Parte II. Resoluções - Combinatória básica 99
90. Para resolvermos este problema, devemos notar que o número de 0’s em que
873! termina é igual ao número máximo p de fatores 10 que podem ocorrer
na decomposição 873! = N • 10**. Além disso, como IO? = 2P • 5**, e o número
de fatores 2 é maior do que o número de fatores 5 na decomposição de 873!
em números primos, temos que p é igual ao expoente de 5 na decomposição
em fatores primos do número em questão. Observe, então, que:
5 10 870
873! = 1 • • • 4 • (5*^7)-6 • • • 9 • (5*^2)-11 • • • 869 - (5 • 174)-871 • ■ • 873
Assim, 873! = ABCD • 5215, sendo que em ABC D não existem fatores 5,
pela construção que fizemos. Logo, pelo esquema de resolução anterior
mente sugerido, vem que p = 215, isto é, 873! termina em 215 0’s.
91. (a) Observe que, dadas as restrições do problema, os números que devemos
contar devem possuir 3, 5, 7 ou 9 algarismos. Só há um número
com 3 algarismos que contemple as condições impostas: 306. Com 5
algarismos, temos números da forma 3_0_6. Logo, temos 7 opções
para a segunda posição e 6 para a quarta, donde são 7 • 6 = 42 os
números nesse caso. Prosseguindo, temos 7 • 6 ■ 5 ■ 4 = 840 números
com 7 algarismos, e7-6-5-4-3-2 = 7! = 5.040 números com
100 Problemas Resolvidos de Combinatória
(n2)! = l2 • 2 • 3 • 22 • 5 • • • (n2 — 1) • n2
= (l2 • 22 • • • n2)[2 ■ 3 • 5 • • • (n2 — 1)]
= (1 • 2 • • • n)2[2 • 3 • 5 • • • (n2 — 1)]
= (n!)2[2 • 3 ■ 5 ■ • • (n2 — 1)].
Logo, segue do desenvolvimento acima que, para n > 3 (na verdade, para
n = 2 também), (n2)! > (n!)2.
Por outro lado, temos que:
(n!)2 = [1 • 2 • • • (n — 1) • n] [n • (n — 1) • • • 2 • 1]
= (1 • n) • [2 • (n - 1)] ■ • - [(n - 1) • 2] • (n • 1).
Agora, note que cada termo do produto acima é da forma (i + l)(n — i),
com i variando entre 0 e n — 1. Para i = 0 ou i = n - 1, tem-se claramente
que (t + l)(n — i) = n. Caso contrário, isto é, se 0 < i < n — 1, então
n — i > 1, donde i(n — í) > i. Portanto, ainda nesse caso, temos que
(i + l)(n — Í) = i(n — i) + (n — i) >i + n — i = n. Convém agora que
atentemos para uma sutileza do problema. Observe que, para n = 1 ou
para n = 2, (n!)2 = nn. No entanto, para n > 3, garantimos a existência
de i tal que 0 < i < n — 1, fato que nos garantirá a desigualdade que vem
a seguir:
(n2)! (n!)2 nn .
Parte II. Resoluções - Combinatória básica 101
93. (a) Para resolvermos este item, faremos uso da identidade explicitada na
sugestão. Assim, temos:
1 • 1! = 2! - 1!
2- 2! = 3! - 2!
3- 3! = 4! - 3!
n 1 _ 1
(n 4- 1)1 n! (n 4-1)!
Portanto, somando membro a membro as igualdades obtidas, e fazendo
os cancelamentos apropriados, vem que (i+í)! = ~ (n+i)!’
94. (a) Temos uma quantia de 6! = 720 números distintos de seis dígitos
cada. Dispondo todos os números, um abaixo do outro, podemos efe
tuar a soma coluna a coluna. Em cada uma delas (unidades, dezenas,
centenas etc.), cada algarismo aparece tantas vezes quantas forem
as permutações dos algarismos das demais, ou seja, 5! = 120 vezes.
Portanto, em cada coluna, os algarismos que nela aparecem somam
i 120 • 1 4- 120 ■ 2 4- 120 • 3 4- 120 • 4 4- 120 - 5 4- 120 • 6 = 2.520. Con
siderando, por fim, a ordem de grandeza de cada coluna, obtemos a
soma 2.520(1 4- 10 4- 100 4- 1.000 4- 10.000 4- 100.000) = 279.999.720,
que é o número procurado.
(b) Para resolvermos este problema, basta que contemos os números que
precedem o número dado. São eles, obviamente, os números de 5
102 Problemas Resolvidos de Combinatória
16!
= 2.627.625.
4! (4!)5
A divisão da fração inicial por 4! tem por finalidade desprezai* a ordem
dos grupos, pois estes, segundo o enunciado, são indistinguíveis.
(b) Agora, devemos repetir o raciocínio empregado no item anterior, obser
vando que temos três grupos com 2 objetos e dois grupos com 3 objetos.
Parte II. Resoluções - Combinatória básica 103
Logo, temos:
16!
= 252.252.000
3! • 2! (2!)4 • (3!)3 ■ 41
96. (a) Como a palavra em questão possui 10 letras distintas em sua com
posição, o número de anagramas possíveis da palavra IMPORTUNAS
é 10! = 3.628.800.
(b) Uma vez que os anagramas a serem contados devem começar por IMP,
nesta ordem, restam 7 letras distintas a serem permutadas nas posições
seguintes. Logo, são 7! = 5.040 anagramas, neste caso.
(c) Agora além de permutarmos as restantes 7 letras, devemos permutar
as três do trecho IMP, obtendo um total de 3! • 7! = 30.240 anagramas.
(d) Agora, o trecho IMP não precisa estar necessariamente no início do
anagrama. Podemos, então, considerá-lo como um bloco além das 7
letras já existentes. Logo, temos 8! = 40.320 anagramas possíveis.
(e) As três primeiras letras devem ser IMP, nesta ordem, as três seguintes
devem ser ORT, em ordem aleatória, e as quatro últimas devem ser
UNAS, também em qualquer ordem. Portanto, o número de anagra
mas, neste caso, é 3! • 4! = 144.
97. Podemos denotar os rapazes por ri, 7*3 e r4, e as moças por mi, m? e 7723.
Analogamente, cada cadeira vazia será denotada por v. Assim, interessa-
nos o número de permutações de ri^rzr^mirr^msvvvv nas quais os blocos
de cadeiras destinados aos rapazes e às moças permanecem intactos, embora
as posições de cada rapaz e de cada moça em cada um deles possa variar.
Assim, considerando as repetições existentes (lugares vazios), temos um
total de - -^j'3! = 4.320 disposições diferentes das pessoas.
homens: x
Convidados do marido
mulheres: 7 — x
homens: 7 — x
Convidados da esposa
mulheres: x.
Agora, para cada x (1 < x < 7), temos as seguintes escolhas a realizar:
(a) escolha dos x homens pelo marido: ;
(b) escolha das 7 — x mulheres pelo marido: (7 ®a.);
(c) escolha dos 7 — x homens pela esposa: (7 ;
(d) escolha das x mulheres pela esposa: (®).
Note que, se x = 0, então o marido deve ter convidado 7 mulheres e a
esposa 7 homens, o que é impossível. Da mesma forma, x = 8 conduz a
Parte II. Resoluções - Combinatória básica 105
é©U) =
-C)’©‘+C)‘G)‘+©’C)
2 2 2 2
4-
©x©s
= 3.427.776
possíveis convites.
+ i)G7i)
(?)
tomando p = i 4- 1 nessa ‘nova’ identidade. Logo:
n—1 n—1
(»+i)g;,) n(n 4-1)
E
i=0
(")
= ^(n — i) = 14-24-------F n =
i=0
2
101. (a) Para que as simplesmente apareça, basta que escolhamos 7 elementos
dentre os 11 restantes. Logo, (l,1) = 330 é o número de vezes em que
106 Problemas Resolvidos de Combinatória
2(3 (I) 28 ,
+ y® 11
9t(j-1) y(y-l)
=> 2 2 - 28
x^^ + y^^- 11
(*-i)(y-i) = 28
0/ - 1) + (z - 1) ' 11
28
=> (rr - l)(j/ - 1) = — (x + y - 2). (1)
{x — l)(y — 1) = 28
(x - 1) + (y - 1) = 11.
104. Podemos supor a existência de 10 caixas, cada uma das quais contendo
algarismos idênticos entre si. Isto é, suponhamos que a caixa 0 contenha
apenas algarismos iguais a 0, a caixa 1 contenha apenas algarismos iguais
a 1, e, assim, sucessivamente. Suponhamos, ainda, que todas as caixas
contenham os algarismos correspondentes em quantidade ilimitada. Con
sideremos que, da caixa 0, vamos retirar xq algarismos iguais a 0, da caixa
1, vamos retirar aq algarismos iguais a 1, e assim por diante. Como os
números em questão devem ter 7 algarismos, o número de soluções inteiras
não negativas da equação xq + rcj + • • • + xg = 7 é justamente o resultado
que procuramos, ou seja, o número de colunas escritas. Isso ocorre porque
cada coluna se caracteriza pela quantidade de dígitos de cada tipo existentes
em cada um de seus elementos, isto é, com uma solução da equação acima.
Portanto, retirando-se o caso em que são selecionados sete algarismos iguais
a 0, obtemos, como resposta ao problema, — ~ Cg ) — 1 ~ 11.439,
utilizando o Exercício 25.
(b) Este item possui resolução similar à do anterior. Tomando cada vértice
da base, podemos conectá-lo a cada um dos n vértices da face paralela
à base (a qual chamaremos “tampa” do prisma). Entretanto, três
dessas conexões não devem ser consideradas diagonais. De fato, cada
vértice da base é ponto de encontro de três arestas, sendo duas delas
pertencentes à base e uma delas perpendicular a esta, conectando a
base à “tampa”. Essas três arestas formam, pois, um triedro. Assim,
os três segmentos que partem do vértice em questão e terminam em
pontos de intersecção do triedro com a “tampa” (por sua vez, vértices
da “tampa”) não devem ser considerados diagonais do prisma. A figura
que vem na seqüência ilustra nossas considerações para um prisma
pentagonal:
c*
D’ B*
D B
E A
106. Pela relação de Stifel-Pascal (vide parte (b) do Exercício 60), temos que
110 Problemas Resolvidos de Combinatória
Logo:
K00][0+0]-[(
n
=n[0+(.
n-1 / I l\
k 4-1
= n (n j
=n>0 n—1 _ —1 /
n— \
-i—
(n + l)n
n!
00 ■■■(:)■
107. (a) Vamos demonstrar essa identidade de duas maneiras diferentes, ambas
muito elegantes: algebricamente e por argumentos combinatórios.
• Demonstração algébrica;
O Binômio de Newton nos garante que (a + ò)n.
(;)•(?)•-4:) = È(")
i=0 V 7
= è(?) r-i
i=0 X 7
= (l + l)n
= 2n.
k 4- 1 k 4-1 fc 4-2
4-
k k +1 k+1
k+2 k + 2' k 4~ 3
k
+ k +1 k 4" 1
k+3 fc +3 k + 4'
k
+ k 4- 1 k 4- 1
k+r k 4- r k 4- r 4- 1
k
+ k 4“ 1 k 4- 1
que:
k 4- r k -I- r + 1
k k 4- 1
a
(A: - z) (k (k — i)!(a — k 4- i)l
k—i
a (q-i)!
(k — i — l)!(a — k 4- ?)!
a— 1 \
a k — i — 1) ’
fc-i z
0-1
k — i — 1/
i=0 '
fa 4~ b —
a k— 1 )’
Parte II. Resoluções - Combinatória básica 113
a+b— 1 (a + b — 1)1
a a
k—1 (k — l)!(a + b — k)l
ak (a + 6)!
a + b kl(a + b — k)\
ak í a + b\
a + b\ k J
109. (a) Note que, para cada i E N tal que 1 < i < n, vale o fato de que
í(”) = ^iT(n-í)! = n(í-i)7(n-í)i ~ n(?-i) (este mesmo resultado se
encontra também no item (a) do Exercício 50). Logo:
-§•©n / 1\
-g—>©
i=0
n
i=l \ / i=0 x 7
= 2 • n2n-1 + 2n
= (n+ l)2n,
-K3 n — 1\ n—1
+• ■•+("-1)-"(”) =
n—1
= 1•n 1 ) +2•n +3•n 4-----
2 3
n — 1\
4- (n — 1) • n
n — 1J
n— 1 n—1 n— 1 n—1
=n +2 +3
1 2 3 n—1
= n • (n - l)2<n-1>“1
= n(n- l)2n-2,
110. (a) Suponhamos que xi, x^, ..., xn sejam as n variáveis que temos à
disposição. Um termo típico de um polinômio homogêneo de grau p
tem a forma sendo cuj 4- «2 + • • • + &n = p, já que
os termos devem ter grau idêntico. E fácil ver, então, que o número
de termos diferentes de um tal polinômio corresponde ao número de
Parte II. Resoluções - Combinatória básica 115
113. (a) Como os temas são todos distintos, os k grupos devem ser também
considerados distintos. Assim, a partir dos kr alunos originais, pode
mos escolher os r responsáveis pelo primeiro tema de (^r) maneiras
diferentes, os r responsáveis pelo segundo tema de (fcr~r) =
maneiras distintas. Prosseguindo com esse raciocínio, os k grupos
poderão ser formados de:
(kr^ Ç(k — l)r ) Ç(k - 2)r) Ç [k — (k — l)]r
r
(fcr)!
________ [(fe ~ lk]! [(fc-2)r]l r!
r![(fc — l)r]! r![(fc — 2)r]! r![(fc —3)r]! r!0!
(fcr)!
(r!)fc
maneiras distintas.
(b) Agora, os grupos devem ser considerados indistinguíveis, pelo fato de
todos possuírem o mesmo tema e a mesma cardinalidade. Logo, es
colhido um tema dentre os k existentes, é suficiente que dividamos o
resultado encontrado no item anterior por fc!, visando a desprezar a
ordem dos grupos. Assim:
(fcr)! (fcr)!
k-
fc!(r!)fc (fc — l)!(r!)*
é o número de maneiras de se realizar a divisão dos grupos, nesse caso.
114. (a) Entre Paulo e Marta, deve haver 3 pessoas. Contando, além delas,
Paulo e Marta, temos um bloco composto de 5 pessoas. Como a fila
possui 8 posições, esse bloco pode ocupar 4 posições diferentes. Além
disso, Marta e Paulo podem, a cada permutação, trocar de posição, o
que nos impele a multiplicar o resultado final por 2. Finalmente, as
6 posições restantes podem ser preenchidas de 6! maneiras distintas.
Portanto, a resposta ao problema é 2 • 4 • 6! = 5.760.
(b) Agora, como as 8 pessoas devem sentar-se numa mesa redonda, haverá
três pessoas entre Paulo e Marta nos dois sentidos, a saber, horário e
anti-horário. Fixando, então, Paulo e Marta em duas cadeiras (note
que todas as maneiras de se fazer isso são equivalentes, uma vez que a
mesa é redonda), sobram-nos 6 cadeiras, as quais podem ser ocupadas
pelas 6 pessoas restantes de 6! = 720 maneiras, resultado do problema.
Analogamente, poderiamos, em primeiro lugar, permutar 6 pessoas
circularmente (excetuando-se as duas em destaque) de (6 — 1)! = 5!
Parte II. Resoluções - Combinatória básica 117
+70}’ í3'! }»•••! {^íq —1}> {*£ío+l}’ • • • > {■Ejo—1}’ {a'jo+l}> • • • >
Agora, ocorre que, na etapa anterior à da obtenção de P^\ dois dos seus
elementos (os quais são subconjuntos de A) deviam estar “fundidos”. Ora,
como P^ possui n — 1 elementos, o número de possibilidades para que
isso tivesse ocorrido é A seguir, obtivemos um outro conjunto P^
contendo n — 2 elementos. No passo anterior, dois deles haviam de estar
“fundidos”, o que pôde ocorrer de (n22) maneiras diferentes. Portanto,
prosseguindo com esse raciocínio até 2\ contendo apenas dois subcon
juntos de A (resultado da primeira partição realizada), poderiamos obter
P^ de (2) = 1 maneira. Assim, pelo processo inverso ao do particiona-
mento, chegamos ao conjunto P^ l\ cujo único elemento é o conjunto
A. Portanto, uma vez tendo analisado todas as possibilidades disso ter
20Consideraremos, nesta resolução, que a “fusão” é o processo inverso da partição.
Parte II. Resoluções - Combinatória básica 119
n\ (n — 1)! (n — 2)! 3! 2!
” 2!(n- 2)! ’ 2!(n —3)! ’ 2!(n - 4)! 2! • 1! 2! 0!
n!(n — 1)1
— 2n-1 ’
n!
(n — Zc)
fc!(n — &)!
n!
= (k + 1)
(Zc 4- l)!(n — k — 1)!
/ n \
= (fc+1) U +1/
da identidade, que:
7l!
(fc+1) k + l)+k\k) + + l)!(n - fc - íj!
n\
+k
k\(n — k)\
(n — k)n\ k • n!
+
kl(n — fc)! fc!(n — fc)!
(n — fc)n! 4- k • n!
fc!(n — fc)!
n\
n k\{n — k)\
- ■(:)
§C)(*T n v
J \k + s- jj
(;)(*:•
K:M)( / n
k+s—
) \k + ns — 1
1}( + ...
J \k + s — kj'
Como na resolução do item anterior, vamos considerar n caixas distin
tas contendo, cada uma, pelo menos dois objetos idênticos e nenhum
diferente destes e, ademais, que caixas distintas possuam objetos dis
tintos. Agora, desejamos selecionar s + k objetos dessas caixas em
duas etapas: primeiro, selecionar s distintos entre si e depois mais k
distintos entre si, mas não necessariamente distintos dos s já escolhi
dos. O número de maneiras de se fazerem tais seleções é igual a (”) (£).
Analogamente, podemos dividir a mesma contagem em diversos ca
sos. Primeiro, podemos selecionar k + s objetos distintos dentre os n
tipos existentes de maneiras e, em seguida, podemos selecionar
s objetos dentre os k + s já selecionados de (fc^s) maneiras (estes
corresponderíam à primeira etapa da escolha e os k restantes à se
gunda etapa). Assim, (q) (fc^s) (fc”s) conta o número de seleções em
Parte II. Resoluções - Combinatória básica 121
00 - oc s + (n — s)
k
■ 0 §(■)(:: 3
■ §(:)(:©©■ (2)
ín\ ín — s\ n! (n — s)!
s!(n —s)! (k — j)!(n — k — s + j)l
n! (k + s — j)!
(k + s — j)l(n — k — s + f)l sl(k — j)\
n
k+s—
(:)(:) -
§(■k + ns-jjV'\
- £©(' n i
k + s - jj ’
122 Problemas Resolvidos de Combinatória
0© ■ C)(‘"’©A
- oècr
- g ©(”©)(/<)■ (3)
(:)(:)
S + j) \ j J\k- j)
= v (s+J; V 5 V n (4)
s+jV s
. j J\k~ j) = (s + j)!
j!s!
s!
(k - j)!(s - k + j)!
(s + j)! kl
à:!(S + j-T)! jl(k-j)l
(:)© - k
- g©g(*)(z (5)
- ©(©,)
124 Problemas Resolvidos de Combinatória
0© - £©£©(,!,)(.«)
i y n \
- S0©2( k-jj \s+jj
- £ (•) © GVÍ'
como queríamos demonstrar. Na última das passagens acima, uti
lizamos, novamente, o Exercício 71, para n = n + i, m = s + kep = n.
Com relação ao fato de, na demonstração anterior, ter aparecido, como
limite superior do somatório, k em lugar de m, podemos justificá-lo
da mesma forma que fizemos no item (b) do Exercício 118.
120. (a) Como pode haver prateleira vazia, o número de livros em cada uma
corresponde ao número de soluções inteiras não negativas da equação
X\ +%2 + + ^4 + X5 = 25, que corresponde a = (24)- Além
disso, para cada uma dessas divisões, podemos permutar os livros de
25! maneiras diferentes, uma vez que devemos considerar a sua ordem
em cada uma delas. Logo, 25! • (249) = número da ordem de 1029,
é a quantidade de divisões possíveis dos livros nas prateleiras.
(b) Considerando as 23 letras do nosso alfabeto escritas em seqüência,
como não pode haver palavras “vazias”, temos 22 espaços entre as
letras para dispor 4 divisões, que determinarão, obviamente, 5 palavras
distintas. Assim, (22) escolhe tais espaços. Uma vez fixados tais espa
ços, podemos permutar as letras de 23! maneiras diferentes, e temos
também que desprezar a ordem das palavras formadas, dividindo o
resultado final por 5!. Assim, a resposta é ^r(242), número da ordem
de 1024.
121. (a) Para resolver este item, consideremos todas as m-combinações com
repetições de p diferentes moedas21 e n—p diferentes notas de dinheiro.
Além disso, suponhamos que cada moeda e que cada nota de dinheiro
21 Uma m-combinação com repetições de p diferentes objetos corresponde a uma seleção de m
objetos a partir de p tipos distintos, de tal maneira que cada tipo de objeto possa ser tomado
mais de uma vez. Pelo Exercício 25, ainda, segue que o total dessas m-combinações corresponde
ao número de soluções inteiras não negativas de xi + • • • + xp = m, ou seja,
Parte II. Resoluções - Combinatória básica 125
m+n—p— m+n—p—2
. n-p-1 _
+ •••
. n-p-1
m + p — 1\ ín-p- 1\
+ J \n ~ P - V ’
. P~ 1
isto é, o segundo membro da identidade em questão. Por outro lado,
sabemos que o total de m-combinações com repetições de p moedas
e de ?i - p notas de dinheiro é igual ao total de m-combinações com
repetições de n elementos distintos, a saber, Logo, o resul
tado está demonstrado.
(b) No resultado do item anterior, basta substituir p por p+1, n por n + 2,
e m por m — n. A identidade, então, segue imediatamente.
E .91252.
9=1
= 125 + 31 + 13 + 7 + 5 + 3 + 2 + 1 + 1 + 1 + 1 = 190.
'2n + r\ /2n — r\
72 J \ 72 J
(2n4-r)! (2n —r)!
71!(t2 4”7")! 721(77.-7')!
(2n 4- r)!(2n — r)!(2n)(2n — !)••• (2?2 — r 4- 1)72(72 — 1) • • • (72 — r 4- 1)
n!(72 4- r)!72!(?2 — r)l(2n)(2n — 1) • • • (2t2 — r 4- 1)72(72 — 1) • • • (n — r 4-1)
(2?2 4- r)(272 4- r — 1) • • • (2tt 4- l)(272)!(272)!n(?2 - 1) • • • (72 - r 4- 1)
71!(72 4- r)(n 4- r — 1) ■ • • (72 4- l)72!n!72!(272)(272 — !)••• (2n — r 4-1)
[(2t2)!]2 272 4-t" 2714-7" — 1 +1 n
2n 4-1 n—1
72 n — r+1
(6)
(n!)4 n+r n+r—1 n 4-1 2n 2n — 1
tz 2n — r + 1
2n + k 2n — k
<
n+k n—k '
2n 4- r
n
[(2r»)!]2 2n 4- r 2n — r 4- 1 272 -1 n n—1 n — r 4-1
<
(n!)4 n+r n — r 4- 1 72—1 2n 272 -1 2n — r 4-1
((2n)!]a 2n 4- r n
(n!)- n+r 2n
<
[(2n)f 2n n
(n!)4 72 272
=C)’
128 Problemas Resolvidos de Combinatória
Na última desigualdade, utilizamos que 22±r < ^i. De fato, isto vale se, e
somente se, (2n + r)n < (n + r)(2n) <=> 2n2 + nr < 2n2 + 2nr <=> 0 < nr, o
que é sempre verdade. Logo, segue que:
N
\kJ \k — 1/ (?)
(k- ! fc-2
\ k
+ k—1
+■"+(?)
= 0 + 0 +•••+ 0
= 0,
sendo tal representação única, dado que > 0, para 1 < i < k, e
0 < xi < x2 < ■ • . < xk.
Parte II. Resoluções - Combinatória básica 129
(x\ = (Xk~1
N = (Í} \k k—~\}
ykj + (k
N - \k) \k — 1 1/
130. (a) Para responder tal questão, procederemos contando a quantia de nú
meros em que o dígito 9 não aparece, subtraindo este resultado do total
de números que podem ser formados, obtendo, assim, o valor procu
rado. Como só nos interessam números menores do que 1.000, pode
mos nos restringir aos 999 números compreendidos entre 1 e 999. Não
contendo 9 em sua formação, temos 9*9-9 = 729 números diferentes
(observe que os números de um dígito e de dois dígitos também foram
contados como, por exemplo, 081 e 007). Nesse caso, todavia, conta
mos também o número 000 = 0, donde se tem apenas 728 números a
serem retirados de 999, obtendo-se 999 — 728 = 271 como resposta ao
problema.
Para que o dígito 9 ocorra duas vezes, o número deve ter pelo menos
dois dígitos. Se tiver exatamente 2, só é possível o número 99. Se tiver
3, os 2 dígitos 9 podem ocupar as últimas duas casas (8 opções), ou
as extremidades (9 opções), ou as duas primeiras posições (9 opções).
Lembrando que também há o caso do número 999, temos como res
posta: 1+84-9-1-9-1-1 = 28 possibilidades.
(b) Aplicaremos o mesmo procedimento do item anterior. Para números
de 3 dígitos, são 9-9-9 = 729 os números em que 0 não ocorre.
Considerando números de 2 dígitos, o número de vezes em que 0 não
ocorre é 9 • 9 = 81. Por último, são 9 os números com um dígito
distintos de 0. Logo, temos 729 + 81 + 9 = 819 os números menores do
que 1.000 que não apresentam 0 em sua composição. Assim, a resposta
ao nosso problema é o total de 999 — 819 = 180 números.
Com relação ao número de vezes em que o dígito 0 aparece duas vezes,
é fácil ver que isso só é possível se exatamente as últimas duas casas
forem ocupadas por tal dígito. Logo, são 9 as possibilidades nesse caso.
(c) Vejamos a quantidade de números que não apresentam nem 0 nem 9
em sua composição. E claro que, neste caso, temos 8 opções para cada
casa, donde 8-8-8 = 512 é a quantia de números de 3 dígitos que
não apresentam 0 nem 9 em sua formação. Quanto a números de 2
dígitos, são 8 • 8 = 64 aqueles que não apresentam 0 nem 9 em sua
formação. Finalmente, para números de um só dígito, temos apenas
8 opções. Portanto, é igual a 512 + 64 + 8 = 584 o número de vezes
em que nem 0 nem 9 ocorrem. Logo, 999 — 584 = 415 é a quantia de
números que apresentam 0 ou 9 em sua composição. Logo, sendo n o
valor procurado, temos, utilizando os resultados dos itens anteriores,
Parte II. Resoluções - Princípio da Inclusão e Exclusão 131
131. (a) Caria lançamento pode resultar em 6 valores distintos e, como são 6
os lançamentos, o número de possibilidades é igual a 66 = 46.656.
(b) Por razões didáticas, vamos dividir o problema em casos:
i. número de maneiras de resultarem 6 faces idênticas;
E fácil ver que, como só temos seis valores possíveis, são apenas 6
as possibilidades nesse caso.
ii. número de maneiras de resultarem exatamente duas faces distin
tas;
Sejam, por exemplo, tomadas as faces 1 e 2 dos dados. Calculare
mos o número de maneiras de que exatamente tais faces resultem
no lançamento. Como temos 6 dados e cada um deverá resultar
em 1 ou 2, são 26 as possibilidades. Nesse número, porém, estão
embutidos os dois casos em que só uma das faces ocorre (só o valor
1 ou só o valor 2). Então, para cada par de faces distintas, temos
26 — 2 opções em que exatamente duas faces ocorrem. Ocorre,
ainda, que são as escolhas possíveis das duas faces. Então, o
resultado é (®) ■ (26 - 2) = 15 • 62 = 930.
iii. número de maneiras de resultarem exatamente 3 faces distintas;
Aplicando uma resolução similar à da parte ii, tomemos as faces
1, 2 e 3 dos dados e vejamos qual o número de maneiras de as três
22
Aqui, utilizamos que, dados dois conjuntos A e B, é válida a igualdade:
©WCP-G) • 46 6
• 26
e |A n B O C| = 4! = 24. Portanto:
134. Observe que temos uma expressão com 10 letras constando de 5 pares de
letras iguais. Para maior praticidade, vamos dividir o problema em casos:
= 3-
60.
5!
-34+3!
2! • 2!
(a) Vamos inicialmente considerar o total de divisões que podem ser feitas,
incluindo casos em que alguma pessoa não recebe letras. Como dispo
mos de 6 letras a, devemos dividir tais letras entre três pessoas o que,
como sabemos, pode ser relacionado com a equação xi 4- X2 4- X3 = 6.
Nela, cada variável representa as quantidades de letras a que vão ser
distribuídas para cada pessoa, e 6 é o total disponível de letras a
serem distribuídas. Então, o número de divisões possíveis da letra em
questão é igual ao número de soluções inteiras não negativas da dita
equação, que sabemos ser dado por (3+|-1) = (|) = 28. Além disso,
devemos dividir as 9 letras restantes (que são duas a duas distintas)
entre as três pessoas. Assim, chegamos a um total de divisões igual
a 28 • 39 = 551.124. Desse número, entretanto, devemos retirar os
casos em que alguém não recebe nenhuma letra. Considere os con
juntos X — {divisões em que a pessoa X não recebe nenhuma letra},
para X = A,B,C. Procuramos o valor de |A U B U C|. Observe
agora que |A| = |B| = |C| = 7 • 29 = 3.584, sendo que 7 e 29 con
tam, respectivamente, o número de maneiras de se distribuírem as
letras a e o número de maneiras de se distribuírem as outras letras
entre as duas pessoas candidatas a recebê-las. Além disso, observe
que |A A B| = |A Cl C| = \B D C| = 1, pois só há uma maneira de dar
todas as letras a alguém. Por último, é claro que |,4 A B Cl C| = 0.
136 Problemas Resolvidos de Combinatória
|AuAuA3| =
= |Ai| + |A| + |AI — |Xi n Al - |A n Al — IA nAl
+ IA n A2 n A3| = 3 • 233 - 3 • 232 + 23 = 34.937.
n n
9n = (10 + (-l))n (-ir =Ê(-üQio’
i=0 v ' i=0 ' '
+ (-1)"-1
n
= E(-l) (:)■”
138 Problemas Resolvidos de Combinatória
gn 10n lOn-f
- w+ £(-!>■ Q) 10n-i
n
10n-i
38. (a) Para encontrarmos a resposta deste item, basta que tenhamos clara a
definição de função, segundo a qual cada elemento do domínio deve
possuir uma única imagem no contradomínio. Assim, para cada um
dos n elementos do domínio A, existem k possíveis imagens no con
tradomínio B, donde kn é o número de funções f : A —> B.
(c) Analogamente ao que fizemos no item (a), temos k(k — 1) • • • (fc —n+1)
funções injetoras.
= E(-d O-*)”
1=1
139. (a) Cada pessoa deve receber 7 peças. Para tanto, uma maneira simp._
de resolver o problema é colocar todas as peças em fila e, em seguida,
distribuir as 7 primeiras para a primeira pessoa, as próximas 7 para
a segunda pessoa e, assim, sucessivamente. E claro que, para pôr as
peças em ordem, temos 28! possibilidades. Entretanto, como a ordem
das mesmas em cada um dos 4 grupos de 7 peças é irrelevante (pois
só desejamos distribuí-las às pessoas), o total de distribuições a que
chegamos é
(b) O problema que temos agora equivale ao de dividir 28 objetos distintos
entre 4 caixas distintas de modo que nenhuma caixa fique vazia. Note,
porém, que o número de maneiras de se realizarem tais divisões é
justamente o de funções sobrejetoras de um conjunto de 28 elementos
em outro de 4 elementos. Como vimos no item (d) do Exercício 138,
este número é:
+ (-!)“ Q)(4-4)28
428 - 4 • 328 + 6 • 228 - 4,
140. (a) Denotemos Ai = {disposições em que o i-ésimo casal fica junto}. As
sim, | AuAuAuAuAl é igual ao número de permutações circulares
nas quais pelo menos um dos casais permanece junto. Bastar-nos-á,
então, subtrair esse valor do total possível de disposições dos 5 ca
sais. Observe, porém, que |A| = 2-8!, sendo o fator 2 responsável
por considerar a ordem do i-ésimo casal e 8! responsável pela per
mutação circular das 8 pessoas restantes juntamente com o i-ésimo
casal. Analogamente, temos | A D Aj\ = 22 • 7!, | A O Aj D A| = 23 • 6!,
|A n Aj n Ak n Al = 24 • 5! e | A n a2 n A3 n A n Al = 25 • 4!. Logo,
pelo Princípio da Inclusão e Exclusão, vem que:
|A u Au A u A u A| =
= 0(2-89- (|)(22-7!) + Q}(23-6!)- Q)(2<5!)
+ G) (25 • 4!) = 250.368.
IAU...U A| =
= f”}(2-(2n-2)!)- Q(22-(2n-3)!) + ---
(2"(n - 1)!)
n
= E(-1)-' Q(2i-(2n-i-l)l).
1=1
1 1
m i-y-+ ^<í —
y PiPj + + PlP2--'Pr
xÍíjPiP^
i- —
v pij \ P2J ' Pr
como queríamos mostrar.
142. (a) Havendo tantas latas quanto queiramos de cada tipo, basta que conte
mos quantas latas de cada um dos tipos serão compradas, número que
sabemos coincidir com a quantidade de soluções inteiras não negativas
da equação xi 4- x? 4- X3 4- X4 = 15. Assim, há (
possíveis compras, utilizando o Exercício 25.
i5ir*) = ca=«is
(b) Neste caso, teremos que nos valer do Princípio da Inclusão e Exclusão.
Considerando a mesma equação do item (a), definamos, para cada i,
os conjuntos Ai = {compras de 15 latas nas quais Xi > 7}, sendo x, o
número de latas de refrigerante do tipo i que foram compradas. Assim,
do total calculado em (a), devemos retirar IA1UA2UA3UA4I para obter
o número desejado. Consideremos, por exemplo, o cálculo de |Ai|. Se
rzq > 7, então x±—7 > 0. Logo, podemos substituir, na equação do item
(a), xi — 7 por yi, e Xi = yi para i 1. Então, temos a nova equação
2/1 + 2/2 + 3/34-3/4 = 8. Assim, |Ai | corresponde ao número de soluções
inteiras não negativas desta equação, isto é, = (V) = 165- ^or
simetria, vem também que JAsl = IA31 = | A4I = 165. Analogamente, o
número de elementos de Ai D Aj é igual ao número de soluções inteiras
não negativas de yi 4- 2/2 4- 1/3 + V4 — 1> que é igual a 4. Agora,
observando que as intersecções de três ou mais dos conjuntos Ai são
vazias (para elas, o número de latas compradas é pelo menos 21, que é
maior do que 15), temos que |Ai U A2UA3UA4I = 4-165— (2) -4 = 636.
Logo, a resposta é 816 — 636 = 180.
6’s juntos. Assim, devemos fazer a mesma contagem que fizemos com os
conjuntos anteriores e, em seguida, subtrair uma vez o total de ordenações
das nove letras nas quais há 3 6’s juntos. Logo, |B| = — ^jp = 4.410.
Analogamente, temos \A l~) C*| = |A A £>| = |C Cl £>| = 5T3! = 420, e ainda
|A A B| = |B D C| = |B A D| = pjrp — ^p = 1.080. Além disso, temos
lAnCnPI = g = 120 e |AabaC| = |Aabal>| = |BaCa£>| = = 300
e, finalmente, |A A B D C A £>| = 5! — 4! = 96. Portanto:
|AUBUCUD| = (3-1.680 + 4.410)-(3-420 + 3-1.080)
+ (120 + 3 ■ 300) - 96
= 5.874.
9! - 5.874 = 1.686.
Portanto, a solução que procuramos é igual a (2!)á-3!
9 8 6 5 4 3 2 1
= 9!
1!
+7
2! '3! 4!
+ 5!
+
6! '7!
+ 777
8! ' 9!
Portanto, o número de permutações possíveis é igual a:
98765432 1
10! - 9!
1! 2!
+ 3! 4! + 5! 6! +'7! ~ 8! +' 9!}
= 9!
w _ 2,1 _ I , 1 _ £ , £ _ _3 1
1! + 2! 3! + 4! 5! + 6! 7! + 8!
9!
= 1.468.457.
144 Problemas Resolvidos de Combinatória
147. Como os algarismos de 1.000.000 não têm soma igual a 15, podemos con
siderar todos os inteiros entre 1 e 999.999 como sendo de seis dígitos. Por
exemplo, 43 pode ser visto como 000.043. Representando cada algarismo
por a?i, X2, ..., xq, o resultado do problema consiste no número de soluções
inteiras não negativas da equação aq + • • • + xq = 15, desprezando-se as
soluções em que Xi > 10, para 1 < i < 6. Ocorre que o número de soluções
da equação acima é igual a = (25°), pelo Exercício 25. Supondo
agora, em particular, x^ > 10, podemos fazer a substituição xi = yi + 10
e Xi = yi, 2 < i < 6, recaindo na equação yi + • • • + y& = 5, com yi > 0
para cada i. Assim, obtemos uma nova equação que possui — (5°)
soluções. Como tal raciocínio pode ser empregado para cada uma das seis
variáveis da equação original, a resposta do problema é (25°)~ 6(5°) = 13.992.
Observe que esta é uma aplicação do Princípio da Inclusão e Exclusão.
Para calcularmos |XU VUZ|, os itens (a) e (b) nos fornecem, respecti
vamente, |X| = |y| = \z\ = 980 e |x n y| = |x n z\ = |y n z\ = 620.
Logo, resta-nos calcular jX ny n Z\, o que não será tarefa fácil! Con
siderando os blocos AA, BB e CC, temos 6! permutações envolvendo
eles e as letras remanescentes A, B e C. Nestas, contamos duas vezes
as permutações que contêm AAA, BB e CC, duas vezes as que contêm
AA, BBB e CC, e duas vezes as que contêm AA, BB e CCC. Por
exemplo, as que contêm AAA ocorrem 5! = 120 vezes. Logo, como
são três os casos, temos uma nova quantia de 720 — 3 • 120 = 360 per
mutações. Acabamos, agora, por retirar duas vezes as permutações
que contêm AAA, BBB e CC, duas vezes as que contêm AAA, BB e
CCC, e duas vezes as que contêm AA, BBB e CCC. Cada um desses
grupos de permutações tem número de elementos igual a 4! = 24.
Portanto, nosso novo sub-resultado é o valor 360 + 3-24 = 432. Final
mente, estamos agora contando duas vezes as permutações que contêm
AAA, BBB e CCC, que são em número de 3! = 6. Temos, enfim, que
|X A y A Z| = 432 - 6 = 426. Logo:
146 Problemas Resolvidos de Combinatória
149. Denotemos os alemães por Ai, A2, A3, os espanhóis por Ei, E2, E3, e os
franceses por Fi, F2, F3. Então, nosso problema se reduz a encontrar o
número de permutações das letras A1A2A3E1E2E3F1F2F3, de modo que
não haja letras de mesma espécie juntas. Ora, o item (c) do Exercício 148
nos garante que a resposta seria igual a 174 caso não houvesse índices nas
letras. Ocorre que, se considerarmos cada permutação das letras sem os
índices, podemos acrescentá-los de (3!)3 maneiras (3! escolhas para cada
tipo de letra). Logo, a resposta é 174 • (3!)3 = 37.584 modos distintos.
150. Considerando que são apenas duas pessoas, basta que dividamos os objetos
para uma delas, pois, dessa forma, os da outra também ficam determinados.
Sendo assim, considere que xy, X2 e x3 sejam as quantidades de cada um
dos três tipos de objetos distribuídos a uma das duas pessoas. Então,
nosso problema se resume a encontrar o número de soluções inteiras não
negativas da equação x^ + X2 + x3 = 3n, sujeita à restrição de que Xi < 2n,
para i = 1,2,3, pois só dispomos de 2n objetos de cada tipo. O número de
soluções da equação acima é ('. 3n+3-1
3-1 ) ~ Agora, retiraremos desse
montante as soluções que apresentam uma das variáveis maior do que 2n.
Particularmente, para zi > 2n, tomemos x{ = xi — 2n — 1 > 0, x'2 = %2 e
x'2 = X3. Assim, temos a nova equação x{ + x'2 + x'3 = n — 1, que possui
zn—1+3—1
l 3-1 ) = (”2*) soluções. Como os casos em que X2 > 2n e x3 > 2n
possuem soluções idênticas, o resultado é ('3n2+2) - S^J1) = 3n2 + 3n +1.
Observe, por fim, que esta foi uma aplicação do Princípio da Inclusão e
Exclusão.
151. (a) Basta que efetuemos a distribuição dos objetos para duas pessoas, pois,
assim, os objetos da terceira também ficam determinados. Sendo zi,
X2 e X3 as quantidades de cada um dos três tipos de objetos distribuídos
à primeira pessoa e y\, y2 e 7/3 as quantidades de cada um dos três tipos
de objetos distribuídos à segunda pessoa, nosso problema se resume a
Parte II. Resoluções - Princípio da Inclusão e Exclusão 147
xi 4- xq + X3 = n
yi+y2 + yz = n,
sujeito à condição Xi+yi < n, para i = 1,2,3, uma vez que só dispomos
de n objetos de cada tipo. O número de soluções inteiras não negativas
de cada uma das equações do sistema acima é (”3^1 ) = (nJ2)- Logo, o
número de soluções do sistema, sem restrições, é ("J2) C*^2)- Todavia,
o número de soluções do problema que violam a condição rei 4- yi < n
corresponde ao número de soluções do sitema:
^2 + = r, 0 < r < n
?/2 4- ?/3 = s, 0 < s < n,
com r 4- s < n, ou seja, r < n — s — 1. Para cada par (r, s), as soluções
do sistema são em número de (r 4-l)(s 4-1). Como s varia de 0 a
n — 1 e r varia deOan — s — 1, temos o seguinte número de soluções
inconvenientes, nesse caso:
n—1n—s—1
(r+i)(s+i) =
s—0 r=0
n—1 n—s—1
= 3=0 12
r=0
(r+
= + 1) (n-5)(n-s+l)
So 2
n—s+1
-GXTHXMXV)- -G)©
í n 4* 2 4“ 1\
= \ 34-1 )
ín 4- 3\
"l 4 /’
aplicando, na penúltima passagem, o resultado encontrado no item (b)
do Exercício 121, para m = n + 2, n — 3 e p = 1. Obviamente, para
os casos X2 4- y-2 < n e x$ 4- yz < n, por simetria, devemos chegar
148 Problemas Resolvidos de Combinatória
possíveis distribuições.
(b) Basta aplicar a resposta encontrada no item anterior para n = 6. Logo,
temos 2) (6 2 2) — 3(6^3) = (®)2 — 3(9) = 406 maneiras de realizar
tal distribuição.
Parte II. Resoluções - Funções geradoras e partições 149
(_l)r = ( (-”)(-”-1)-"(-n-r + l)
( l)r( 1)rn(n+1)---(n + r~ !)
(n + r — 1)!
= (~l)2r
r!(n — 1)!
n 4- r — 1\
r J
No desenvolvimento anterior, utilizamos o conceito de Binômio de
150 Problemas Resolvidos de Combinatória
x16 1 —X )
1___________
(1 — x:2)(1 — x3)2(l — x5)’
154. (a) Uma das maneiras de provarmos este resultado é imaginar que se
dispõe de n caixas distintas, cada uma contendo m objetos idênticos.
Supondo que só se pode selecionar caixas inteiras, podemos não sele
cionar nenhuma caixa de uma única maneira. Podemos selecionar uma
caixa de n maneiras. Em geral, r caixas podem ser selecionadas de (”)
maneiras distintas, sendo que, ao selecionarmos r caixas, estamos, na
verdade, selecionando mr elementos. Desta maneira, por um lado, a
função geradora para tais escolhas é a função (1 4- xm)n e, por outro, é
a função 1 4- (™)xm 4- (^(z”1)2 -I------ 1- (xm)n. Como ambas as funções
controlam as mesmas escolhas, vale a identidade.
(b) Com relação a f(x), podemos imaginar que dispomos de três caixas
distintas, cada uma das quais contendo n objetos idênticos. O coefi
ciente de x2n+1, bem o sabemos, pode ser interpretado como o número
de maneiras de se escolherem 2n 4-1 objetos das três caixas. Como, de
cada uma, podemos retirar no máximo n objetos, pelo menos um de
cada caixa deve ser selecionado. Portanto, uma vez efetuada a seleção,
tomemos um objeto proveniente de cada caixa (como cada caixa pos
sui n elementos idênticos, tal seleção é única). Ora, isso é como se
as caixas iniciais tivessem, cada uma, apenas n — 1 objetos e, em vez
de selecionarmos 2n 4- 1 objetos, selecionássemos 2n — 2, seleção que
é contabilizada pelo coeficiente de x2n~2 em g(x). Reciprocamente,
se tivermos três caixas contendo, cada uma, n — 1 objetos idênticos e
desejarmos selecionar 2n — 2 objetos, podemos acrescentar um objeto
de cada tipo na seleção, acabando por escolher 2n 4-1 objetos, o que é
contabilizado pelo coeficiente de x2n+1 em /(x). Assim, os coeficientes
em questão são realmente idênticos.
152 Problemas Resolvidos de Combinatória
= (1 4- x 4- x2 4- • • • 4- xn-1)3
/I -xn 3
\ 1 —X
= (1 — 3xn 4-3x2n - x3n)(l - x)-3.
[x25(l-x100 )(l-x,25)-l]6 =
_ t150 (1 — X:100)6(l — x::25)-6
= (x6 — X13_a.16_
— ax.20 + ...)(1_a.)-3
f-i V (n + m - 2^ — 1 n \ Zn — 1\
1 n-1 m/2/ \n — 1/
n + m — 21 — 1
1=0 \ / \ n—1
= Ui • 1 4- 03 ■ 3 4- • • • 4- a2m+i(2m 4- 1).
Agora, pelo Exercício 157, sabemos que cada um dos a^s pode ser escrito
de maneira única como soma de potências distintas de 2. Então, temos:
159. (a) Suponhamos uma dada partição de n cuja maior parte é igual a k.
Representando-se tal partição num Diagrama de Ferrers25, sua primei
ra linha, claramente, deve possuir k pontos. Em seguida, tomemos sua
partição conjugada26. Ora, este novo diagrama possui k Unhas, donde
a partição deve possuir k partes. Assim, a cada partição de n cuja
maior parte é fc, associamos outra que possui k partes. Similarmente,
dada uma partição de n em k partes, tomando sua partição conjugada,
obtemos uma partição de n cuja maior parte é igual a k. Assim, está
demonstrado o que queríamos. Observe que pequenas alterações na
demonstração anterior poderão nos conduzir ao fato de que o número
25Caso não esteja familiarizado com este conceito, consulte a referência bibliográfica [13],
26 A partição conjugada de uma dada partição é aquela cujo diagrama de Ferrers é obtido
trocando-se cada linha do diagrama original por coluna. Observe que esta transformação dá
origem a uma nova partição de n, já que o número total de pontos é preservado.
156 Problemas Resolvidos de Combinatória
44 = 10 4-9 + 64-5 + 4 + 3 + 2 + 2 + 2 + 1,
44 = 19 + 15 + 7 + 3.
160. (a) Caso não houvesse recomendações de se fazer uso de Funções Gerado
ras para resolver este problema, o mesmo tornar-se-ia trivial. De fato,
para expressarmos n como soma de duas partes, digamos a eb, basta
que façamos com que a percorra valores entre 1 e [^J.
Primeiramente, vamos calcular o número de partições de n em, no
máximo, duas partes. Como vimos no final da resolução do item (a)
do Exercício 159, este número é o mesmo que o de partições de n
cujas partes são limitadas por 2. É fácil ver que a função geradora
que controla o número de partições de n em partes iguais a 1 ou 2 é a
função:
1
(1 — x)(l — X2)
Para resolvermos o problema, então, devemos calcular o coeficiente de
xn na expansão acima. Observe, porém, que:
1 1 1
(1 — x)(l — X2) 2(1 -x)2
+ 2(1 -x2)'
oo
IP1**:3i+1)(l +x:3i+2)
t=i
: =
(1 - x6í+2)(l - x6i+4)
“ 11 (i _ X3Í+1)(1 _ 3-31+2)
OO oo
1
:6i+2)(l-x' (l-a:3*+i)(1-a;3i+2)
í=l i=l
oo
= ID -
Í=1
■6i+2)(l - x',6i+4) .
°o i
n (i - a^+lXi - X6i+4)(i - x6í+2)(1 _ 3»6i+5)
o° 1
=n (i-x6i+i)(i-x6i+5) ’
como desejávamos.
162. (a) Dada uma partição de n em três partes, é claro que pelo menos
duas dessas partes devem ser menores do que pois, caso contrário,
teríamos duas partes maiores do que ou iguais a o que é uma
contradição. Assim, suponhamos que n = a + b + c, com a,b <
e acrescentemos a a e a ò, obtendo a' = a + % < % + % = n,
b' = b+ ^<^ + ^=n, e d = c < n, de modo que 2n = a' 4- b' 4- d é
uma partição de 2n em três partes menores do que n.
Por outro lado, dada uma partição de 2n em três partes menores do
que n, é claro que pelo menos duas delas devem ser maiores do que
5, pois, caso contrário, teríamos duas menores do que ou iguais a
implicando que a terceira fosse maior do que n, uma contradição.
Assim, seja 2n = a 4- b 4- c, com a, b > Tomando a' = a — > 1,
160 Problemas Resolvidos de Combinatória
(1 4- z)5e18a:
é igual a (9^4 xx) • 14! = (32) • 14!, valor da ordem de 1013. Nessa última
etapa, utilizamos o resultado do Exercício 25.
(c) E trivial o fato de que o número de n-uplas possíveis de se formarem
com os elementos de {1,2,... ,k} é igual ao número de maneiras de
se distribuírem n objetos distintos em k caixas distintas. De fato, no
primeiro caso, temos k opções de preenchimento para cada posição.
Logo, kn é o número de n-uplas. No segundo, temos k escolhas de
caixa para colocar cada objeto. Assim, o número de distribuições é,
também, kn. E interessante observar que este é, ainda, o número
de funções existentes de um conjunto de n elementos em um de k
elementos.
Assim, considerar a contagem das distribuições dos 14 símbolos nas 4
palavras de modo que a primeira contenha pelo menos dois símbolos
e cada uma das outras contenha pelo menos um símbolo equivale a
considerar a contagem das 14-uplas formadas por elementos do con
junto {1,2,3,4} nas quais o número 1 aparece pelo menos duas vezes,
e os números restantes aparecem, pelo menos, uma vez. Ora, a função
geradora para a contagem de tais 14-uplas é a função:
X2 3
(x2 x3 \ /
(ã+3T + "J V X+ 2! + "'
= (e1 - x - iXe1 - 1) 3
= (ex — x — l)(e3a: — 3e,2x + 3ex _
= e4x — xe3x — 4e3x + 3xei2x
2* + 6e2x — 3xex — 4ex + x + 1.
14
Estamos, portanto, interessados no cálculo do coeficiente de yyy na
expansão acima. De maneira simples, o valor procurado é igual a:
414 - 14 • 313 - 4 • 314 + 42 • 213 + 6 • 214 - 42 - 4 = 227.425.380.
9 9
(b) A diferença deste item em relação ao anterior é que, neste caso, basta
que, em vez de a + b > c, tenhamos a + b > c. Assim, da mesma forma,
teremos y = b - a > 0, z = c- b > 0 e a > z. Nesta etapa, contudo,
a resolução diverge da do item anterior, pois teremos que dividir o
problema em dois casos:
Parte II. Resoluções - Funções geradoras e partições 165
x3
(x3 + x6 4----- )(1 4- x2 + x4 4------ ) =
(1 — x:‘2)(1 — x3)
168. (a) Suponhamos um objeto particular x dentre n 4-1 objetos iniciais. Com
relação à distribuição de tal objeto dentre as k caixas, ou ele ficará
sozinho numa delas, ou ele ficará acompanhado de ao menos um objeto.
No primeiro caso, só há uma maneira de depositá-lo sozinho numa das
caixas, uma vez que elas são idênticas, e há, por definição, S(n, k — 1)
maneiras de distribuirmos os n objetos restantes nas outras k — 1
caixas idênticas. No segundo caso, podemos primeiramente distribuir
os n outros objetos entre as k caixas de S(n, k) maneiras. Uma vez
ocupadas por objetos distintos, as caixas passam a ser distinguíveis,
havendo k possibilidades para o acréscimo de x a uma delas. Logo,
S(n 4- 1, Â:) = S(n, k — 1) 4- kS(n, k). Observe ainda que, como são
triviais os fatos de que, para cada n, 5(n,n) = S(n, 1) = 1, a relação
anteriormente provada torna o cálculo de 5(n, fc) possível para cada
166 Problemas Resolvidos de Combinatória
I2s(n,ky-
n=0
oo
[(fc - i)r]n
n=0
n\
kí i=0 x 7
fc Z1 \
1
~ Zc’
’ í=o
(e1 - l)fc
k\
utilizando, na última passagem, a Fórmula do Binômio de Newton.
(c) Agora, por informação do enunciado da questão, temos que:
n n
Bn = S^n' = S(n’
fc=l fc=0
uma vez que 5(n,0) — 0. Logo, utilizando, ainda, o resultado do item
(b), temos:
k
-1)— = étex — 1
Z3 Bn^\’ = n=0fc=0
n=0
ZL è ZZ
= fc=0 fc!
Expandindo a função geradora acima num software matemático, obte
mos:
X° X1 X2 X3 X4 X5 X6
= 1Õ!+1ir+22!+53!+154!+525!+2036r + -
Assim, por exemplo, Bq = 203, isto é, existem 203 partições de um
conjunto de 6 elementos.
Parte II. Resoluções - Funções geradoras e partições 167
l
169. (a) Considerando que se dispõe de um número ilimitado de cada um dos
dígitos em caixas separadas, o problema equivale a retirar dígitos das
4 caixas de tal maneira que a ordem da retirada é levada em conta.
Além disso, deve ser retirada uma quantidade par de 0’s e ímpar de l’s.
Portanto, é necessária a utilização de funções geradoras exponenciais
controlando a presença de cada um dos tipos de dígitos na seqüência.
A função que controla a presença do dígito 0 é igual a:
„ X2 X4 1 ,
1+2!+4!+- = 2(e +C >'
x3 x5 l.x
*+ 3! + 5T + "“2(e
170. (a) Se nenhum dígito deve ocorrer exatamente duas vezes, a função gera
dora que controla a presença de cada um deles é igual a:
z3 x4 .X
x2
1 + a:+3!+¥ + "=ff 2?
Logo, o número que procuramos é o coeficiente de yy na expansão de:
9 3 T2
X rr4 T
ex
T = é,3x - 33—
2C + 3— e
4 8
1
#4)- X'
6
x3
+ 2 + e~2x ex
= 4 'T
.3 -r3
1.1 X' ,2x
37 e~2x
— -e
=
- 4 3x + 26x +
+ -e 24ee21 — —
4C x — —
4- -e~ 24 6e-2* - —
12'
Efetuando agora os cáculos, para r 3, temos como resposta o coefi
ciente:
3r 1 f-l)r , ... _2nr
r —3 or-3
- r(r - l)(r - 2)— + (-l)r-2r(r - l)(r - 2)—,
4 2 4 v M 7 24 ' '
ou, pondo em evidência os termos adequados:
(—l)r + 3r + 2 r(r — l)(r — 2)2r~3 . ,
4 24 k k h
Para o caso r = 3, basta subtrair | do resultado precedente, já que
1 X3 __ X3
2 ' 3! — 12-
171. (a) Observe que, para que tenhamos soma par, o número de faces ímpares
que aparecem deve ser par. A função geradora que controla o número
de faces pares é a função que, na expressão fornecida pelo
enunciado deste item, está fora dos colchetes. De fato, sabemos que:
1
= (1 + X + x2 + .. .)(1 + X + x2 + .. .)(1 + X + x2 + . . .).
(1 — x)3
Observe, então, que os três termos entre parênteses, à esquerda, con
trolam o número de faces iguais a 2, 4 e 6, respectivamente.
Agora, vamos mostrar que a expressão que está dentro dos colchetes
é a função que controla o número de faces ímpares, de tal maneira
que elas apareçam, em conjunto, um número par de vezes. De fato,
observemos que:
1 ___ 1
(1 — x)3 +
+ (1 + x)3
= (1 + x + x2 + .. .)(1 + x + x2 + .. .)(1 + x + x2 + . . .) (9)
+ (1 - X + x2 - .. .)(1 — x + x2 — . . .)(1 - X + x2 - ...). (10)
170 Problemas Resolvidos de Combinatória
1 1 1 1
2 (1 — x)3 (1 — x) 3 (1 + x)3_
12
n=0
n bn)x —
OO oo
,n
= ^2 an^ 12 bnx,n‘
71=0 71=0
_ 1 1 _______
1
2 (1 — x)3 (1 — x)3
+
1 1 _______
1
2 (1 — x)3 (1 — x)3
_ 1 1 1
_______ 1
2 (1 — x)3 [(1 — x)3
+ (1 — x)3
+
=1. 1 -2- 1
2 (1 — x)3 (1 + x)3
1
(1 — x2)3
OO
=E
r=0
(-l)rx2r.
= ^f + l-
Xj + xj yj + yj Zj + Zj
2’2’2
Xr + Xs yr 4- ys zr + zs
2 2 ’ 2
173. Obviamente, qualquer pessoa deve possuir entre 0 e 300.000 fios de ca
belo. Consideremos, portanto, esses 300.001 tipos de pessoas, e agrupemos
os habitantes de São Paulo em termos do seu número de fios de cabelo.
Observando agora que 10.788.682 = 300.001 • 35 + 288.647, deve haver 36
pessoas em São Paulo com o mesmo número de fios de cabelo. De fato,
se houver no máximo 35 pessoas em cada um dos 300.001 grupos exis
tentes, então os habitantes de São Paulo ficariam reduzidos a, no máximo,
300.001 ■ 35 = 10.500.035, o que é uma contradição. Esta é uma aplicação
do que denominamos Princípio da Casa dos Pombos. Portanto, n = 36 é a
resposta do problema.
174. (a) Suponhamos que existam 5 caixas numeradas, de tal modo que, na i-
ésima caixa, coloquemos o(s) objeto(s), dentre a, e b,, que satisfaz(em)
a propriedade P, para i = 1,2,3,4,5. Como são 5 as caixas e dois os
tipos de objetos (aj’s e b/s), pelo Princípio da Casa dos Pombos, como
5 = 2 • 2 -I-1, pelo menos três caixas devem conter, em conjunto, três
aj’s ou três bj’s.
(b) Como no item anterior, suponhamos 10 caixas numeradas, de tal modo
que, na í-ésima caixa, coloquemos o(s) objeto(s), dentre a,, bi e Ci, que
satisfaz(em) P, sendo i = 1,2,..., 10. Como 10 = 3 • 3 4-1, deve haver
pelo menos 4 objetos de um mesmo tipo (a,, b, ou c,) satisfazendo P.
Logo, n = 4.
(c) Conjeturemos que n = 4. Suponhamos, então, que não haja quatro
ai’s com a propriedade P. Portanto, deve haver dois aj’s, digamos
ai e 02, que não satisfazem P, donde bi, b2, Cl e C2 satisfazem P.
Restam-nos, pois, três bi's e três c/s. Novamente pelo exposto no
enunciado, destes, deve haver pelo menos mais dois b^s ou pelo menos
mais dois c^s satisfazendo P, donde segue o resultado. Agora, se
n = 5, não há garantia da validade da afirmação. De fato, poderiamos
ter P satisfeita apenas por ai, 02, 0.3, bi, 63, 64, bs, C2, C4, C5, não
contemplando a afirmação dada, donde concluímos que n = 4. Note,
no exemplo fornecido, que aparecem quatro b/s satisfazendo P. De
174 Problemas Resolvidos de Combinatória
•D
Observe que qualquer um dos 6 pontos deve estar ligado aos 5 pontos
restantes, formando 5 segmentos, de sorte que, como são duas as cores
disponíveis, deve haver pelo menos três desses segmentos coloridos
com uma mesma cor. Seja, como na figura acima, A o nosso ponto
de origem, determinando três segmentos vermelhos: AB, AC, AD. Se
pelo menos um dentre BC, CD e BD for vermelho, então pelo menos
um dentre os triângulos ABC, ACD e ABD é vermelho. Por outro
lado, se BC, CD e BD forem todos azuis, então BC D é um triângulo
azul.
(b) Sugerimos, neste caso, que o leitor acompanhe a explicação subseqiien-
te fazendo uma figura. Cada um dos 17 pontos deve ser ligado aos
16 restantes, formando 16 segmentos. Destes, como 16 = 3-5 + 1,
pelo menos 6 devem ser coloridos com a mesma cor. Por exemplo,
suponhamos que A seja o nosso ponto de origem, e que AB, AC, AD,
AE, AF e AG sejam segmentos verdes. Se um dos segmentos que
unem entre si os pontos B, C, D, E, F e G for verde, então já se
forma um triângulo verde. Por exemplo, se BD for verde, então o
triângulo ABD é verde. Por outro lado, se nenhum desses segmentos
Parte II. Resoluções - Princípio da Casa dos Pombos 175
for verde, então devemos notar que B, por exemplo, deve se ligar
a C, D, E, F e G, formando 5 segmentos. Como argumentamos
no item anterior, pelo menos três dentre estes devem ser, digamos,
vermelhos. Suponhamos, então, sem perda de generalidade, que BC,
BD e BE sejam vermelhos. Ora, pelo mesmo raciocínio aplicado no
item anterior, haverá um triângulo de mesma cor (vermelha ou azul)
envolvendo apenas os pontos B, C, D e E.
3
EB3
178. Consideremos a seqüência aj, a2> •••, an2+i- Seja í; o número de ter
mos da mais longa subseqüência crescente que tem início em ai, para
i = 1,2,..., n2 + 1. Se algum ít- for pelo menos n 4- 1, o problema está
terminado. Caso contrário, isto é, se, para cada i, tivermos 1 < ti < n,
teremos n2 4- 1 t^s a assumirem n valores distintos, a saber, 1, 2, ..., n.
Se cada um desses valores aparecer no máximo n vezes, teremos somente
n2 valores de ti, o que é uma contradição. Logo, existem pelo menos n 4- 1
ti’s iguais. Agora, vamos mostrar que os üí's associados a esses n 4- 1 t,’s
compõem uma subseqüência decrescente. Supondo, para tais termos, que
ti = tj para i < j, devemos mostrar que ai > aj. Como os termos da
seqüência original são distintos, se a, < aj, então a» seguido pelos tj termos
da subseqüência crescente que começa em aj compõem uma subseqüência
crescente de tj + 1 termos começando em a,, donde ti > tj 4- 1, o que é
contraditório. Logo, ai > aj, e o resultado está provado.
176 Problemas Resolvidos de Combinatória
179. (a) Primeiramente, observe que dois números consecutivos quaisquer são
primos entre si. Para que um subconjunto do conjunto dado não pos
sua elementos primos entre si, ele não poderá conter números con
secutivos. Ocorre que {1,3,5,...,2n — 1} e {2,4,6,... ,2n} são os
maiores subconjuntos que obedecem tal condição. Como ambos pos
suem apenas n elementos, e o subconjunto que desejamos deve conter
n + 1 elementos, concluímos que qualquer subconjunto do conjunto
dado possui um par de números consecutivos. Portanto, o resultado
está demonstrado.
Agora, para provar que todo n+ 1-subconjunto do conjunto dado pos
sui pelo menos um par de números tais que um divide o outro, basta
considerar que todo elemento compreendido entre 1 e 2n pode ser
escrito na forma 2^/71, sendo m ímpar e variando entre 1 e 2n, ou
seja, assumindo, no máximo, n valores distintos. Como os subconjun
tos considerados devem possuir n + 1 elementos, concluímos que pelo
menos dois dos seus elementos devem ser produto de uma potência de
2 pelo mesmo m, a saber, 2rm e 2sm. Assim, como r s, fica provado
o resultado.
(b) Considere os 8 números abaixo:
43
4343
434343
43434343
4343434343
434343434343
43434343434343
4343434343434343
Como temos mais do que 7 números, pelo menos 2 deles devem possuir
restos iguais ao serem divididos por 7. Tomando a diferença entre esses
2 números, obtemos um múltiplo de 7 da forma 43... 43 • 102A:. Como
102fc não é múltiplo de 7, concluímos que 43... 43 deve ser múltiplo de
7. Assim, encontramos um múltiplo de 7 da forma 43 ... 43. Agora,
ampliando, de maneira conveniente, a seqüência original de números
da forma 43... 43, obtemos tantos múltiplos de 7 quanto desejarmos,
o que prova o resultado solicitado.
Parte II. Resoluções - Princípio da Casa dos Pombos 177
|çq -p| = |(t - s)a - ([ia] - LsqJ)I = l(ÍQ _ lÍQJ) ~ (sa - LsqJ)I
donde segue que:
P 1
a---- < —.
nq
Isso prova que todo intervalo da reta, por menor que seja, sempre contén
números racionais, isto é, que o subconjunto Q dos números racionais é
denso no conjunto dos números reais R, como se costuma afirmar em Análise
Matemática.
178 Problemas Resolvidos de Combinatória
Probabilidade
181. (a) Denotemos a e v, respectivamente, cada bola azul e cada bola vermelha
retirada da caixa. Para que o palhaço permaneça seco, em cada ponto
da seqüência formada de a’s e v’s, o número de a's deve ser maior
do que ou igual ao número de v’s. Ou seja, em cada momento, o
número de passos para trás dados até então deve ser maior do que ou
igual ao número de passos para frente. Ora, estamos exatamente nas
condições do Exercício 83, assumindo os a’s em lugar dos c’s e os v's
em lugar dos d’s. Analogamente, o fato do palhaço estar inicialmente
na ponta do trampolim da piscina equivale ao fato do caixa daquele
exercício inicialmente não possuir troco. Logo, o número de maneiras
do palhaço ficar seco é igual a:
n — n + 1 (n +ri 1 (2ri\
n n + 1 \ n )'
(Í)
(b) Vamos reduzir este problema ao tratado no Exercício 83 de uma manei
ra muito simples. Uma vez organizadas as duas filas de n pessoas de
acordo com suas alturas, podemos dar 5 reais a cada uma das pessoas
da primeira fila e 10 reais a cada uma das pessoas da segunda. Feito
isto, arranjamos as 2n pessoas numa única fila por altura, obtendo
uma nova fila de 2n pessoas na qual n possuem 5 reais e n possuem 10
reais. Afirmamos, então, que, uma vez tendo feito a organização por
altura, obtemos uma fila “boa” no sentido empregado no Exercício 83.
De fato, considere a pessoa que pertencia à fc-ésima posição da segunda
fila. Então, há pelo menos k pessoas maiores do que ela e que possuem
5 reais (as k primeiras da primeira fila) e, no máximo, k — 1 maiores
do que ela e que possuem 10 reais (as k — 1 primeiras da segunda fila).
Isso implica que não há problemas com troco para nenhum membro
da fila, isto é, que esta fila é “boa”. Além disso, tomando qualquer
pessoa que pertencia à primeira fila, também não há problema com
troco, pois cada uma dessas pessoas já possui 5 reais.
Parte II. Resoluções - Probabilidade 179
182. Note que as faces devem ser números naturais, pois a face de um dado
nunca é nula. Assim, |A| corresponde ao número de soluções positivas da
equação a+ò+c= 9 e |£?| corresponde ao número de soluções positivas
dea + ò + c = 10, contanto que a,b,c < 6. Ora, as únicas soluções de
a + b + c = 9 que devem ser desprezadas são as três formadas pela trinca
(7,1,1). Portanto, |A| = (3Z]) — 3 = (®) — 3 = 25, utilizando o Exercício
25. Analogamente, as soluções de a + 6 + c = 10 que devem ser desprezadas
são as 3! = 6 da trinca (7,1,2) e as 3 da trinca (8,1,1). Portanto, vem
que |B| = (— 6 — 3 = (9) — 9 = 27. É claro, ainda, que o conjunto
de todos os lançamentos dos dados tem cardinalidade 63 = 216, donde
n(n — l)(n — 2) • • • (n — r + 1) n!
nr nr(n — r)!'
(b) Como um ano possui 365 dias, se r = 366, então, pelo Princípio da
Casa dos Pombos, pelo menos duas pessoas farão aniversário no mesmo
dia, donde a probabilidade de que duas pessoas façam aniversário no
180 Problemas Resolvidos de Combinatória
X)!?) 30
1.771'
1-4 14
n—1 n—1
1
14 N 14
n—1
N
n—2
2
>
14 N
> • ■ •
n—n
04 n
N
1-4
Parte II. Resoluções - Probabilidade 183
a = --^- = n,
22^
28Dada uma função f : R —» R, definida por /(x) = aax2 + a\x -I- ao, para 02 > 0, seu valor
mínimo Xmin ® dado por Xmin = 202"
184 Problemas Resolvidos de Combinatória
188. (a) Como os dados possuem cores distintas, podemos denotá-los por di,
d2, CÍ3, CZ4, d$ e de. Temos 6 possibilidades para o valor obtido em
di, 5 para d2, 4 para da, 3 para d^, 2 para ds e 1 para dg (não pode
haver faces repetidas). Portanto, como o total de lançamentos é 66, a
probabilidade de que todas as faces sejam distintas é
(b) O valor que aparecerá em todas as faces é um dos 6 possíveis. Logo,
® a probabilidade, nesse caso.
(c) Existem (3) = 20 maneiras distintas de ocorrer o mesmo valor em
três dados distintos, e o valor que neles aparece pode ser qualquer
um dos 6 possíveis. Em seguida, os valores que aparecerão nas faces
restantes podem ser escolhidos de 5 • 4 • 3 = 60 maneiras. Portanto, a
probabilidade requerida é 6'26°660 =
(d) Temos 6(3) = 120 possíveis resultados para os três dados que conterão
um mesmo valor, 5(2) = 15 possibilidades para os dois dados que
conterão outro valor, e 4 possibilidades para o dado restante. Assim,
a probabilidade é igual a 120665'4 =
189. (a) Como todos os seis dados são idênticos, para que todas as faces sejam
distintas, só há uma possibilidade. Agora, façamos a contagem de
todas as ocorrências possíveis. Ora, para caracterizarmos o que ocorre
num lançamento, basta que determinemos quantas faces de cada valor
aparecem. O número de possíveis lançamentos, desse modo, é igual
ao número de soluções da equação xi + • • • + xq = 6, para Xi > 0,
que é igual a = (V) ~ 462, pelo Exercício 25. Portanto, a
probabilidade de que todas as faces sejam distintas é
(b) Se todas as faces devem conter o mesmo valor, a probabilidade é igual
a _6_ _ J_
d 462 — 77’
(c) Temos 6 possibilidades para o valor que aparece nas três faces iguais.
Quanto às três faces restantes, devemos contar as ocorrências com 3
valores distintos dentre os 5 restantes, o que resulta (3) = 10 maneiras.
Portanto, é a probabilidade, nesse caso.
(d) Agora, são 6 opções para as três faces repetidas, 5 para as outras duas
repetidas, e 4 para a outra face. Logo, é a probabilidade
solicitada.
Parte II. Resoluções - Probabilidade 185
(?)(^)
(?) '
Em Teoria das Probabilidades, dizemos que a expressão acima, como função
de k, segue o modelo hipergeométrico de distribuição.
191. (a) Trabalhar com seleções de cartões sem reposição equivale a efetuar
contagens de números de 7 algarismos distintos dentre 1, 2, 3, 4, 5,
6 e 7. O total de números ímpares, neste caso, é 4 • 6!, sendo que 4
conta as possibilidades para o preenchimento da casa das unidades do
número (1, 3, 5 ou 7) e 6! conta as opções de preenchimento de suas
6 casas restantes. Ora, como 7! é o total de números, a probabilidadt
de que o número obtido seja ímpar é
(b) Agora, uma vez que há reposição dos cartões na caixa, pode haver
repetição de algarismos nos números considerados. Nesse caso, são
4 • 76 números ímpares, de um total de 77 números. Assim, temos
que a probabilidade cujo cálculo nos foi solicitado é = i. Note
que ela coincide com a obtida no item (a). Em geral, deixaremos ao
leitor a tarefa de provar que, se a caixa inicial contivesse n cartões
numerados por 1, 2, 3, ..., 72, então, ao se retirarem 72 cartões com
ou sem reposição, as probabilidades de se obter número ímpar seriam
idênticas (inclusive para 72 par).
193. (a) Como as bolas de mesma cor são indistinguíveis, só há uma maneira
de se extraírem da urna 3 bolas de cada cor. O número total de
maneiras de se extraírem 9 bolas da urna corresponde ao número de
soluções inteiras não negativas da equação Xi + x% + x$ = 9, para
0 < Xi < 6. A função geradora que controla cada uma das variáveis Xi
é 1 + x + x2 d------ F x6 = Logo, o número de soluções da equação
acima é igual ao coeficiente de x9 na expansão de:
1-x7 3
= (1 - x7)3(l - x)~3 = (1 - 3x7 + 3x14 - x21)(l - x) 3.
1 —X
194. (a) Para que um apostador faça uma quadra, 4 dos 6 números sorteados
devem ter sido por ele escolhidos de maneiras. Quanto às outras
duas dezenas escolhidas, devem estar entre as 42 não sorteadas de (422)
maneiras. Assim, o número de casos favoráveis ao apostador é (8) (422).
Como o total de apostas possíveis é (468), a probabilidade de que 0
apostador acerte exatamente quatro dezenas é:
(!)(?) 4.305
(?) “ 4.090.504
(I) ■ 42 21
(?) 1.022.626
195. (a) Das 8 dezenas escolhidas pelo apostador, deve haver 3 sorteadas e 5
não sorteadas. As 3 sorteadas podem ser escolhidas de (3) maneiras e
as 5 não sorteadas, de (755) maneiras. Uma vez que o total possível de
apostas distintas é (8g), a probabilidade desejada vale:
©(?) 1.278
(?) 214.643’
(5(7) 1.278
(?) ~ 214.643’
naturalmente coincidindo com o resultado anterior.
(b) De modo análogo ao item anterior, resolveremos o problema, a princí
pio, baseados nas escolhas do apostador, supondo o sorteio já reali
zado. Sabemos que, das 8 dezenas por ele escolhidas, 4 devem ter sido
sorteadas e 4 não devem ter sido sorteadas. Logo, (4) (45) é o número
de escolhas que o favorecem, donde a probabilidade desejada é igual
a:
(5(7) 315
(“) 1.502.501'
Como outra forma de resolução, podemos efetuar a contagem dos
sorteios que favorecem o apostador, tendo ele feito sua aposta. A fim
de que ele faça a quadra, ele deve ter escolhido quatro dos valores
sorteados de (8) maneiras e, com relação ao quinto valor do sorteio,
deve estar entre os 72 que ele não escolheu. Logo, a probabilidade
desejada é:
(5(7) 315
(?) 1.502.501
(c) Neste caso, aplicando novamente os dois tipos de resolução dos itens
(a) e (b), temos que a probabilidade é igual a:
©(?) (5(7) 7
(?) (?) 3.005.002 ‘
196. (a) Representando os dez carros por q, C2,..., cio, e cada lugar vago por v,
para que não haja vagas vazias consecutivas, basta que consideremos o
total de maneiras de se encaixarem 4 v’s entre as 10 letras de C]C? ■ • • Cio
de modo que cada v fique entre dois Ci’s ou num dos extremos da
permutação. Como são 11 os espaços em tais condições, temos (l4)
190 Problemas Resolvidos de Combinatória
30
14!
= ---.
4!
91
e) ■
(b) Dentre os p pés retirados do armário, deve haver k pares de sapatos.
Portanto, 2k sapatos devem estar aos pares e p — 2k não devem possuir
seu par. Os k pares de sapatos podem ser escolhidos de (£) maneiras.
Em seguida, (escolhe quais os pares aos quais pertencem os p—2k
sapatos que não tiveram seu par escolhido. Cada um desses p — 2k
sapatos, finalmente, pode ser pé esquerdo ou direito do seu par. Assim,
Parte II. Resoluções - Probabilidade 191
(n\fn-k\ np—2k
\kJ \p—2k) ' Z
(?)
198. Acompanhe a figura abaixo para entender a resolução deste problema:
v.
V^l
c*
Vn+1
199. (a) Observe que, como há disputa de terceiro lugar, o jogador que chegar
à semifinal (n — 1-ésima etapa) jogará, necessariamente, mais um jogo
(a saber, a final ou a disputa do terceiro lugar). Assim, não é possível
que um jogador dispute exatamente n — 1 partidas durante o torneio,
donde p(n — 1) = 0. Para 1 < k < n — 2, temos que A deve participar
de exatamente k etapas do torneio. Ora, para que isso ocorra, ele
deve ganhar todas as k — 1 partidas anteriores e perder a k-ésima
partida. A probabilidade de ocorrência de cada um desses k eventos
é igual a | donde, nesse caso, p(fc) = (|)*. Finalmente, para k — n,
basta calcular a probabilidade de que A vença as n — 2 primeiras
partidas. Dessa forma, A chegará até a n — 1-ésima etapa, e jogará,
por conseguinte, n partidas, incluindo a desta eta^a e a da final ou a
da disputa do terceiro lugar. Assim, p(n) = (|)n~ ■
(b) Dado o interesse deste item, duas engenhosas resoluções serão apre
sentadas.
Em primeiro lugar, suponhamos que p(fc) denote a probabilidade de
que A e B se enfrentem num torneio reunindo 2k jogadores (dentre
os quais A e B se encontram), de modo que p(n) refere-se à resposta
do problema. A fim de que A e B se enfrentem na primeira etapa do
torneio, eles devem ser uma das 2n-1 duplas desta etapa. Supondo
que isso ocorra, os 2n — 2 jogadores restantes podem ser agrupados de:
(2n-2
;)(2(V:
n-i -1)!
!)(V)-(Ê)©
(2n—1 )'■
(2"-1-1)! 1 (271-1)!
o (2—1)!
(2H-1 - 1)1
(V)
2n-i
1 2n — 2 1 . 1 2n -2
p(n) =
2n - 1 + FTirp(n-1) = 2n — 1 + 22(2n - 1) p(n- 1).
Iterando seguidas vezes tal relação, temos:
1 2n - 2 / 1 2n-1 - 2
p(n) =
2n — 1 + 22(2n - 1) V2n-1 - 1 + 22(2n-l _ !)
p(n - 2)
1 1 271-1 - 2
2n — 1
+ 2(2n - 1) +
+ 23(2n - 1) p(n - 2)
1 1
2n — 1
+
2(2n - 1)
2n-i -2 1 on—2 _ 9 \
+ 23(2n - 1) + 22(2n—2
1 1 1 2n~2 - 2
+ 2(2n - 1)
2n — 1 + + 22(2n - 1) + 24(2n - 1)
p(n - 3),
194 Problemas Resolvidos de Combinatória
1 1 1 22 — 2
p(n) =
2n - 1
+’ 2(2n - 1) +•••+ 2n-2(2n _ 1) + 2n(2n - l)^1)
1 1 1 1
+’ 2(2n - 1)
+ ... + + 2^-i (2n - 1)
2n — 1 2n“2(2n - 1)
1 1 1 \
1 + - + -.- + 2n-i J
2n — 1
1
2n — 1 1 “ 2 /
' 2n —1 \
1 2n |
2n - 1 1 I
2 /
1
2n~i’
1 1 1 2n — 2 1 1
1-
2n-1 4 2n-1 - 1 2n - 1 ' 2(2n - 2) 2(2n - 1)'
Parte II. Resoluções - Probabilidade 195
Como não há surpresas nos jogos, é claro que A e B vencem suas partidas,
passando à segunda fase do torneio. Nesta etapa, a probabilidade de que
ambos não se enfrentem é:
1 2n-1 - 2 2(2n~1 - 2)
1-
2n-1 - 1 ~ 2n-1 - 1 2n — 2 '
Prosseguindo com este raciocínio, a probabilidade de que A e B não se
enfrentem na fc-ésima etapa é:
1 2n-k+1 - 2 2(2n-fc+1 - 2)
1-
2n-(fc-i) _ | — 2n~k+1 — 1 — 2n~k+2 — 2 ’
para k e N tal que 1 < k < n - 1. Assim, a probabilidade de que os dois
melhores jogadores não se enfrentem até a n — 1-ésima etapa é igual ao
produto das probabilidades de não se enfrentarem em cada uma das n — 1
etapas iniciais. Portanto, o valor que procuramos é:
2n - 2 2(2n-1 - 2) 2(2l’n“2 - 2) 2(22 - 2) 2n~2(22 - 2) 2n-i
: n-2
2n — 1 ’ 2 2«-i _ 2 23 -2 2n - 1 2n - 1
E interessante observar que esta probabilidade é máxima (igual a 1) para
n = 1 e aproxima-se de | à medida que n cresce.
196 Problemas Resolvidos de Combinatória
201. A probabilidade de que uma dada pessoa não aniversarie hoje é igual a |||.
Logo, dentre n pessoas, a probabilidade de nenhuma aniversariar hoje é
(|H)n. Logo, 1 — (j^)n refere-se à probabilidade de que pelo menos uma
dentre n pessoas aniversarie hoje. Pelo enunciado, desejamos encontrar o
menor valor de n que torna verdadeira a seguinte inequação:
n
364 n 1 364 1 1
1- >2~ - <=> n > log 364 - <=> n > 252,65...
365 365 2 365 2
203. (a) Para que a porta seja aberta na A:-ésima tentativa, todas as k — 1
tentativas anteriores devem ter sido frustradas, e somente a fc-ésima
deve ser bem-sucedida. A cada tentativa, há uma chave a menos no
molho. Assim, a probabilidade de errar a chave na primeira tenta
tiva é 2=1, uma vez que só uma das chaves é correta. Na segunda, a
probabilidade é igual a 2^2. Prosseguimos com este raciocínio até a
k — 1-ésima tentativa, cuja probabilidade de fracasso é H=|±l.
n—k+Z
Final-
mente, na fc-ésima tentativa, a probabilidade de acerto é ^4+t- L°g°’
a probabilidade desejada vale:
n—1 n—2 n—3 n—k+1 1 1.
n n—1 n—2 n—k+2 n—k+1 n
Uma outra resolução consiste em associar cada conjunto de k tenta
tivas de abertura da porta com uma fc-seqüência, de tal maneira que
sua i-ésima posição seja ocupada pela chave que se prestou à i-ésima
tentativa de abertura da porta. Ora, o total de seqüências de chaves,
nesse caso, é igual a n(n— l)(n —2) • • • (n —fc + 1), enquanto que o total
de seqüências que contêm a chave correta na fc-ésima posição é igual
a (n — l)(n — 2) • • • (n — k + 1) (número de casos favoráveis). Assim,
por outro caminho, reencontramos:
(n — l)(n — 2) • • • (n - k + 1) 1
n(n — l)(n — 2) • • • (n — k + 1) n
205. (a) Como a ordem de retirada das bolas importa, o total de seleções das n
bolas é igual a 9n. Para que o produtos dos números selecionados seja
divisível por 6, devemos retirar pelo menos um múltiplo de 2 e pelo
menos um múltiplo de 3. Definamos, pois, os seguintes conjuntos:
©O 54.600
© 3.268.760'
Parte II. Resoluções - Probabilidade 201
(ac?) 286.650
© 3.268.760
Como os eventos calculados nos itens acima são independentes, a pro
babilidade de que o apostador receba algum prêmio é igual à soma das
probabilidades encontradas, ou seja, 332681760 = biãsãO- Logo, a proba
bilidade de que o apostador não seja premiado é:
15.733 132.847
1-
148.580 “ 148.580’
valor aproximadamente oito vezes maior do que a probabilidade de
ganhar.
207. Quando o matemático constata que uma das caixas está vazia, para que
a outra caixa contenha k palitos, 2n — k devem ter sido por ele consumi
dos, e a 2n — k 4- 1-ésima seleção deve ser referente a uma caixa vazia.
Associando cada conjunto de escolhas de palitos com uma 2n — k 4- 1-
seqüência, devemos selecionar quais as n posições dentre as 2n — k iniciais
ocupadas pelos palitos da caixa vazia de (2n~fc) maneiras. Deste modo,
as posições dos palitos da caixa que contém k palitos também ficam de
terminadas. A probabilidade de que cada uma das posições da seqüência
seja respeitada é igual a | pois, a cada cigarro, a caixa da qual será re
tirado o palito para acendê-lo é escolhida aleatoriamente. Logo, como há
2n — k 4-1 posições e há duas possibilidades para a caixa a ser esvaziada, a
probabilidade requerida vale:
2
2n-k\ /i\2"-k+1 = (';V) (2n —- k)\
(2n
. " 1W ■2~n~k n\(n — fc)! • 22n-fc
208. (a) A probabilidade de resultar número par é igual à soma das probabili
dades de resultar 2, 4 ou 6, isto é:
1_p(4) = l-l = |.
3
^P=ü-
Dessa maneira, p(Ci) = PÍÇz} = H’ PÍ^3) = ÍT e P(^) = p(Cs) = Tr
(b) Neste item, denotaremos p(C{) a probabailidade do candidato Ci ga
nhar o segundo turno, tendo já ganho o primeiro. Caso apenas C\ e
C4 passem para o segundo turno da eleição, como suas chances de ga
nhar serão proporcionalmente mantidas, teremos que p(C() = %p(Cj),
donde:
Q 2
p(CÍ) + p(Cj) = 1 =s- -p(CÍ) + p(Cl) = 1 => p(&4) = -
[11] RIORDAN, J. Combinatorial identities. New Jersey: John Wiley &: Sons,
1968. 256 pp.
204 Problemas Resolvidos de Combinatória
[16] TUCKER, A. Applied Combinatorics. New York: John Wiley & Sons, 1980.
447 pp.
[18] WHITWORTH, W. A. Choice and chance. New York and London: Hafner
Publishing Company, 1965. 342 pp.
Anotações
•m sol 9,
rtíorp -llCo
em mente o livro
uai o primeiro
0(0' gTogfe
0
lemas aqui
788539 901685