3º Atividade Da Disciplina Matemática Discreta

Prévia do material em texto

3º Atividade Da Disciplina Matemática Discreta (2021.2-T01). 
ALUNA: Adriana Tavares da Costa. 
 
Problema 1. 
Em uma lanchonete, o lanche principal é composto por dois tipos de carnes, 
dentre eles carne de hambúrguer, filé na chapa, calabresa e bacon, uma folha verde 
(alface e rúcula), um de tipo de queijo (cheddar, mussarela, prato ou gouda), uma 
escolha de molho (picante, especial ou maionese), com ou sem cebola, e uma verdura 
(picles, tomate ou cenoura), tudo isso servido em um pão com gergelim. 
a) De quantas maneiras um cliente pode pedir seu lanche, considerando que 
cliente faz o pedido e a ordem de montagem dos ingredientes é padrão (não 
importa!). 
 
b) A lanchonete criou uma promoção para o dia dos namorados: pague um e leve 
dois! De quantas maneiras um casal pode tomar seu lanche, sabendo que a 
moça odeia cebola? (Considere ainda que a ordem da montagem é padrão) 
 
c) Suponha que o cliente peça o seu lanche com dois hambúrgueres, alface, queijo 
cheddar, molho especial, cebola, picles tudo isso em um pão com gergelim. 
Supondo agora que a ordem dos ingredientes importa (considere a ordem de 
baixo para cima), de quantas maneiras um cliente pode pedir seu lanche? 
 
d) A ordem de montagem dos lanches não é mais padrão. De quantas maneiras 
um cliente pode pedir um lanche nesta lanchonete? 
 
Solução: 
a. Carne temos 4 tipos 
Folha verde 2 tipos 
Queijo 4 tipos 
Molho 3 tipos 
Com ou sem cebolas 
Verduras 3 tipos 
 Como o lance é composto por dois tipos de carne, uma folha verde, um 
de tipo de queijo, uma escolha de molho, com ou sem cebola, e uma verdura 
tudo isso servido em um pão com gergelim. Temos que o número de 
possibilidade (𝑁𝑝) é 
𝑁𝑝 = 4 ∗ 3 ∗ 2 ∗ 4 ∗ 3 ∗ 2 ∗ 3 = 1728. 
 
b. Como ela odeia cebola temos que o número de possibilidade para o lanche dela 
será 
𝑁𝑝 = 4 ∗ 3 ∗ 2 ∗ 4 ∗ 3 ∗ 3 = 864 
Assim o número de possibilidade para o casal tomar seu lanche é 
𝑁𝑃 = 1728 ∗ 864 = 1492992. 
 
c. Para isso tomemos 𝑁𝑝 considerando que se tomarmos as suas carne de 
hambúrguer juntas se trocarmos ela da ordem álter a maneira com que foi 
realizada a montagem, assim 
𝑁𝑝𝑜 = 8! = 40320 
Agora calcularemos o número de possibilidade que amenas alternaram-se apenas 
a posição das duas carnes de hamburguês juntas 
𝑁𝑝𝑐 = 6! ∗ 7 
Assim o número de possibilidade da montagem é 
𝑁𝑃.𝑀 = 8! − 6! ∗ 7 = 35280 
d. Termos 
𝑁𝑃 = 8! ∗ 1728 = 69672960 
 
Problema 2. 
a) Quantas sequências binárias formadas pelos algarismos 0 e 1 de comprimento 𝑛 
existem? 
b) Quantas são as sequências binárias formadas pelos algarismos 0 e 1 existem tais 
que seu comprimento é n e o número de algarismos 0 nas mesmas é k (𝑛 ≥ 𝑘)? 
c) Quantas são as sequências ternárias formadas pelos algarismos 0, 1 e 2 existem 
tais que seu comprimento é n e o número de algarismos 0 nas mesmas é k (𝑛 ≥ 
𝑘)? 
d) Generalize esta ideia para sequências ternárias, onde o número de 0's é k e o 
número de 1's é l, onde 𝑙 + 𝑘 ≤ 𝑛. 
 
Solução: 
 
a. Para isso tomaremos 𝑆𝑛 = {𝑎1, 𝑎2, … , 𝑎𝑛−1, 𝑎_𝑛} como sendo de 
comprimento 𝑛, onde para cada 𝑎𝑘𝑐𝑜𝑚 𝑣𝑎𝑟𝑖𝑎𝑛𝑑𝑜 𝑘 = 1,2, … , 𝑛 e para cada 
𝑎𝑘 podemos alternar na escola de seu representante ente 0 e 1, assim termos 
que o número de possíveis sequência 𝑁𝑆𝑛 é 
𝑁𝑆𝑛 = 2
𝑛 
 
b. As sequências binárias tais que seu comprimento é n e o número de 
algarismos 0 nas mesmas é k (𝑛 ≥ 𝑘) é 
𝑁𝑆𝑛 = 2
𝑛−𝑘 
Como 𝑘 ≤ 𝑛 temos que 𝑛 − 𝑘 > 0 logo 2𝑛−𝑘 𝜖 ℤ. 
 
c. Será 
𝑁𝑆𝑛 = 3
𝑛−𝑘 
 
 
d. Generalizando teremos 
𝑁𝑆𝑛 = 3
𝑛−𝑘−𝑙 
 
 
 
Problema 3. 
a) Demonstre com argumentos combinatórios a identidade a seguir, conhecida 
como identidade de Chu–Vandermonde. 
 Para 𝑚 𝑒 𝑛 inteiros positivos, 
 𝐶(𝑚 + 𝑛, 𝑟) = ∑ 𝐶(𝑚, 𝑟 − 𝑘)𝐶(𝑛, 𝑘) 
𝑛
𝑘=0
 
 
b) Conclua que 
𝐶(2𝑛, 𝑛) = ∑ 𝐶(𝑛, 𝑘)2
𝑛
𝑘=0
 
 Solução: 
a. Dado o conjunto 𝐶 = {𝑐1, 𝑐2, … , 𝑐𝑛, 𝑐𝑛+1, … , 𝑐𝑛+𝑚} , considerem-se dois 
subconjuntos de 𝐶𝑗 𝑗⁄ = 1,2 disjuntos, isto é, sem elementos comuns, um 𝐶1 =
{𝑐1, 𝑐2, … , 𝑐𝑛} com 𝑛 elementos e outro com 𝑚 ,𝐶2 = {𝑐𝑛+1, 𝑐𝑛+2, … , 𝑐𝑛+𝑚}, 
tais que 𝐶 = 𝐶1 ∪ 𝐶2 
O segundo membro conta o número de maneiras distintas de 
escolher 𝑟 elementos de entre os 𝑛 + 𝑚 de 𝐶. 
Quanto ao primeiro membro, comecemos por reparar que 
há 𝐶(𝑛, 𝑗)maneiras distintas de escolher 𝑗 elementos entre os 𝑛 de 𝐶1; 
há 𝐶(𝑚, 𝑟 − 𝑗) maneiras distintas de escolher 𝑟 − 𝑗 elementos entre 
os 𝑚 de 𝐶2; 
pelo que há 𝐶(𝑛, 𝑗)𝐶(𝑚, 𝑟 − 𝑗) maneiras distintas de selecionar 𝑗 elementos 
de 𝐶1 e simultaneamente 𝑗 − 𝑟 de 𝐶2. 
Ora, se somarmos todas estas parcelas 𝐶(𝑛, 𝑗)𝐶(𝑚, 𝑟 − 𝑗) para os possíveis 
valores que 𝑗 pode tomar, desde 𝑗 = 0 até 𝑗 = 𝑛, obtemos evidentemente o 
mesmo número 𝐶(𝑛 + 𝑚, 𝑟). Como mostrámos a igualdade dos dois membros 
da identidade de Vandermonde, concluímos a justificação. 
 
b. Comecemos por reparar que poderíamos ter escolhido para limite inferior do 
somatório 0 , em vez de 𝑘, porque para 𝑖 < 𝑘, 𝐶(𝑖, 𝑘) = 0, por convenção 
usual. 
O segundo membro (lado direito) conta o número de maneiras diferentes de 
escolher 𝑛 elementos dum conjunto, tal como 𝑆 =
{𝑠1, … , 𝑠𝑛} com 𝑛 elementos e, ao mesmo tempo, 𝑛 elementos doutro conjunto, 
por exemplo 𝑋 = {𝑥1, 𝑥2, … , 𝑥𝑛, … , 𝑥2𝑛+𝑘} com 2𝑛 + 𝑘 elementos. 
Quanto ao primeiro membro, considerem-se dois subconjuntos de 𝑋 disjuntos 
(sem elementos comuns),um 𝑋1 = {𝑥1, 𝑥2, … , 𝑥𝑛} com 𝑛 elementos, e 
outro 𝑋2 = {𝑥𝑛+1, … , 𝑥2𝑛+𝑘} com 2𝑛 + 𝑘 elementos, tais que 𝑋 = 𝑋1 ∪ 𝑋2 
Escolhamos agora 𝑛 elementos de 𝑋 pertencendo 𝑖 deles a 𝑋1 e 𝑛 −
𝑖 a 𝑋2 com 0 ≤ 𝑖 ≤ 𝑛. 
i) Há 𝐶(𝑛, 𝑖) maneiras diferentes de escolher 𝑖 elementos entre 
os 𝑛 de 𝑋1; 
ii) há 𝐶(𝑛 − 𝑘, 𝑛 − 𝑖) = 𝐶(𝑛 − 𝑘, 𝑖 − 𝑘) maneiras diferentes de 
escolher 𝑛 − 𝑖 elementos entre os 𝑛 − 𝑘 de 𝑋2; 
iii) daqui decorre que, para um dado 𝑖, há 𝐶(𝑛, 𝑖)𝐶(𝑛 − 𝑘, 𝑖 −
𝑘) maneiras distintas de selecionar esses 𝑛 elementos de 𝑋. Assim, 
cada parcela, 𝐶(𝑛, 𝑖)𝐶(𝑛 − 𝑘, 𝑖 − 𝑘)𝐶(𝑛, 𝑐) conta o número de 
maneiras diferentes de escolher 𝑛 elementos de𝑋 (dos quais 𝑖 ∈ 𝑋1 ) e, 
simultaneamente, 𝑘 de 𝑆 Somando, para todos os possíveis valores 
de , estas parcelas, obtemos o número total 
 
A primeira igualdade é justificada por 
𝐶(𝑛, 𝑘)𝐶(𝑛 − 𝑘, 𝑖 − 𝑘) = 𝐶(𝑛, 𝑖)𝐶(𝑖, 𝑘) 
e a segunda pela observação inicial. 
É claro que as duas contagens, a direta representada pelo produto do segundo 
membro e a indireta, pela soma do primeiro (lado esquerdo) hão de ser iguais, 
o que mostra 
𝐶(2𝑛, 𝑛) = ∑ 𝐶(𝑛, 𝑘)2𝑛𝑘=0 , como pretendíamos. 
 
 
 (1.2) Problema 4. 
 Mostre que 𝑛𝐶(𝑛, 𝑘) = (𝑘 + 1)𝐶(𝑛, 𝑘 + 1) + 𝑘𝐶(𝑛, 𝑘). 
 Solução: 
 Primeiro vamos calcular que é(𝑘 + 1)𝐶(𝑛, 𝑘 + 1) 
(𝑘 + 1)𝐶(𝑛, 𝑘 + 1) =
(𝑘 + 1)𝑛!
(𝑘 + 1)! (𝑛 − 𝑘 + 1)!
=
𝑛! (𝑛 − 𝑘)
𝑘! (𝑛 − 𝑘)!
 
E agora vamos calcular 𝑘𝐶(𝑛𝑛, 𝑘) 
𝑘𝐶(𝑛𝑛, 𝑘) = 𝑘
𝑛!
𝑘! (𝑛 − 𝑘)!
 
 Logo: (𝑘 + 1)𝐶(𝑛, 𝑘 + 1) + 𝑘𝐶(𝑛, 𝑘) =
𝑛!(𝑛−𝑘)
𝑘!(𝑛−𝑘)!
+ 𝑘
𝑛!
𝑘!(𝑛−𝑘)!
=
𝑛!
𝑘!(𝑛−𝑘)!
((𝑛 − 𝑘) + 𝑘) =
𝑛!
𝑘!(𝑛−𝑘)!
𝑛 = 𝑛𝐶(𝑛, 𝑘) 
 
Problema 5. 
Quantos subespaços existem de um espaço vetorial 𝑉 de dimensão 𝑛? 
Solução: 
.......? 
 
(1.3.6) Problema 6. 
a) Quantos são os anagramas da palavra MATEMATICAMENTE? 
b) Dentre os anagramas da palavra MATEMATICAMENTE quantos deles 
possui todos os A’s agrupados? 
 
Solução: 
a. Temos 15 letras, se todas fossem diferentes, a quantidade de anagramas 
seria igual a 15!. Mas não é tão simples assim pois temos algumas 
repetições: 
 A letra A aparece 3 vezes 
 A letra M aparece 3 vezes 
 A letra T aparece 3 vezes 
 A letra E aparece 3 vezes 
Devemos descontar as repetições para que a contagem dos anagramas 
seja feita da forma correta. Para que isto seja feito,vamos dividir o 15! 
pelo fatorial de cada uma das repetições. Veja: 
15!
3!4
= 1009008000 
b. Teremos 
13 ∗
(15 − 3)!
3!3
= 28828800 
 
Problema 7. 
Considere a seguinte situação. Suponha que há 12 pessoas sentadas em uma 
mesa horizontal. A cada 10 minutos um garçom coloca mais uma cadeira em um espaço 
vazio logo a direita das pessoas. A cada intervalo de 10 minutos o garçom conta de 
quantas maneiras as 12 pessoas podem se sentar à mesa. 
Ao final de duas horas o garçom revela o número de maneiras que estas pessoas 
poderiam se sentar à mesa. Qual é esse número? 
Solução: 
 E fácil nota que ao fim das duas horas a mesa estará com 24 cadeiras a 
disposição das 12 pessoas, assim o número de possibilidades são 
 12! ∗ 12 = 5748019200 
Problema 8. 
Quantas são as soluções de 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 27, onde 𝑥1, 𝑥2 ≥
 0 e 𝑥3, 𝑥4 ≥ 1 e 𝑥5 ≥ 2. 
Solução: 
Podemos fazer as seguintes substituições de variáveis sem alterar as soluções: 
𝑥1 = 𝑎1 , 𝑥2 = 𝑎2 , 𝑥3 = 𝑎3 + 1, 𝑥4 = 𝑎4 + 1, 𝑥5 = 𝑎5 + 2. E a equação fica: 
𝑎1 + 𝑎2 + 𝑎3 + 1 + 𝑎4 + 1 + 𝑎5 + 2 = 27 
→ 𝑎1 + 𝑎2 + 𝑎3 + 𝑎4 + 𝑎5 = 23, 
As soluções agora são inteiras positivas incluindo o zero. 
Assim temos que o número de solução será 
27!
4! 23!
= 17550 
 
 
 
Problema 9. 
 Em um restaurante trabalham quatro garçons. Cada gorjeta que um garçom 
recebe deposita em uma caixinha. Certo dia os garçons abriram a caixinha e 
encontraram R$150,00 em notas de R$2,00. De quantos modos possíveis o montante de 
gorjetas pode ter sido constituído? 
Solução: Para calcular iremos utilizar a seguinte formula 
𝐶(𝑘 − 1, 𝑛 − 1) =
(𝑘 − 1)!
(𝑘 − 1 − 𝑛 + 1)! (𝑛 − 1)!
 
Onde 𝑘 = 75 𝑒 𝑛 = 4 
𝐶(75 − 1, 4 − 1) = 𝐶(74,3) =
74!
(71)! (3)!
= 64824 
 Assim o número de possibilidade é 64824. 
 
Problema 10. 
Encontre o coeficiente de √8𝑎4 na expansão de (𝑎 + √2)
7
 . 
Solução: 
Para resolvermos esse exercício utilizaremos a Proposição 2, que diz o seguinte: 
Para 𝑎, 𝑏 ∈ ℝ, 𝑒 𝑛 ∈ ℕ, 
(𝑎 + 𝑏)𝑛 = ∑ 𝐶(𝑛, 𝑖)𝑎𝑖𝑏𝑛−𝑖
𝑛
𝑖=0
 
O que implica que 
(𝑎 + √2)
7
 = ∑ 𝐶(7, 𝑖)𝑎𝑖𝑏7−𝑖
7
𝑖=0
 
 
 o coeficiente de √8𝑎4 = √23𝑎4 = 2√2𝑎4, pode ser calculado da seguinte 
forma 
 
𝐶(7, 4) =
7!
(7 − 4)! (4)!
= 35 
 
Problema 11. 
De acordo com o Novo Testamento da Bíblia, na santa ceia, Jesus Cristo se 
sentou em uma mesa com os seus doze discípulos. Suponha que a mesa era redonda, e 
que cada modo de se sentar é considerado distinto se cada pessoa que está ao lado é 
distinta, ou seja, simples rotações de todos os integrantes não configuram uma maneira 
diferente de se sentar. 
a) De quantas maneiras Jesus e os apóstolos podem ter se sentado na santa ceia? 
b) De quantas maneiras eles podem ter se sentado à mesa de maneira que Jesus e Judas 
estejam sempre em polos opostos. 
Solução: 
a. Para resolver esta questão utilizaremos a Proposição 6, que diz o seguinte: 
O número de permutações circulares de 𝑛 elementos, 𝑃𝐶(𝑛) é dado por 
𝑃𝐶(𝑛) = (𝑛 − 1)! 
 Assim, 
𝑃𝐶(12) = (12 − 1)! = 11! = 39916800 
 
b. Para que jesus e judas esteja em lados oposto necessitaremos fixar os dois e 
calcular a possibilidade 
Então ficaremos com 
𝑃𝐶2(12) = (12 − 2)! = 3628800 
 
Problema 12. 
Prove o Lema 2 de 1.3.8. 
𝐶(𝑛 + 1, 𝑘)𝐶(𝑘, 𝑗) = 𝐶(𝑛 + 1 − 𝑗, 𝑘 − 𝑗)𝐶(𝑛 + 1, 𝑗), para quaisquer 𝑛, 𝑗 𝑒 𝑘 
naturais. 
 Solução: 
𝐶(𝑛 + 1 − 𝑗, 𝑘 − 𝑗)𝐶(𝑛 + 1, 𝑗) 
=
(𝑛 + 1 − 𝑗)!
(𝑛 + 1 − 𝑗 − 𝑘 + 𝑗)! (𝑘 − 𝑗)!
∗
(𝑛 + 1)!
(𝑛 + 1 − 𝑗)! (𝑗)!
 
=
1
(𝑛 + 1 − 𝑘)! (𝑘 − 𝑗)!
∗
(𝑛 + 1)!
(𝑗)!
 
=
𝑘!
𝑘!
∗
1
(𝑛 + 1 − 𝑘)! (𝑘 − 𝑗)!
∗
(𝑛 + 1)!
(𝑗)!
 
=
𝑘! (𝑛 + 1)!
(𝑛 + 1 − 𝑘)! (𝑘 − 𝑗)! 𝑘! 𝑗!
 
 
=
(𝑛 + 1)!
(𝑛 + 1 − 𝑘)! 𝑘!
∗
𝑘!
(𝑘 − 𝑗)! 𝑗!
= 𝐶(𝑛 + 1, 𝑘)𝐶(𝑘, 𝑗) 
 
Problema 13. 
Prove o Lema 1 de 1.3.8. Sejam 𝑖, 𝑗 ∈ ℤ, com 𝑖 ≥ 𝑗 + 1 e 𝑗 ≥ 0, então 
∑(−1)ℎ𝐶(𝑖, ℎ) = (−1)𝑗𝐶(𝑖 − 1, 𝑗)
𝑗
ℎ=0
 
Solução: 
...........? 
 
Problema 14. 
Mostre, utilizando argumentos combinatórios que 𝑃(𝑛, 𝑘) = 𝑛𝑃(𝑛 − 1, 𝑘 −
 1), para 𝑛, 𝑘 inteiros positivos. 
Solução: 
...........? 
 
Problema 16. 
 Prove que se (𝛥𝑎𝑛) é um polinômio de grau 𝑘 mostre que o termo geral 𝑎𝑛 é 
um polinômio de grau 𝑘 + 1 sobre a variável 𝑛. 
Solução: 
...........? 
 
Problema 17. 
Encontre o valor das somas. 
a) ∑ 2𝑗4 + 2𝑗 + 1999𝑗=0 
b) ∑ 𝑗(𝜋𝑗 + 1)999𝑗=0 
Solução: 
...........? 
 
Problema 19. 
a) Há dezenove jogadores de vôlei em um time. O técnico deseja dividir estes 
jogadores em dois(três)? times, um com sete (um é reserva) e outros dois com seis 
jogadores. De quantas maneiras ele pode fazer isto? 
b) Suponha o treinador agora descobre que dentre os dezenove jogadores há três 
líberos. Sabendo que em um time só pode jogar um líbero, de quantas maneiras o 
técnico pode dividir as três equipes? 
Solução: 
...........? 
 
Problema 20. 
Encontre o número de permutações de 𝐴10 = {𝑎1, 𝑎2, … , 𝑎10} ⊂ {0,1,2 … ,9} 
em que a) 𝑎1 < 𝑎2 b) 𝑎1 < 𝑎2 e 𝑎4 < 𝑎5. 
Solução: 
...........? 
 
Problema 21. 
 Mostre que 𝑛𝐶(𝑛, 𝑘) = (𝑘 + 1)𝐶(𝑛, 𝑘 + 1) + 𝑘𝐶(𝑛, 𝑘). 
Solução: 
 Primeiro vamos calcular que é(𝑘 + 1)𝐶(𝑛, 𝑘 + 1) 
(𝑘 + 1)𝐶(𝑛, 𝑘 + 1) =
(𝑘 + 1)𝑛!
(𝑘 + 1)! (𝑛 − 𝑘 + 1)!
=
𝑛! (𝑛 − 𝑘)
𝑘! (𝑛 − 𝑘)!
 
E agora vamos calcular 𝑘𝐶(𝑛𝑛, 𝑘) 
𝑘𝐶(𝑛𝑛, 𝑘) = 𝑘
𝑛!
𝑘! (𝑛 − 𝑘)!
 
 Logo: (𝑘 + 1)𝐶(𝑛, 𝑘 + 1) + 𝑘𝐶(𝑛, 𝑘) =
𝑛!(𝑛−𝑘)
𝑘!(𝑛−𝑘)!
+ 𝑘
𝑛!
𝑘!(𝑛−𝑘)!
=
𝑛!
𝑘!(𝑛−𝑘)!
((𝑛 − 𝑘) + 𝑘) =
𝑛!
𝑘!(𝑛−𝑘)!
𝑛 = 𝑛𝐶(𝑛, 𝑘) 
 
Problema 22. 
 Prove que o número de monômios em 𝑛 variáveis de grau 𝑘 é igual a 𝐶(𝑛 + 𝑘, 
𝑘). 
Solução: 
...........? 
 
Problema 23. 
 Prove que o número de permutações de (𝑎1, 𝑎2, … , 𝑎2𝑛 ) com 𝑛 zeros e 𝑛 uns, 
entre os primeiros k elementos dos quais existem pelo menos tantos zeros quanto uns, 
para cada 𝑘 = 1,2, . . . , 2𝑛 é igual a 𝐶𝑛+1 = 𝐶(2𝑛,𝑛) 𝑛+1 . Dica: Considere os conjuntos 
de caminhos reticulados A: que saem da origem e atingem (𝑛, 𝑛) e B: que também 
partem da origem e chegam a (𝑛, 𝑛), porém que não cruzam a reta 𝑦 = 𝑥 + 1. Utilize a 
fórmula de reflexão de André para encontrar 𝐶𝑛+1. 
Solução: 
...........? 
 
Problema 24. 
 Encontre o número de elementos no conjunto 𝑋 = {2,3,4, … ,700} que não são 
múltiplos de 2, ou 3, ou 7 ou 9. 
Solução: 
Primeiramente vamos tomar os conjuntos 
𝑋2 = {𝑥 ∈ 𝑋 𝑥⁄ = 2𝑛 𝑐𝑜𝑚 𝑛 = 1,2, … ,350} 
𝑋3 = {𝑥 ∈ 𝑋 𝑥⁄ = 3𝑛 𝑐𝑜𝑚 𝑛 = 1,2, … ,233} 
𝑋7 = {𝑥 ∈ 𝑋 𝑥⁄ = 7𝑛 𝑐𝑜𝑚 𝑛 = 1,2, … ,100} 
𝑋9 = {𝑥 ∈ 𝑋 𝑥⁄ = 9𝑛 𝑐𝑜𝑚 𝑛 = 1,2, … ,77} 
Considere 𝑋2 = {𝑥 ∈ 𝑋 𝑥⁄ = 2𝑛 𝑐𝑜𝑚 𝑛 = 1,2, … ,350}, 𝑋3 = {𝑥 ∈ 𝑋 𝑥⁄ =
3𝑛 𝑐𝑜𝑚 𝑛 = 1,2, … ,233}, 𝑋7 = {𝑥 ∈ 𝑋 𝑥⁄ = 7𝑛 𝑐𝑜𝑚 𝑛 = 1,2, … ,100} e 𝑋9 =
{𝑥 ∈ 𝑋 𝑥⁄ = 9𝑛 𝑐𝑜𝑚 𝑛 = 1,2, … ,77}. Desejamos 𝑁(𝑋2̅̅ ̅ ∩ 𝑋3̅̅ ̅ ∩ 𝑋7̅̅ ̅ ∩ 𝑋9̅̅ ̅) que 
sabemos que é igual a 
𝑁(𝑋2̅̅ ̅ ∩ 𝑋3̅̅ ̅ ∩ 𝑋7̅̅ ̅ ∩ 𝑋9̅̅ ̅) = 𝑁(𝑋) − 𝑁(𝑋2) − 𝑁(𝑋3) − 𝑁(𝑋7) − 𝑁(𝑋9) +
𝑁(𝑋2 ∩ 𝑋3) + 𝑁(𝑋2 ∩ 𝑋7) + 𝑁(𝑋2 ∩ 𝑋9) + 𝑁(𝑋3 ∩ 𝑋7) + 𝑁(𝑋3 ∩ 𝑋9) +
𝑁(𝑋7 ∩ 𝑋9) − 𝑁(𝑋2 ∩ 𝑋3 ∩ (𝑋7)) − 𝑁(𝑋2 ∩ 𝑋3 ∩ 𝑋9) − 𝑁(𝑋2 ∩ 𝑋7 ∩ 𝑋9) −
𝑁(𝑋3 ∩ 𝑋7 ∩ 𝑋9) + 𝑁(𝑋2 ∩ 𝑋3 ∩ 𝑋7 ∩ 𝑋9) 
Como 2, 3, 7, 9 são primos entre se exceto o 3 e 9 temos que 
(𝑋) = 699 
𝑁(𝑋2) = ⌊
700
2
⌋ = 350 
𝑁(𝑋3) = ⌊
700
3
⌋ = 233 
𝑁(𝑋7) = ⌊
700
7
⌋ = 100 
𝑁(𝑋9) = ⌊
700
9
⌋ = 77 
𝑁(𝑋2 ∩ 𝑋3) = ⌊
700
2 ∗ 3
⌋ = 116 
𝑁(𝑋2 ∩ 𝑋7) = ⌊
700
2 ∗ 7
⌋ = 50 
𝑁(𝑋2 ∩ 𝑋9) = ⌊
700
2 ∗ 9
⌋ = 38 
𝑁(𝑋3 ∩ 𝑋7) = ⌊
700
3 ∗ 7
⌋ = 33 
𝑁(𝑋7 ∩ 𝑋9) = ⌊
700
7 ∗ 9
⌋ = 11 
𝑁(𝑋2 ∩ 𝑋3 ∩ 𝑋7) = ⌊
700
2 ∗ 3 ∗ 7
⌋ = 16 
𝑁(𝑋2 ∩ 𝑋7 ∩ 𝑋9) = ⌊
700
2 ∗ 7 ∗ 9
⌋ = 5 
𝑁(𝑋3 ∩ 𝑋9) = 𝑁(𝑋9) = 77 
𝑁(𝑋2 ∩ 𝑋3 ∩ 𝑋9) = 𝑁(𝑋2 ∩ 𝑋9) = 38 
𝑁(𝑋3 ∩ 𝑋7 ∩ 𝑋9) = 𝑁(𝑋7 ∩ 𝑋9) = 11 
𝑁(𝑋2 ∩ 𝑋3 ∩ 𝑋7 ∩ 𝑋9) = 𝑁(𝑋2∩ 𝑋7 ∩ 𝑋9) = 5 
 
 Assim, 
𝑁(𝑋2̅̅ ̅ ∩ 𝑋3̅̅ ̅ ∩ 𝑋7̅̅ ̅ ∩ 𝑋9̅̅ ̅) = 699 − 350 − 233 − 100 − 77 + 116 + 50 + 38 + 33 +
11 + 77 − 16 − 5 − 38 − 11 + 5 = 199 
 Portanto nosso conjunto tem 199 elementos 
 
Problema 25. 
 Lembrando que dois inteiros positivos 𝑛 e 𝑚 são relativamente primos se o 
único divisor positivo comum deles é 1, a função phi de Euler, 𝜙 é tal que: 𝜙(k): = 
𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 𝑟𝑒𝑙𝑎𝑡𝑖𝑣𝑎𝑚𝑒𝑛𝑡𝑒 𝑝𝑟𝑖𝑚𝑜𝑠 𝑐𝑜𝑚 𝑘, 𝑝𝑎𝑟𝑎 𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑒𝑛𝑡𝑟𝑒 1 𝑒 
𝑘 − 1. Utilize o princípio da inclusãoexclusão para calcular 𝜙(50). 
Solução: 
 
 
 
Problema 26. 
Um desarranjo de ordem 𝑛 é uma permutação de 𝑛 elementos, onde na posição 𝑖 
o elemento 𝑎𝑖 não aparece, para 𝑖 = 1,2, … , 𝑛. Por exemplo (𝑎2, 𝑎4, 𝑎1, 𝑎3 ) é um 
desarranjo de ordem 4, enquanto (𝑎1, 𝑎4, 𝑎2, 𝑎3 ) não é. Mostre, utilizando o princípio 
da inclusão-exclusão, que o número de desarranjos de ordem 𝑛, 𝐷𝑛 é igual a 
 𝐷𝑛 = 𝑛! (1 −
1
1!
 +
1
2!
 −
1
3!
 + ⋯ +
(−1)𝑛
𝑛!
) 
Solução: 
i) Para 𝑛 = 1 teremos que 
 Note que não temos desarranjo possível, agora observe que 
0 = 1! (1 −
1
1!
) 
Logo para 𝑛 = 1 a formula vale 
Para 𝑛 = 2 teremos que 
Os desarranjos podem ser exibidos e assim podemos contra, exibidos 
termos: 
 Note que temos apenas um desarranjo possível que é (𝑎2, 𝑎1), agora 
observe que 
1 = 2! (1 −
1
1!
+
1
2!
) 
 
Logo para 𝑛 = 2 a formula vale 
ii) Agora vamos definir uma formula de recorrência 
Seja o número de permutações caóticas dos elementos (distintos) 
da sequência 𝑎1, 𝑎2, … , 𝑎𝑛+2. Podemos “separar” estas permutações em 
dois grupos: aquelas em que ocupa o lugar do elemento que está na 
primeira posição e aquelas em que isto não ocorre. 
As permutações caóticas do primeiro grupo são formadas do 
seguinte modo: primeiro, escolhe-se um elemento para trocar de posição 
com 𝑎1, o que pode ser feito de (𝑛 + 1) formas. Para cada uma delas, 
permutam-se os 𝑛 elementos restantes, de forma que nenhum deles fique 
em sua posição original. Isto pode ser feito de 𝐷𝑛 modos. Logo, o 
número de permutações do primeiro grupo é: (𝑛 + 1)𝐷𝑛. 
Para formar as permutações do segundo grupo, procedemos do 
seguinte modo: escolhemos um lugar da sequência para alocar o 
elemento 𝑎1 (lugar x), colocando, “provisoriamente”, o elemento deste 
local na primeira posição. Isto pode ser feito de (𝑛 + 1) formas. Para 
cada uma delas permutamos os (𝑛 + 1) elementos restantes de modo que 
nenhum fique na posição original e 𝑎𝑥 não fique na primeira posição. Isto 
pode ser feito de 𝐷𝑛+1 modos. Logo, o número de permutações do 
segundo grupo é: (𝑛 + 1)𝐷𝑛+1 
Portanto: 𝐷𝑛+2 = (𝑛 + 1)𝐷𝑛+1 + (𝑛 + 1)𝐷𝑛 
 Suponhamos, agora, que a afirmação seja válida ∀ 𝑘 ∈ Ν, com 
1 ≤ 𝑘 ≤ (𝑛 + 1) . Em particular, para 𝑘 = 𝑛 e 𝑘 = 𝑛 + 1, temos: 
 
𝐷𝑛 = 𝑛! ∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
 
e 
𝐷𝑛+1 = (𝑛 + 1)! ∑
(−1)𝑖
𝑖!
𝑛+1
𝑖=0
 
 Então, para (𝑛 + 2), temos 
𝐷𝑛+2 = (𝑛 + 1)(𝐷𝑛+1 + 𝐷𝑛) 
 Assim 
𝐷𝑛+2 = (𝑛 + 1) ( (𝑛 + 1)! ∑
(−1)𝑖
𝑖!
𝑛+1
𝑖=0
+ 𝑛! ∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
) 
= (𝑛 + 1)𝑛! ((𝑛 + 1) ∑
(−1)𝑖
𝑖!
𝑛+1
𝑖=0
+ ∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
) 
= (𝑛 + 1)! ((𝑛 + 1) (∑
(−1)𝑖
𝑖!
+
(−1)𝑛+1
(𝑛 + 1)!
𝑛
𝑖=0
) + ∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
) 
= (𝑛 + 1)(𝑛 + 1)! ∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
+ (𝑛 + 1)(−1)𝑛+1 + (𝑛 + 1)! ∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
 
= (𝑛 + 2)! (∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
) + (𝑛 + 2)(−1)𝑛+1 + (𝑛 + 2 − 1)(−1)𝑛+1 
= (𝑛 + 2)! (∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
+
(𝑛 + 2)(−1)𝑛+1
(𝑛 + 2)!
 +
(−1)(−1)𝑛+1
(𝑛 + 2)!
) 
= (𝑛 + 2)! (∑
(−1)𝑖
𝑖!
𝑛
𝑖=0
+
(−1)𝑛+1
(𝑛 + 1)!
 +
(−1)𝑛+2
(𝑛 + 2)!
) 
= (𝑛 + 2)! (∑
(−1)𝑖
𝑖!
𝑛+2
𝑖=0
) 
 O que mostra a formula para (𝑛 + 2).