Análise Combinatória e Probabilidade - Exercícios

Prévia do material em texto

Análise Combinatória, Probabilidade e Aplicações - Lista 4.
Ex 1 Dado um décagono, quantos são os triângulos cujos vértices são vértices não-
consecutivos do décagono?
Corresponde a escolha de 3 elementos não consecutivos de um conjunto de
10 elementos (vértices). Logo há,
g(10, 3) =
10
7
(
10− 3
3
)
Ex 2 (Generalização do segundo lema de Kaplansky) Seja Ω = {1, 2..., n}.
Quantos são os p-subconjuntos de Ω de modo que entre cada dois elementos esco-
lhidos para o subconjunto haja, no conjunto, pelo menos r elementos não escolhidos
para o subconjunto? Considere que os elementos 1 e n de Ω são "adjacentes".
Demonstração: Condicionando aos subconjuntos formados em relação aos
elementos 1, 2, ..., r pertencerem ou não a eles, temos as duas situações:
1. Os subconjuntos que não contêm nenhum desses elementos.
Há claramente então f(n− r, p, r), pois teremos que escolher p elementos não
consecutivos do conjunto {r + 1, r + 2, ..., n}.
2. Os subconjuntos que contêm um desses elementos.
Neste caso, qualquer um dos elementos considerados inicialmente; 1,2,... r,
estará a menos de r unidades do elemento escolhido. Seja então x ∈ {1, 2..., r} o
elemento escolhido. Há r possibilidades de escolhas; ademais, uma vez escolhido x,
teremos que escolher p−1 elementos de {1, 2, ..., n}\{x− r, ..., x + r}. Logo teremos
f(n− 2r − 1, p− 1, r).
O número de subconjuntos é portanto a soma das duas situações anteriores.
Logo há,
g(n, p, r) = f(n− r, p, r) + f(n− 2r − 1, p− 1, r) = n
n− pr
(
n− pr
p
)
Ex 3 Um bairro possui n ruas numeradas de 1 a n. Joãozinho tem uma namorada
em cada uma das ruas do bairro. De quantas maneiras é possível em um dia visitar
p de suas namoradas, sob a condição de que a casa de cada uma das p garotas visi-
tadas fique pelo menos r ruas distantes uma da outra?
a) Se as ruas 1 e n não são consideradas vizinhas.
Corresponde a uma aplicação do primeiro lema de Kaplansky. Assim há,
f(n, p, r) =
(
n− (p− 1)r
p
)
1
b) Se as ruas 1 e n são consideradas vizinhas.
É uma aplicação direta do segundo lema de Kaplansky, existem portanto,
g(n, p, r) =
n
n− pr
(
n− pr
p
)
Ex 4 Para cada inteiro positivo n, define-se ϕ(n) como sendo o número de inteiros
positivos que são primos com n e não superiores a n, isto é, que são primos com
n e menores ou iguais a n. Se a decomposição de n em fatores primos é da forma
n = pj11 p
j2
2 ...p
jr
r , em que p1, ..., pr são fatores primos distintos, mostre que:
a) ϕ(n) = n
(
1− 1
p1
)(
1− 1
p2
)
...
(
1− 1
pr
)
Demonstração: Sejam os conjuntos:
• Ω = Conjunto dos inteiros positivos menores ou iguais a n;
• Ai = Conjunto dos elementos de Ω que são múltiplos de pi (1 ≤ i ≤ r)
ϕ(n) é o número de elementos de Ω que não pertencem a nenhum dos con-
juntos Ai, 1 ≤ i ≤ r, pois do contrário, havendo um tal elemento x ∈ Ai, o
mdc(x, n) ≥ pi. Segue-se então que:
Ai = {pi, 2pi, ..., n} ⇒ |Ai| =
n
pi
Ai ∩ Aj = {pipj, 2pipj, ..., n} ⇒ |Ai ∩ Aj| =
n
pipj
Ai1Ai2 ...Aik = {pi1pi2 ...pik , 2pi1pi2 ...pik , ..., n} ⇒ |Ai1Ai2 ...Aik | =
n
pi1pi2 ...pik
∀ {i1, i2, ..., ik} ⊂ {1, ..., r}
Queremos então determinar o número de elementos de Ω que não pertencem
a nenhum dos Ai, ou seja:
ϕ(n) = (A1 ∪ ... ∪ Ar)c = |Ω| − | (A1 ∪ ... ∪ Ar) | = S0 −
(
S1 − S2 + ... + (−1)r−1Sr
)
⇒
ϕ(n) = S0 − S1 + S2 + ... + (−1)rSr (1)
Acontece que:
S0 = |Ω| = n, S1 =
r∑
i=1
n
pi
, S2 =
r∑
1≤i1<i2≤r
n
pi1pi2
, ..., Sr =
n
p1p2...pr
Logo, de (1) segue-se imediatamente que:
ϕ(n) = n−
(
n
p1
+
n
p2
+ ... +
n
pr
)
+
(
n
p1p2
+ ... +
n
pr−1pr
)
+ ... + (−1)r n
p1p2...pr
=
n
(
1− 1
p1
)(
1− 1
p2
)
...
(
1− 1
pr
)
2
b) Use o resultado do item anterior e calcule ϕ(120)
Da decomposição de 120 = 23 × 3 × 5 em fatores primos, resulta p1 = 2,
p2 = 3 e p3 = 5. Logo,
ϕ(120) = 120
(
1− 1
2
)(
1− 1
3
)(
1− 1
5
)
= 32
c) Se p é primo, quanto vale ϕ(p)?
Todos os inteiros de 1 a p− 1 são primos com p. Logo, ϕ(p) = p− 1.
Ex 5 Quantos são os elementos do conjunto {1, 2, ..., 500} que são divisíveis por
3 ou 5, mas não por 7?
Sejam os conjuntos:
1. A1 = {x ∈ N∗; 1 ≤ x ≤ 500 e 3|x}
2. A2 = {x ∈ N∗; 1 ≤ x ≤ 500 e 5|x}
3. A3 = {x ∈ N∗; 1 ≤ x ≤ 500 e 7|x}
4. A1 ∩ A2 = {x ∈ N∗; 1 ≤ x ≤ 500 e 15|x}
5. A1 ∩ A3 = {x ∈ N∗; 1 ≤ x ≤ 500 e 21|x}
6. A2 ∩ A3 = {x ∈ N∗; 1 ≤ x ≤ 500 e 35|x}
7. A1 ∩ A2 ∩ A3 = {x ∈ N∗; 1 ≤ x ≤ 500 e 105|x}
A partir disso, segue-se que:
|A1| = 166 |A2| = 100 |A3| = 71 |A1∩A2| = 33 |A1∩A3| = 23 |A2∩A3| = 14 |A1∩A2∩A3| = 4
O evento de interesse, os elementos que são divisíveis por 3 ou 5 e não são
por 7 é: (A1 ∪ A2)− A3. Segue-se então que:
| (A1 ∪ A2)− A3| = |A1 ∪ A2| − | (A1 ∪ A2) ∩ A3| = |A1 ∪ A2| − | (A1 ∩ A3) ∪ (A2 ∩ A3) | =
|A1|+ |A2| − |A1 ∩ A2| − |A1 ∩ A3| − |A2 ∩ A3|+ |A1 ∩ A2 ∩ A3| = 200
Ex 6 Prove que Dn = nDn−1 + (−1)n para n ≥ 2, em que Dn é o número de per-
mutações caóticas dos inteiros de 1 a n.
3
Temos que:
Dn = n!
[
n∑
k=0
(−1)k
k!
]
= n!
[
1
0!
− 1
1!
+
1
2!
+ ... +
(−1)n
n!
]
=
n!
[
n−1∑
k=0
(−1)k
k!
]
+ n!
(−1)n
n!
= n(n− 1)!
[
n−1∑
k=0
(−1)k
k!
]
+ (−1)n = nDn−1 + (−1)n
Ex 7 Prove que Dn é o inteiro mais próximo de
n!
e
Demonstração: para n = 1, é verdade, pois D1 = 0 é o inteiro mais próximo
de 1!
e
= 0, 3.... O mesmo acontece para n = 2, pois D2 = 1 e 2!e = 0, 7...
Seja agora n ∈ N : n ≥ 3. Da expansão de Mclaurin, segue-se que:
ex =
∞∑
i=0
xi
i!
=
1
0!
+
x
1!
+
x2
2!
+
x3
3!
+ ...
Para x = −1, segue-se que:
e−1 =
1
0!
− 1
1!
+
1
2!
− 1
3!
+ ...
A partir disso, segue-se imediatamente que:
|Dn −
n!
e
| = |n!
(
1
0!
− 1
1!
+ ... +
(−1)n
n!
)
− n!
(
1
0!
− 1
1!
+
1
2!
− 1
3!
+ ...
)
| =
n!|(−1)
n+1
(n + 1)!
+
(−1)n+2
(n + 2)!
+ ...| ≤ n!
(
1
(n + 1)!
+
1
(n + 2)!
+ ...
)
=
1
n + 1
+
1
(n + 1) (n + 2)
+
1
(n + 1) (n + 2) (n + 3)
+ ...
≤ 1
n + 1
+
1
(n + 1)2
+
1
(n + 1)3
+ ... =
1
n + 1
1− 1
n + 1
=
1
n
<
1
2
.
Logo, para n > 2, Dn é um inteiro situado a uma distância menor que 12 do
número n!
e
. Assim, Dn é o inteiro mais próximo de n!e .
Ex 8 (Ballot Theorem) Se b > 0, então o número de caminhos de (0, 0) a (n, b)
os quais não visita o eixo das abscissas é igual a
b
n
Nn (0, b). Sugestão: A primeira
posição visitada é necessariamente (1, 1).
Ex 9 Numa eleição há 30 votantes e dois candidatos A e B. Se não há votos nulos
e nem brancos, e o resultado final é de 10 votos a favor de A, quantas são as apu-
rações possíveis nas quais A permanece com no mínimo 2 votos de vantagem sobre B?
4
O total de maneiras em que a apuração pode configurar-se é
(
30
10
)
. Pois
considerando cada voto para o candidato A como um "passo"para cima (S) e cada
voto para o candidato B como um "passo"para baixo (D), temos:
S + D = 30 e S −D = 10 ⇒ S = 20 e D = 10
Os 3 primeiros votos "passos", tem que ser necessariamente para o candidato
A, feito isto, basta excluir do total de possíveis resultados de apurações, aquelas que
infringem à condição do problema. Pelo princípio da reflexão temos que N23,10 =
N−3,10, ou seja, o número de trajetórias que vão do ponto (3, 3) ao ponto (30, 10) e
que tocam a reta y = 2 é igual ao número de trajetórias que vão do ponto (3,−3)
ao ponto (30, 10). Logo há
(
27
20
)
de tais trajetórias, pois:
S + D = 27 e S −D = 13 ⇒ S = 20 e D = 7
Logo, o total de apurações possíveis em que o candidato A se mantém sempre
a frente do candidato B com no mínimo dois votos é:(
30
10
)
−
(
27
20
)
Ex 10 Qual é o número mínimo de pessoas que se deve haver em uma sala para que
possamos garantir que pelo menos duas delas sejam nascidas no mesmo mês?
Pelo princípio de Dirichlet ou Princípio da Cada dos Pombos, segue-se que o
número mínimo de pessoas é 13.
5