Prova Analise (2017.2) COM RESOLUCAO

Prévia do material em texto

Ana´lise Combinato´ria e Teoria dos Grafos
Resoluc¸a˜o da Prova I - 2017/2
1. Determine uma fo´rmula fechada que seja em func¸a˜o de n para a seguinte soma:
n∑
i=0
i2
Cin
5i
→
n∑
i=0
i2
Cin
5i
→
n∑
i=0
i2Cinx
i x = 5−1
→
n∑
i=0
i.i
n(n− 1)!
i(i− 1)!(n− k)!x
i
→
n∑
i=0
i.nCi−1n−1x
i
→
n∑
i=0
((i− 1) + 1).nCi−1n−1xi
→
n∑
i=0
(i− 1).nCi−1n−1xi +
n∑
i=0
nCi−1n−1x
i
→
n∑
i=0
n(i− 1) (n− 1)(n− 2)!
(i− 1)(i− 2)!(n− k)!x
i +
n∑
i=0
nCi−1n−1x
i
→
n∑
i=0
n(n− 1)Ci−2n−2xi +
n∑
i=0
nCi−1n−1x
i
→ n(n− 1)x2
n∑
i=0
Ci−2n−2x
i−2 + nx
n∑
i=0
Ci−1n−1x
i−1
→ n(n− 1)x2(1 + x)n−2 + nx(1 + x)n−1
n(n− 1)5−2(1 + 5−1)n−2 + n5−1(1 + 5−1)n−1
2. Realizadas todas permutac¸o˜es simples com os algarismos 0, 3, 4, 6 e 7 e colocados os nu´meros assim
obtidos em ordem decrescente, qual e´ a posic¸a˜o do nu´mero 36.047?
→ Ha´ 2 formas de solucionarmos esse problema
1) Podemos contar do maior valor (76.430), somando todas as permutac¸o˜es desses algarismos, ate´ o valor
que queremos. Se seguirmos esse racioc´ınio dividiremos o nosso problema nos seguintes casos:
I) Nu´meros em que o primeiro algarismo e´ maior que 3:
3× 4! =

7 = 4!
6 = 4!
4 = 4!
II) Nu´meros em que o primeiro algarismo e´ 3 e o segundo e´ maior que 6:
3! =
{
3 7 = 3!
III) Nu´meros em que o primeiro algarismo e´ 3, o segundo e´ 6 e o terceiro e´ maior que 0:
2× 2! =
{
3 6 7 = 2!
3 6 4 = 2!
IV) Nu´meros em que o primeiro algarismo e´ 3, o segundo e´ 6, o terceiro e´ 0 e o quarto e´ maior que
4:
1! =
{
3 6 0 7 = 1!
V) Nu´meros em que o primeiro algarismo e´ 3, o segundo e´ 6, o terceiro e´ 0, o quarto e´ 4 e o quinto
e´ maior que 7:
0!
1
Com isso basta somarmos todos os valores de cada um dos casos para obter a posic¸a˜o de tal nu´mero:
3× 4! + 3! + 2× 2! + 1! + 0! = 84
2) Podemos calcular todas as possibilidades (5!) e subtrair delas as posic¸o˜es seguintes ao valor que pro-
curamos. Esses valores podem ser contabilizados com os seguintes casos:
I) Nu´meros em que o primeiro algarismo e´ ≤ 3:
2× 4! =
{
0 = 4!
3 = 4!
II) Nu´meros em que o primeiro algarismo e´ 3 e o segundo e´ ≥ 6:
2× 3! =
{
3 6 = 3!
3 7 = 3!
III) Nu´meros em que o primeiro algarismo e´ 3, o segundo e´ 6 e o terceiro e´ ≤ 0:
2! =
{
3 6 0 = 2!
IV) Nu´meros em que o primeiro algarismo e´ 3, o segundo e´ 6, o terceiro e´ 0 e o quarto e´ ≥ 4:
2× 1! =
{
3 6 0 4 = 1!
3 6 0 7 = 1!
Agora devemos tomar bastante cuidado porque, a partir do momento que subtra´ımos o caso (I), na˜o
podemos subtrair o caso (II) porque estaremos perdendo posic¸o˜es que devem ser contabilizadas, logo
somamos. Igualmente na˜o podemos somar novamente o caso (III) e assim por diante nos fornecendo:
5!− 2× 4! + 2× 3!− 2! + 2× 1! = 84
3. Cada pessoa de um grupo de cinco pessoas recebeu um dado contendo faces numeradas de 10 a 100; e
esta˜o interessados em saber de quantas maneiras eles podem jogar estes dados, cada um jogando o seu, e
obter a soma dos resultados igual a 270. O uso de func¸o˜es geradoras para resolver o problema e´ obrigato´rio.
• Segundo o enunciado devemos obter valores dentro do intervalo [10, 100] onde n = 5 do qual representa
a quantidade de pessoas que ira˜o lanc¸ar o seu dado onde a soma dos valores dos lanc¸amentos e´ 270, logo
devemos encontrar o coeficiente de [x270]. Com isso temos a func¸a˜o geradora (x10 +x11 +x11 + . . .+x100)5
da qual podemos manipula´-la da seguinte forma:
→ (x10 + x11 + x11 + . . . + x100)5
→ x50(1 + x2 + x3 + . . . + x90)5
→ x50
(
1− x91
1− x
)5
→ x50(1− x91)5(1− x)−5
Agora basta encontrarmos o coeficiente de [x270]:
[x270]x50(1− x91)5(1− x)−5
[x220](1− x91)5(1− x)−5
(
5
0
)(−5
220
)
+ (−1)×
(
5
1
)(−5
129
)
+
(
5
2
)(−5
38
)
(
5
0
)(
224
220
)
+ (−1)×
(
5
1
)(
133
129
)
+
(
5
2
)(
42
38
)
(
224
220
)
− 5×
(
133
129
)
+ 10×
(
42
38
)
ou
(
224
4
)
− 5×
(
133
4
)
+ 10×
(
42
4
)
2
4. De quantas maneiras podemos acomodar 15 pessoas em 5 quartos sem que nenhum quarto fique vazio?
Primeiramente percebemos que nenhum dos quartos deve ficar vazio, logo podemos colocar no ma´ximo 11
pessoas em um quarto. Como o problema esta´ utilizando pessoas distintas, utilizamos func¸o˜es geradoras
exponenciais para resolve-lo. Dado que temos n = 5 quartos dos quais podem armazenar no mı´nimo 1 e
no ma´ximo 11 pessoas e queremos saber quantas formas temos de permutar 15, obtemos a func¸a˜o geradora:
→
[
x15
15!
](
x +
x2
2!
+
x3
3!
+
x4
4!
+ . . . + +
x11
11!
)5
Podemos simplificar tal func¸a˜o pelo Nu´mero de Euler do qual nos dara´ o mesmo coeficiente:
→
[
x15
15!
](
x +
x2
2!
+
x3
3!
+
x4
4!
+ . . . +
x11
11!
+ . . .
)5
=
[
x15
15!
]
(ex − 1)5
Com isso basta calcularmos esse binoˆmio e retirarmos o coeficiente de cada um dos Nu´meros de Euler
gerados:
→
[
x15
15!
]
(ex − 1)5 =
[
x15
15!
]
(e5x − 5e4x + 10e3x − 10e2x + 5e1x − 1)
515 − 5× 415 + 10× 315 − 10× 215 + 5
5. De quantos modos podemos pintar um cubo usando 8 cores diferentes de forma que suas faces tenham
cores distintas entre si?
Comec¸amos primeiramente escolhendo uma das 8 cores que temos para pintar o cubo (6 faces), com
isso obtemos facilmente:
C68
Pore´m devemos permutar todas estas cores entre as faces do cubo obtendo agora:
6!× C68
Ate´ enta˜o parece estar tudo certo, pore´m vamos analisar melhor o problema: Suponhamos que essas 8
cores que possu´ımos sejam denotadas pelas letras A,B,C,D,E, F,G,H e as faces do cubo por espac¸os
em branco. Com isso uma poss´ıvel maneira de pintar esse cubo seria:
A - B - C - D - E - F
onde:
frente - costas - esquerda - direita - cima - baixo
Assim obtendo o seguinte cubo:
A
B
C D
E
F
A - B - C - D - E - F
Sendo assim se fixarmos a face frontal com a cor A e girarmos 4 vezes o cubo obteremos o mesmo cubo
original mostrando que esta´ sendo contado 4 permutac¸o˜es va´lidas de um mesmo cubo:
A
B
E F
D
C
A
B
D C
F
E
A
B
F E
C
D
A
B
C D
E
F
A - B - E - F - D - C A - B - D - C - F - E A - B - F - E - C - D A - B - C - D - E - F
3
Logo, como temos 6 faces para fixar, devemos retirar as 4 rotac¸o˜es de cada uma delas do nosso resultado
gerando:
6!× C68
6× 4 =
6× 5× 4!× C68
4!
= 30× C68 = 840
4