Avaliações e Gabaritos-20180619

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Avaliações/CEDERJ-AD1-1-18.pdf
Curso de Tecnologia em Sistemas de Computação
Disciplina: Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
AD1 - Primeiro Semestre de 2018
Nome -
Assinatura -
Questões:
1. (1,0) Verifique se cada uma das seguintes afirmações é verdadeira ou
falsa. Se for verdadeira prove, se for falsa justifique.
(a) ∅ ∈ {{∅}}.
(b) {∅} ⊆ {{∅}}.
(c) A∪(B−C) = (A−B)∪(A−C). sendo A e B conjuntos quaisquer.
2. (1,5) Usando o Princípio de Inclusão e Exclusão, determine o número
de permutações de 1, 2, 3, 4, 5, 6, 7, 8) nas quais nem o 2 ocupa o 2o lugar
nem o 6 ocupa o 6o lugar.
3. (2,0) Mostre pelo Princípio da Indução Matemática que:
(a)
2.6.10.14 · · · (4n− 2) =
(2n)!
n!
para todo número natural n.
(b)
n∑
i=3
k
2k
= 1−
n + 2
2n
para todo número natural n ≥ 3.
4. (2.0) Para usar um aplicativo, deve ser escolhida uma senha de 8 carac-
teres formada por algumas das 26 letras do alfabeto e/ou por alguns dos
10 dígitos (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). As letras e os números não podem
estar repetidos. As letras devem ser maiúsculas. De quantas maneiras
podem ser escolhidas se cada senha deve conter:
(a) pelo menos 1 letra? Justifique,
(b) a letra Z? Justifique,
(c) os dígitos 7 e 9 sempre juntos? Justifique.
5. (1.5) Numa classe de 12 estudantes um grupo de 7 será selecionado
para uma excursão. De quantas maneiras diferentes esse grupo poderá
ser formado:
(a) se não houver restrições? Justifique.
(b) se 2 dos 12 estudantes são namorados e só irão juntos? Justifique.
6. (2.0) Quantos são os anagramas da palavra ARARUAMA:
(a) sem restrições? Justifique;
(b) que contenham as vogais todas juntas? Justifque;
(c) que contenham as vogais todas juntas e as consoantes também
todas juntas? Justifque
Avaliações/CEDERJ-AD2-1-18.pdf
Curso de Tecnologia em Sistemas de Computação
Disciplina: Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
AD2 - Primeiro Semestre de 2018
Nome -
Assinatura -
Questões:
1. (1.1) Uma florista tem rosas, cravos, ĺırios e margaridas em estoque.
Quantos buquês diferentes de uma dúzia de flores contendo pelo menos
2 rosas e um ĺırio podem ser feitos? Justifique.
2. (1.1) Usando o teorema das colunas calcule a seguinte soma:
S = 5× 6× 7 + 6× 7× 8 + 7× 8× 9 + . . .+ 32× 33× 34.
Justifique.
3. (1.1) Para que valores de n ∈ N o desenvolvimento do binômio de
Newton (
√
2x− 5
x3
)n possui termo independente? Justifique.
4. (1.1) Determine a fórmula fechada da seguinte relação de recorrência:
an = 2an−1 + n2
n , a0 = 1,
para n ≥ 1. Justifique.
5. (4.0) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for verdadeira, prove, se for falsa dê um contra-exemplo, justificando.
1
(a) Se dois grafos G1 e G2 têm o mesmo número de vértices, o mesmo
número de arestas e a mesma sequência de graus de vértices então
G1 e G2 são isomorfos.
(b) Se F = (V,E) é uma floresta então |E| = |V | − k , onde k é o
número de componentes conexos de F .
(c) O grafo bipartido completo K6,6 é euleriano e hamiltoniano.
(d) Se G é um grafo planar regular de grau 3 com 20 vértices então G
tem 12 faces.
6. (1.6) Considere o grafo G = (V,E), onde
V = {a, b, c, d, e, f, g, h, i, j} e
V (G) = {(a, b), (b, c), (b, e), (c, d), (d, e), (c, f), (d, g)), (e, h), (f, g), (g, h), (f, j), (h, j), (f, i)}.
(i) G é bipartido? Justifique.
(ii) Calcule o diâmetro de G? E qual o centro de G? Justifique.
2
Gabaritos/gab-CEDERJ-AD2-1-18.pdf
Curso de Tecnologia em Sistemas de Computação
Disciplina: Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
Gabarito AD2 - Primeiro Semestre de 2018
Nome -
Assinatura -
Questões:
1. (1.1) Uma florista tem rosas, cravos, ĺırios e margaridas em estoque.
Quantos buquês diferentes de uma dúzia de flores contendo pelo menos
2 rosas e um ĺırio podem ser feitos? Justifique.
Resposta: Sejam r, c, l,m as quantidades de rosas, cravos, ĺırios e mar-
garidas em estoque, respectivamente. Queremos montar buquês com
12 flores, das quais pelo menos duas são rosas e pelo menos uma é
um ĺırio. Desta forma, queremos o número de soluções inteiras não-
negativas para a seguinte equação:
r + c + l + m = 12 (I)
com as seguintes restrições: r ≥ 2 e l ≥ 1.
Note que podemos reescrever as variáveis r e l em função de duas outras
variáveis r′ e l′ não-negativas, da seguinte maneira:
r = r′ + 2
l = l′ + 1
Desta forma, a equação (I) pode ser escrita de forma equivalente como
descrito na equação (II).
1
r′ + 2 + c + l′ + 1 + m = 12
r′ + c + l′ + m = 9 (II)
O número de soluções inteiras não-negativas da equação (II) é dado
por: CR94 = C
9
9+4−1 = C
9
12 =
12!
3!9!
= 220.
Logo, podem-se montar 220 buquês de 12 flores com pelo menos duas
rosas e um ĺırio a partir do estoque dispońıvel de rosas, cravos, ĺırios e
margaridas.
2. (1.1) Usando o teorema das colunas calcule a seguinte soma:
S = 5× 6× 7 + 6× 7× 8 + 7× 8× 9 + . . . + 32× 33× 34.
Justifique.
Resposta: Seja S =
∑32
i=5 i(i + 1)(i + 2). Vamos calcular o valor deste
somatório utilizando o Teorema das Colunas.
S =
∑32
i=5 i(i + 1)(i + 2)
=
∑32
i=5A
3
i+2
=
∑32
i=5 3!C
3
i+2
= 3!
∑32
i=5C
3
i+2
= 3!(C37 + C
3
8 + . . . + C
3
34)
= 3!([C33 + C
3
4 + . . . + C
3
7 + C
3
8 + . . . + C
3
34]︸ ︷︷ ︸
Teorema das Colunas
− [C33 + C34 + . . . + C36 ]︸ ︷︷ ︸
Teorema das Colunas
)
= 3!(C435 − C47)
= 3!(
35!
31!4!
− 7!
3!4!
)
=
35!
31!4
− 7!
4!
2
Logo, S =
35!
31!4
− 7!
4!
.
3. (1.1) Para que valores de n ∈ N o desenvolvimento do binômio de
Newton (
√
2x− 5
x3
)n possui termo independente? Justifique.
Resposta: Sejam a =
√
2x = (2x)
1
2 e b = − 5
x3
= −5x−3. Do Teorema
Binomial, sabemos que a fórmula do termo geral do desenvolvimento
do binômio (a + b)n é dada por:
Tk+1 = C
k
na
n−kbk
Dáı, temos:
Tk+1 = C
k
n[(2x)
1
2 ]n−k[−5x−3]k
= Ckn(2x)
n−k
2 (−1)k5kx−3k
= Ckn2
n−k
2 x
n−k
2 (−1)k5kx−3k
= Ckn2
n−k
2 (−1)k5kxn−k2 x−3k
= Ckn2
n−k
2 (−1)k5kx(n2− 7k2 )
Como queremos que haja termos independente no desenvolvimento do
binômio,
n
2
− 7k
2
= 0↔ n
2
=
7k
2
↔ n = 7k
Portanto, para que haja termo independente no desenvolvimento de
(
√
2x− 5
x3
)n, n deve ser um múltiplo de 7.
4. (1.1) Determine a fórmula fechada da seguinte relação de recorrência:
an = 2an−1 + n2
n , a0 = 1,
para n ≥ 1. Justifique.
Resposta: Vamos utilizar o método das substituições regressivas.
3
an = 2an−1 + n2
n
= 2 (2an−2 + (n− 1)2(n−1))︸ ︷︷ ︸
an−1
+n2n
= 22an−2 + (n− 1)2n + n2n
= 22 (2an−3 + (n− 2)2(n−2))︸ ︷︷ ︸
an−2
+(n− 1)2n + n2n
= 23an−3 + (n− 2)2n + (n− 1)2n + n2n
...
...
= 2ian−i + (n− (i− 1))2n + (n− (i− 2))2n + . . . + n2n
= 2ian−i + (n− i + 1)2n + (n− i + 2)2n + . . . + n2n
Quando n− i = 0, temos n = i e
an = 2
na0 + 2
n + 2× 2n + . . . + n× 2n
Como a0 = 1, temos
an = 2
n + 2n
n∑
i=1
i︸︷︷︸
P.A. de razão 1
Sabemos que a soma dos n termos de uma PA de razão 1 é dada por:
Sn =
(a1 + an)n
2
onde a1 e an são o primeiro e o n-ésimo termo da P.A., respectivamente.
Portanto,
n∑
i=1
i =
(1 + n)(n)
2
=
n2 + n
2
Dáı,
an = 2
n + 2n(n
2+n
2
) e, consequentemente
4
an = 2
n + 2(n−1)(n2 + n) = 2(n−1)(n2 + n + 2)
Logo, a fórmula fechada da relação de recorrência é
an = 2
(n−1)(n2 + n + 2),∀n ≥ 0
5. (4.0) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for verdadeira, prove, se for falsa dê um contra-exemplo, justificando.
(a) Se dois grafos G1 e G2 têm o mesmo número de vértices, o mesmo
número de arestas e a mesma sequência de graus de vértices então
G1 e G2 são isomorfos.
Resposta: Falsa. Observe na Figura 1 que G1 e G2 são ambos
grafos 3-regulares, com mesmo número de vértices e arestas
mas
não são isomorfos, uma vez que G1 possui triângulos (ou seja 3
vértices que são mutuamente adjacentes) e em G2 o menor ci-
clo tem tamanho 4, ou seja, não existem 3 vértices mutuamente
adjacentes.
Figura 1: G1 e G2 não isomorfos com sequência de vértices (3, 3, 3, 3, 3, 3).
(b) Se F = (V,E) é uma floresta então |E| = |V | − k , onde k é o
número de componentes conexos de F .
Resposta: Verdadeiro.
Seja F = (V,E) uma floresta tal que |V (F )| = n, |E(F )| = m
e k = número de componentes conexas. Como F é uma floresta,
cada componente conexa é uma árvore. Sejam T1, T2, · · · , Tk os
componentes conexos (árvores) de F , V (F ) =
∑k
i=1 V (Ti), E(F ) =∑k
i=1E(Ti). Sabemos que |E(Ti)| = |V (Ti)| − 1 (Teorema).
Logo,
5
|E(F )| = |
∑k
i=1E(Ti)| =
∑k
i=1 |E(Ti)| =
∑k
i=1 |V (Ti)− 1|
= |V (T1)|+ |V (T2)|+ · · ·+ |V (Tk)| − (1 + 1 + · · ·+ 1)︸ ︷︷ ︸
k
= |V (F )| − k
= n− k
(c) O grafo bipartido completo K6,6 é euleriano e hamiltoniano.
Resposta: Verdadeiro. O Teorema de Euler garante que um grafo
é Euleriano se, e somente se, todos os seus vértices têm grau par.
Um K6,6 é um grafo bipartido completo com 6 vértices em cada
parte da bipartição. Consequentemente, é um grafo 6-regular, e,
pelo Teorema de Euler, o K6,6 é euleriano. Além disso, podemos
exibir um ciclo hamiltoniano para o K6,6: a, b, c, d, e, f, g, h, i, j, k, l, a
(considere a Figura 2). Logo, o K6,6 é hamiltoniano.
a b
c d
e f
g h
i j
k l
Figura 2: K6,6 e um de seus ciclos hamiltonianos.
(d) Se G é um grafo planar regular de grau 3 com 20 vértices então G
tem 12 faces.
Resposta: Verdadeiro. O número de faces f de um grafo planar
com n vértices e m arestas é dado por f = m− n + 2. Como G é
3-regular, pelo Teorema do Aperto de Mãos, temos:∑
v∈V (G)
d(v) = 2m
6
donde, m = 30. Portanto, f = 30− 20 + 2 = 12 e G tem 12 faces.
6. (1.6) Considere o grafo G = (V,E), onde
V = {a, b, c, d, e, f, g, h, i, j} e
V (G) = {(a, b), (b, c), (b, e), (c, d), (d, e), (c, f), (d, g)), (e, h),
(f, g), (g, h), (f, j), (h, j), (f, i)}.
Figura 3: Grafo G.
(i) G é bipartido? Justifique.
Resposta: Sim, pois podemos exibir a seguinte bipartição: V =
V1 ∪ V2, onde V1 = {a, c, e, g, i, j} e V2 = {b, d, f, h} (Figura 4).
a b
c d
e f
g h
i
j
Figura 4: Bipartição para G.
7
(ii) Calcule o diâmetro de G? E qual o centro de G? Justifique.
Resposta: A excentricidade de um vértice v, denotada por e(v), é
o maior valor da distância entre v e w, para todo vértice w em G.
v \ w a b c d e f g h i j
a 0 1 2 3 2 3 4 3 4 4
b 0 1 2 1 2 3 2 3 3
c 0 1 2 1 2 3 2 2
d 0 1 2 1 2 3 3
e 0 3 2 1 4 4
f 0 1 2 1 1
g 0 1 2 2
h 0 3 1
i 0 2
j 0
Tabela 1: Distância entre o par de vértices v, w, para todo v, w ∈ G. Note
que, devido à simetria do conceito de distância, a tabela foi parcialmente
preenchida.
Pela Tabela 1, é posśıvel determinar que e(a) = e(e) = e(g) =
e(j) = e(i) = 4 e e(b) = e(c) = e(d) = e(f) = e(h) = 3.
O diâmetro de um grafo G é o maior valor dentre as excentri-
cidades dos vértices de G, i.e., diam(G) = maxv∈V (G) e(v). Dáı,
diam(G) = 4.
O centro de G, denotado por c(G), é o conjunto dos vértices de G
com menor excentricidade. Neste caso, c(G) = {b, c, d, f, h}.
8
Gabaritos/gabarito-ad1-18.pdf
Curso de Tecnologia em Sistemas de Computação
Disciplina: Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
Gabarito AD1 - Primeiro Semestre de 2018
Nome -
Assinatura -
Questões:
1. (1,0) Verifique se cada uma das seguintes afirmações é verdadeira ou
falsa. Se for verdadeira prove, se for falsa justifique.
(a) ∅ ∈ {{∅}}.
Resposta: Falsa. O único elemento do conjunto em questão é {∅}.
As afirmações {∅} ∈ {{∅}} e ∅ ⊆ {{∅}} estariam corretas.
(b) {∅} ⊆ {{∅}}.
Resposta: Falsa. Esta afirmação só seria verdadeira se ∅ fosse
elemento do conjunto. Entretanto, o único elemento do conjunto
em questão é {∅}. As afirmações {∅} ∈ {{∅}}, {{∅}} ⊆ {{∅}} e
∅ ⊆ {{∅}} estariam corretas.
(c) A∪(B−C) = (A−B)∪(A−C). sendo A e B conjuntos quaisquer.
Resposta: Falsa. Observe os diagramas de Venn da Figura 1.
1
Figura 1: Diagramas de Venn
2. (1,5) Usando o Prinćıpio de Inclusão e Exclusão, determine o número
de permutacoes de (1, 2, 3, 4, 5, 6, 7, 8) nas quais nem o 2 ocupa o 2°
lugar nem o 6 ocupa o 6° lugar.
Resposta: Vamos considerar A como o conjunto das permutações de
(1, 2, 3, 4, 5, 6, 7, 8) nas quais o 2 ocupa o 2° lugar, B como o conjunto
das permutações de (1, 2, 3, 4, 5, 6, 7, 8) nas quais o 6 ocupa o 6° lugar,
U como o conjunto de todas as permutações de (1, 2, 3, 4, 5, 6, 7, 8) e P
como o conjunto de permutações de (1, 2, 3, 4, 5, 6, 7, 8) nas quais nem
o 2 ocupa o 2° lugar nem o 6 ocupa o 6° lugar. Para calcular o número
de elementos de P , vamos usar a noção de complemento e o PIE para
2 conjuntos, dado por:
n(A ∪B) = n(A) + n(B)− n(A ∩B)
Utilizando a noção de complemento, podemos escrever n(P ) da seguinte
forma:
n(P ) = n(U)− n(A ∪B)
2
onde n(A ∪B) é calculado usando o PIE, como descrito acima.
CÁLCULO DAS CARDINALIDADES DOS CONJUNTOS
n(U) = P8 = 8!. Basta permutar os 8 algarismos.
n(A) = P7 = 7!. Como o algarismo 2 está fixado na segunda posição,
basta permutarmos os outros 7 algarismos.
n(B) = P7 = 7!. Como o algarismo 6 está fixado na sexta posição,
basta permutarmos os outros 7 algarismos.
n(A ∩ B) = P6 = 6!. Como os algarismos 2 e 6 estão fixados nas se-
gunda e sexta posições, respectivamente, basta permutarmos os outros
6 algarismos.
Pelo PIE, temos: n(A∪B) = 7!+7!−6! = 2×7!−6! = 2×7×6!−6! =
(14− 1)6! = 13× 6!.
Logo, n(P ) = 8!− 13× 6!.
3. (2,0) Mostre pelo Prinćıpio da Indução Matemática que:
(a)
2.6.10.14 · · · (4n− 2) = (2n)!
n!
para todo número natural n.
Resposta: Seja P (n) : 2.6.10.14 · · · (4n− 2) = (2n)!
n!
, ∀ n natural.
BASE DA INDUÇÃO: Vamos mostrar que P (1) é verdadeira.
Como 4(1)−2 = 2 e (2×1)!
1!
= 2! = 2, temos que P (1) é verdadeira.
HIPÓTESE DA INDUÇÃO: Suponha que P (k) : 2.6.10.14. · · · .(4k−
2) = (2k)!
k!
seja verdadeira, ∀k ≥ 1.
PASSO DA INDUÇÃO: Vamos mostrar que se P (k) é verda-
deira, então P (k+1) : 2.6.10.14. · · · .(4k−2).(4(k+1)−2) = (2[k+1])!
(k+1)!
é verdadeira.
3
2.6.10.14. · · · .(4k − 2)︸ ︷︷ ︸
H.I.
.(4(k + 1)− 2) = (2k)!
k!
(4k + 2)
= (2k)!2(2k+1)
k!
× (k+1)
(k+1)
= (2k)!2(k+1)(2k+1)
k!(k+1)
= (2k+2)(2k+1)(2k)!
(k+1)!
= (2k+2)!
(k+1)!
= (2[k+1])!
(k+1)!
Logo, pelo PIM, P (n) : 2.6.10.14 · · · (4n − 2) = (2n)!
n!
é verdadeira
∀n natural.
(b)
n∑
i=3
i
2i
= 1− n + 2
2n
para todo número natural n ≥ 3.
Resposta: Seja P (n) :
∑n
i=3
i
2i
= 1− n+2
2n
, n ≥ 3.
BASE DA INDUÇÃO: Vamos mostrar que P (3) é verdadeira.
De fato, como 3
23
= 3
8
e 1− 3+2
23
= 1− 5
8
= 3
8
, P (3) é verdadeira.
HIPÓTESE DA INDUÇÃO: Suponha que P (k) :
∑k
i=3
i
2i
= 1− k+2
2k
seja verdadeira, ∀k ≥ 3.
PASSO DA INDUÇÃO: Vamos mostrar que se P (k) é verdadeira,
então P (k + 1) :
∑k+1
i=3
i
2i
= 1− (k+1)+2
2k+1
é verdadeira.
4
∑k+1
i=3
i
2i
=
k∑
i=3
i
2i︸ ︷︷ ︸
H.I
+ k+1
2k+1
=
(
1− k+2
2k
)
+ k+1
2k+1
= 1−
(
k+2
2k
− k+1
2k+1
)
= 1−
(
2(k+2)−(k+1)
2k+1
)
= 1−
(
2k+4−k−1
2k+1
)
= 1−
(
k+3
2k+1
)
= 1−
(
(k+1)+2
2k+1
)
Logo, pelo PIM, P (n) :
∑n
i=3
i
2i
= 1− n+2
2n
, é verdadeira ∀n ≥ 3.
4. (2.0) Para usar um aplicativo, deve ser escolhida uma senha de 8 carac-
teres formada por algumas das 26 letras do alfabeto e/ou por alguns dos
10 d́ıgitos (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). As letras e os números não podem
estar repetidos. As letras devem ser maiúsculas. De quantas maneiras
podem ser escolhidas se cada senha deve conter:
(a) pelo menos 1 letra? Justifique,
Resposta: Vamos usar a noção de complemento neste caso. Para
tal, vamos calcular a quantidade total de senhas e subtrair
a quan-
tidade de senhas que NÃO possuem letras. A quantidade total de
senhas com 8 caracteres é dada por: A836 =
36!
28!
. A quantidade de
senhas que NÃO possuem letras é dada por: A810 =
10!
2!
. Logo, uti-
lizando a noção de complemento, a quantidade de senhas é dada
por 36!
28!
− 10!
2!
.
(b) a letra Z? Justifique,
5
Resposta: Como a letra Z está fixada, temos que escolher e po-
sicionar os outros 7 d́ıgitos e, em seguida, vamos escolher uma
posição para a letra Z. Para escolher e posicionar os 7 d́ıgitos, te-
mos A735 =
35!
28!
formas. Posicionados esses d́ıgitos, temos 8 espaços
para posicionar a letra Z, ou seja, 8 formas de posicionar a letra
Z. Pelo PM, a quantidade de senhas que possuem a letra Z é dada
por: 8× 35!
28!
.
(c) os d́ıgitos 7 e 9 sempre juntos? Justifique.
Resposta: Começaremos escolhendo e posicionando os outros d́ıgitos
da senha. Para isso, temos A634 =
34!
28!
. Vamos considerar que os
d́ıgitos 7 e 9 são um único algarismo e escolher um lugar para
posicioná-los entre os algarismos já posicionados. Note que temos
7 espaços e, portanto, 7 maneiras de posicionar o 7 e 9. Note
também que temos duas configurações posśıveis para o 7 e 9: ou
vão aparecer como 79 ou como 97. Logo, pelo PM, a quantidade
de senhas que possuem os d́ıgitos 7 e 9 sempre juntos é dada por
34!
28!
× 7× 2 = 34!
28!
× 14.
5. (1.5) Numa classe de 12 estudantes um grupo de 7 será selecionado
para uma excursão. De quantas maneiras diferentes esse grupo poderá
ser formado:
(a) se não houver restrições? Justifique.
Resposta: Neste caso, não importa a ordem das escolhas. Por-
tanto, a excursão pode ser montada de C712 =
12!
7!5!
formas.
(b) se 2 dos 12 estudantes são namorados e só irão juntos? Justifique.
Resposta: Vamos separar em dois casos: os namorados vão e os
namorados não vão.
• CASO 1: namorados vão
Neste caso, basta escolher os outros 5 estudantes dentre os
10 restantes. Logo, temos C510 =
10!
5!5!
maneiras de formar essa
excursão.
6
• CASO 2: namorados não vão
Neste caso, basta escolher os 7 estudantes dentre os 10 restan-
tes. Logo, temos C710 =
10!
7!3!
maneiras de formar essa excursão.
Pelo PA, temos 10!
5!5!
+ 10!
7!3!
maneiras de formar esta excursão.
6. (2.0) Quantos são os anagramas da palavra ARARUAMA:
(a) sem restrições? Justifique;
Resposta: A palavra ARARUAMA possui 4 A’s, 2 R’s, 1 U e 1
M, totalizando 8 letras. Logo, o número total de anagramas desta
palavra é dado por P 4,2,1,18 =
8!
4!2!1!1!
.
(b) que contenham as vogais todas juntas? Justifque;
Resposta: Vamos considerar todas as vogais como uma única letra
V . Note que existem P 4,15 = 5!4!1! = 5 configurações diferentes
para V . Em seguida, vamos posicionar as consoantes. Temos
P 2,13 =
3!
2!1!
= 3 maneiras de posicioná-las. Depois de posicioná-
las, temos 4 espaços para posicionar V . Logo, pelo PM, temos
5× 3× 4 = 60 anagramas nos quais as vogais estão todas juntas.
(c) que contenham as vogais todas juntas e as consoantes também
todas juntas? Justifique
Resposta: No item (b), constatamos que existem 5 configurações
para V . Vamos assumir que as consoantes também são uma única
letra C. Neste caso, temos P 2,13 = 3!2!1! = 3 configurações distin-
tas para C. Note que, como vogais devem estar todas juntas e
consoantes também, ou temos vogais e consoantes (nesta ordem),
ou consoantes e vogais (nesta ordem). Portanto, 2 configurações
distintas. Assim, pelo PM, temos 5 × 3 × 2 = 30 anagramas nos
quais as vogais todas juntas e as consoantes também todas juntas.
7
Gabaritos/Gabarito-CEDERJ-AP1-1-18-2.pdf
Curso de Tecnologia em Sistemas de Computação
Disciplina Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
Gabarito da AP1 - Primeiro Semestre de 2018
Questões:
1. (1.8) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for verdadeira, prove, se for falsa justifique.
(a) ∅ = {∅}
Resposta: A afirmação é falsa. Dois conjuntos são iguais se todo
elemento de um conjunto é elemento do outro conjunto e vice-
versa.
O conjunto ∅ não tem elementos enquanto {∅} tem um elemento,
∅ ∈ {∅}. Logo, ∅ 6= {∅}.
(b) (A ∪ C)−B = (A−B) ∪ (C −B),
Resposta: A afirmação é verdadeira.
(A ∪ C)−B =
(propriedade da diferença) = (A ∪ C) ∩B =
(propriedade distributiva) = (A ∩B) ∪ (C ∩B) =
(propriedade da diferença) = (A−B) ∪ (C −B)
(c) n(A∪B∪C) = n(A)+n(B)+n(C)−n(A∩B)−n(B∩C)−n(A∩C),
onde A, B e C são conjuntos arbitrários.
Resposta: A afirmação é falsa. Podemos apresentar o seguinte contra-
exemplo:
Considere os seguintes conjuntos:
A = {1, 2, 3, 5}, B = {1, 2, 4, 6}, C = {1, 3, 4, 7}
Neste caso, n(A) = n(B) = n(C) = 4, A ∩ B = {1, 2}, e consequente-
mente n(A∩B) = 2, B∩C = {1, 4} e, portanto, n(B∩C) = 2 e A∩C =
1
{1, 3} e, tendo n(A ∩ C) = 2. Note que A ∪B ∪ C = {1, 2, 3, 4, 5, 6, 7}
e, portanto, n(A ∪B ∪ C) = 7. Por outro lado,
n(A) + n(B) + n(C)− n(A ∩B)− n(B ∩ C)− n(A ∩ C) =
4 + 4 + 4− 2− 2− 2 = 6,
valor diferente de n(A ∪ B ∪ C). Portanto, a fórmula está incorreta
e pode ser reescrita da seguinte maneira, utilizando o Prinćıpio da
Inclusão e Exclusão:
n(A ∪B ∪ C) = n(A) + n(B) + n(C)− n(A ∩B)− n(B ∩ C)− n(A ∩
C) + n(A ∩B ∩ C).
2. (1.7) Mostre por Indução Matemática que:
2.3 + 2.32 + 2.33 + · · ·+ 2.3n = 3n+1 − 3
para todo número natural ≥ 1.
Resposta: Seja P (n): 2.3 + 2.32 + 2.33 + ... + 2.3n = 3n+1 − 3
Base da indução:
Para n = 1, 2.3 = 6 = 9−3 = 32−3 = 31+1−3, logo P (1) é verdadeira.
Hipótese de Indução:
Suponha verdadeiro para k ≥ 1, isto é, P (k) é verdadeira, para k ≥ 1:
P (k): 2.3 + 2.32 + 2.33 + ... + 2.3k = 3k+1 − 3
Passo da Indução:
Vamos mostrar que se P (k) é verdadeiro então P (k + 1) é verdadeiro,
isto é, temos que provar que:
P (k + 1) : 2.3 + 2.32 + 2.33 + ... + 2.3k+1 = 3k+2 − 3 é verdadeira.
2
Desenvolvendo:
2.3 + 2.32 + 2.33 + ... + 2.3k+1 =
= 2.3 + 2.32 + 2.33 + ... + 2.3k︸ ︷︷ ︸
H.I.
+2.3k+1 =
= 3k+1 − 3 + 2.3k+1 =
= 3k+1(1 + 2)− 3 =
= 3k+1(3)− 3 =
= 3k+2 − 3
Logo pelo prinćıpio da indução matemática P (n) é verdadeiro para
todo n natural.
3. (2.0) Uma classe tem 10 meninos e 9 meninas. Determine o número de
comissões diferentes que podemos formar com 4 meninos e 3 meninas:
Seja A o melhor aluno dentre os meninos da classe e seja B a melhor
aluna dentre as meninas.
(a) incluindo obrigatoriamente o melhor aluno dentre os meninos e a
melhor aluna dentre as meninas.
Resposta: Como precisamos escolher o número de comissões com
4 meninos e 3 meninas dentre uma classe com 10 meninos e 9
meninas sendo que A e B estejam sempre presentes na comissão,
então podemos entender este problema como sendo o de encontrar
o número de comissões com 3 meninos e 2 meninas dentre a classe
com 9 meninos (retirado o melhor aluno) e 8 meninas (retirado a
melhor aluna).
Escolher 3 meninos dentre 9 meninos pode ser feito C39 =
9!
6!3!
.
Escolher 2 meninas dentre 8 meninas pode ser feito C28 =
8!
6!2!
.
Assim, pelo prinćıpio multiplicativo, podemos concluir que o número
de comissões que 4 meninos e 3 meninas dentre uma classe com 10
meninos e 9 meninas sendo que obrigatoriamente o melhor aluno
dentre os meninos e a melhor aluna dentre as meninas estejam é
C39 .C
2
8 =
9!
6!3!
. 8!
6!2!
(b) incluindo obrigatoriamente o melhor aluno dentre os meninos ou
a melhor aluna dentre as meninas.
3
Resposta: Sejam A o melhor aluno menino da turma e B a melhor
aluna menina da turma.
Como precisamos escolher o número de comissões com 4 meninos
e 3 meninas dentre uma classe com 10 meninos e 9 meninas sendo
que A OU B estejam presentes na comissão, então devemos divi-
dir este problema em 3 casos:
(i) comissões com 4 meninos e 3 meninas de maneira que A está
na comissão e B não está na comissão.
Neste caso temos que escolher 4 meninos e 3 meninas dentre uma
classe
com 10 meninos e 9 meninas sendo que A esteja na comissão
e B não esteja na comissão, então podemos entender este problema
como sendo o de encontrar o número de comissões com 3 meninos
e 3 meninas dentre a classe com 9 meninos (retirado o melhor
aluno) e 8 meninas (retirado a melhor aluna).
Escolher 3 meninos dentre 9 meninos pode ser feito C39 =
9!
6!3!
.
Escolher 3 meninas dentre 8 meninas pode ser feito C38 =
8!
5!3!
.
Pelo prinćıpio multiplicativo, temos C39 .C
3
8 =
9!
6!3!
. 8!
5!3!
(ii) comissões com 4 meninos e 3 meninas de maneira que B está
na comissão e A não está na comissão.
Neste caso temos que escolher 4 meninos e 3 meninas dentre uma
classe com 10 meninos e 9 meninas sendo que A não esteja na
comissão e B esteja na comissão, então podemos entender este
problema como sendo o de encontrar o número de comissões com
4 meninos e 2 meninas dentre a classe com 9 meninos (retirado o
melhor aluno) e 8 meninas (retirado a melhor aluna).
Escolher 4 meninos dentre 9 meninos pode ser feito C49 =
9!
5!4!
.
Escolher 2 meninas dentre 8 meninas pode ser feito C28 =
8!
6!2!
.
Pelo prinćıpio multiplicativo, temos C49 .C
2
8 =
9!
5!4!
. 8!
6!2!
Vale ressaltar que este item pode ser feito pelo complemento.
(iii) comissões com 4 meninos e 3 meninas de maneira que A e B
pertencem a comissão.
Este caso é semelhante ao item (a) da questão 3, e portanto, temos
C39 .C
2
8 =
9!
6!3!
. 8!
6!2!
comissões.
4
Assim, pelo prinćıpio aditivo, podemos concluir que o número de
comissões que 4 meninos e 3 meninas dentre uma classe com 10
meninos e 9 meninas sendo que obrigatoriamente o melhor aluno
dentre os meninos OU a melhor aluna dentre as meninas estejam
é C39 .C
3
8 + C
4
9 .C
2
8 + C
3
9 .C
2
8 =
9!
6!3!
. 8!
6!2!
+ 9!
5!4!
. 8!
6!2!
+ 9!
6!3!
. 8!
6!2!
4. (1.5) Um grupo de pessoas é formado por sete homens e três mulheres.
Deseja-se formar filas com 5 dessas pessoas de modo que as três mu-
lheres ocupem sempre as três primeiras posições. Assim, de todas as
filas posśıveis, quantas obedecem essa restrição?
Resposta: Como devemos formar filas de modo a colocar as três mulhe-
res do grupo sempre nas três primeiras posições da fila, então isto pode
ser feito de P3 = 3! maneiras. Para completar a fila, faltam 2 pessoas
que devem ser selecionadas dentre os 7 homens. Como importa a ordem
na fila, devemos utilizar o conceito de arranjo, ou seja, o número de
selecionar 2 homens dentre 7 é A27 =
7!
5!
. Pelo prinćıpio multiplicativo,
o número de filas que obedecem essa restrição é P3.A
2
7 = 3!
7!
5!
.
5. (1.5) Quantos números de d́ıgitos, maiores que 600000000, e terminando
em 1 podem ser formados usando apenas os algarismos 1, 1, 1, 1, 3, 3, 6, 6, 6?
Justifique.
Resposta: Queremos formar números de 9 d́ıgitos maiores que 600.000.000
terminando em 1 usando os algarismos 1, 1, 1, 1, 3, 3, 6, 6, 6, ou seja que-
remos arrumar esses algarismos em 9 posições.
A restrição do número ser maior que 6.000.000 nos dá que a primeira
posição só pode ser ocupada pelo algarismo 6 e a restrição do número
terminar em 1 nos dá que a última posição só pode ser ocupada pelo
algarismo 1.
Temos que o algarismo 6 deve ocupar a primeira posição e 1 ocupar a
última posição, desta forma, vamos arrumar os algarismos 1, 1, 1, 3, 3, 6, 6
nas 7 posições restantes:
P 2,2,37 =
7!
2!2!3!
=
7 · 6 · 5 · 4 · 3!
2!2!3!
= 210
6. (1.5) Quantos números naturais de 4 algarismos (repetidos ou não),
podem ser formados com os algarismos 1, 2, 3, 6, 8, e 9. Justifique.
5
Resposta: Cada número de 4 algarismos (que podem ser repetidos)
formados com os d́ıgitos 1, 2, 3, 6, 8, e 9 corresponde a um arranjo com
repetição de 6 elementos tomados 4 a 4. Portanto, o número total
destes números é AR46 = 6
4 = 1296
6
Gabaritos/GABARITO-CEDERJ-AP1-1-18-3-ROCINHA.pdf
Curso de Tecnologia em Sistemas de Computação
Disciplina Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
Gabarito da AP1 - Primeiro Semestre de 2018 - polo rocinha
Questões:
1. (1.8) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for verdadeira, prove, se for falsa justifique.
(a) ∅ ∈ {1, 0,−1}
Resposta: A afirmação é FALSA. Para esta afirmação ser verda-
deira, ∅ deveria ser elemento do conjunto {1, 0,−1}. Desta forma,
as seguintes afirmações são válidas:
• ∅ /∈ {1, 0,−1};
• ∅ ⊂ {1, 0,−1}, pois o conjunto vazio é subconjunto de qual-
quer conjunto.
(b) n(B) = n(A ∪B)− n(A),
Resposta: A afirmação é FALSA. Como contra-exemplo, podemos
tomar os seguintes conjuntos A = {0, 1}, B = {1, 2}. Note que
A ∪ B = {0, 1, 2}. Sendo assim, n(A) = n(B) = 2, n(A ∪ B) −
n(A) = 3 − 2 = 1 e n(B) = 2, ou seja, n(B) 6= n(A ∪ B) − n(A)
contradizendo a afirmação.
(c) Sejam A e B dois conjuntos tais que B ⊆ A.
Então n(A−B) = n(A)− n(B).
Resposta: A afirmação é VERDADEIRA. Temos que A ∪ B =
(A − B) ∪ B. Como (A − B) ∩ B = ∅ então, pelo Prinćıpio
Aditivo, temos n(A ∪ B) = n((A− B) ∪ B) = n(A− B) + n(B).
Por hipótese, temos que B ⊆ A, logo n(A∪B) = n(A). Portanto,
n(A∪B) = n(A) = n(A−B) +n(B), e consequentemente, n(A−
B) = n(A)− n(B).
2. (1.5) Mostre por Indução Matemática que:
2
3!
+
3
4!
+ · · ·+ n
(n + 1)!
=
1
2
− 1
(n + 1)!
1
para todo natural n ≥ 2.
Resposta:
Seja P (n) : 2
3!
+ 3
4!
+ · · ·+ n
(n+1)!
= 1
2
− 1
(n+1)!
∀n ≥ 2
Base da indução: Vamos mostrar que P (2) é verdadeira.
Analisando o lado esquerdo quando n = 2, temos: 2
3!
= 2
6
= 1
3
.
E o lado direito nos fornece: 1
2
− 1
(2+1)!
= 1
2
− 1
3!
= 1
2
− 1
6
= 3−1
6
= 2
6
= 1
3
.
Logo, P (2) é verdadeira.
Hipótese de indução: Suponha P (k) verdadeira, isto é,
2
3!
+
3
4!
+ · · ·+ k
(k + 1)!
=
1
2
− 1
(k + 1)!
, k ∈ N.
Passo Indutivo: Vamos mostrar que se P (k) é verdadeira então
P (k + 1) : 2
3!
+ 3
4!
+ · · ·+ k+1
(k+2)!
= 1
2
− 1
(k+2)!
é verdadeira.
2
3!
+ 3
4!
+ · · ·+ k+1
(k+2)!
=
2
3!
+
3
4!
+ · · ·+ k
(k + 1)!︸ ︷︷ ︸
H.I.
+ k+1
(k+2)!
= 1
2
− 1
(k+1)!
+ k+1
(k+2)!
= 1
2
− 1
(k+1)!
+ k+1
(k+2)(k+1)!
= 1
2
+ −1(k+2)+k+1
(k+2)!
= 1
2
+ −k−2+k+1
(k+2)!
= 1
2
+ −1
(k+2)!
= 1
2
− 1
(k+2)!
Logo, pelo prinćıpio da indução matemática,
P (n) :
2
3!
+
3
4!
+ · · ·+ n
(n + 1)!
=
1
2
− 1
(n + 1)!
é verdadeira ∀n ≥ 2.
2
3. (1.5) Um comitê de 7 membros deve ser formado a partir de 12 mulheres
e de 12 homens. O comitê deve incluir pelo menos 1 mulher e 1 homem.
De quantas maneiras esse comitê pode ser formado? Justifique.
Resposta: Para solucionar esta questão, vamos utilizar o racioćınio do
complemento. Note que, formar comitês que deva incluir pelo menos
uma mulher e um homem é justamente o contrário de formar comitês
com apenas mulheres ou apenas homens no comitê . Consideremos os
seguintes conjuntos:
U : conjunto de todos os comitês contendo 7 membros (é o conjunto
universo).
M : conjunto de comitês contendo 7 membros mulheres.
H: conjunto de comitês contendo 7 membros homens.
X: conjunto de comitês contendo 7 membros, sendo que deve incluir
pelo menos 1 mulher e 1 homem
Observemos que devemos calcular n(X) = n(U)− n(M)− n(H).
Para encontrar o n(U), onde U : conjunto de todos os co-
mitês contendo 7 membros (conjunto universo):
C712+12 = C
7
24 =
24!
7!17!
Para encontrar o n(M), onde M : conjunto de comitês con-
tendo 7 membros mulheres.
C712 =
12!
7!5!
Para encontrar o n(H), onde M : conjunto de comitês con-
tendo 7 membros homens.
C712 =
12!
7!5!
Portanto, o número de comitês com 7 membros a partir de 12 mulheres
e de 12 homens, de modo que deve incluir pelo menos 1 mulher e 1
homem é n(U)− n(M)− n(H) = 24!
7!17!
− 12!
7!5!
− 12!
7!5!
= 24!
7!17!
− 2 12!
7!5!
.
3
4. (2.0) Considere os algarismos 1, 2, 3, 4, 5, 6
e 7. Quantos números na-
turais superiores a 1000 e inferiores a 10000 podem ser formados se:
(a) os números são pares e têm todos os d́ıgitos diferentes. Justifique.
Resposta: Queremos encontrar os números naturais superiores
a 1000 e inferiores a 10000 formados apenas com os algarismos
1, 2, 3, 4, 5, 6 e 7, logo queremos encontrar os números naturais
de 4 algarismos utilizando os algarismos 1, 2, 3, 4, 5, 6 e 7. Como
queremos que os números sejam pares, temos que estes devem ter-
minar com algarismo par, logo temos três possibilidades: 2, 4 e
6. Como para esta questão, todos os d́ıgitos devem ser diferentes,
então utilizaremos arranjos simples. Se fixarmos o algarismo 2
para ser o algarismo final do número temos A(6, 3) para os três
algarismos restantes. Se fixarmos os outros dois algarismos pares
da mesma forma que o algarismo 2, também teremos A(6, 3) para
os outros três algarismos restantes. Portanto, pelo prinćıpio adi-
tivo, temos 3.A(6, 3) = 3.6!
3!
= 360 números pares.
(b) os números são ı́mpares e os d́ıgitos podem ser repetidos. Justifi-
que.
Resposta: Queremos encontrar os números naturais superiores
a 1000 e inferiores a 10000 formados apenas com os algarismos
1, 2, 3, 4, 5, 6 e 7, logo queremos encontrar os números naturais
de 4 algarismos utilizando os algarismos 1, 2, 3, 4, 5, 6 e 7. Como
queremos que os números sejam ı́mpares, temos que estes devem
terminar com algarismo ı́mpar, logo temos quatro possibilidades:
1, 3, 5 e 7. Como para esta questão, os d́ıgitos podem ser repe-
tidos, então utilizaremos arranjos com repetição. Se fixarmos o
algarismo 1 para ser o algarismo final do número temos AR(7, 3)
para os três algarismos restantes. Se fixarmos os outros três alga-
rismos ı́mpares da mesma forma que o algarismo 1, também tere-
mos AR(7, 3) para os outros três algarismos restantes. Portanto,
pelo prinćıpio aditivo, temos 4.AR(7, 3) = 4.73 = 1372 números
ı́mpares.
5. (1.7) Considere as letras da palavra MATEMATICA (sem acento).
4
(a) Quantos anagramas podem ser formados ? Justifique.
Resposta: A palavra MATEMATICA tem 10 letras das quais
3 são A’s, 2 são M’s, 2 são T’s, 1 é E, 1 é I e 1 é C. Como
temos letras repetidas, para determinar o número de anagramas
desta palavra temos que utilizar o conceito de permutação com
repetição. Portanto, temos P 3,2,2,1,1,110 =
10!
3!2!2!1!1!1!
anagramas da
palavra MATEMATICA.
(b) Em quantos anagramas as consoantes estão todas consecutivas?
Justifique.
Resposta: Inicialmente vamos determinar o número de vogais e
consoantes da palavra a fim de facilitar nossos cálculos. A palavra
M A T E M A T I C A tem 5 vogais, a saber: 3A’s, 1 E e 1 I,
e as 5 consoantes: 2M’s, 2T’s e 1C, totalizando 10 letras.
Queremos determinar o número de anagramas onde as CONSOAN-
TES aparecem todas juntas. Para isso, vamos utilizar o seguinte
racioćınio:
Uniremos todas as CONSOANTES em um único bloco e o consi-
deraremos uma única letra. Neste bloco, as 5 consoantes podem
ser arrumadas de P 2,2,15 formas, pois temos duas repetições das
letras M e T.
Agora, basta permutarmos as 5 vogais juntamente com o bloco de
consoantes, levando em conta que a letra A se repete 3 vezes nesta
palavra. Logo, temos P 3,1,1,16 formas de posicionar estas 6 letras.
Portanto, o número de anagramas da palavra M A T E M A T
I C A é dado por:
P 2,2,15 × P
3,1,1,1
6 =
5!
2!2!1!
× 6!
3!1!1!1!
= 30× 120 = 3600.
6. (1.5) No sistema decimal de numeração, quantos números existem com
5 algarismos repetidos ou não? Justifique.
Resposta: Observemos que para no sistema decimal de numeração,
os números são formados pelos algarismos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Que-
remos os números com 5 algarismos repetidos ou não, então temos
5
como restrição que o primeiro d́ıgito (dezena de milhar) não contempla
o algarismo 0, logo o primeiro d́ıgito possui apenas as possibilidades
1, 2, 3, 4, 5, 6, 7, 8, 9.
Para a primeira posição temos 9 maneiras (1, 2, 3, 4, 5, 6, 7, 8, 9). Fixado
um número na primeira posição, temos AR410 = 10
4 possibilidades, pois
para os demais d́ıgitos devemos considerar o algarismo 0 e os números
podem estar repetidos ou não. Logo, usando o prinćıpio multiplicativo,
temos 9AR410 = 90000 possibilidades.
OUTRO RACIOCÍNIO: A quantidade de números de 5 algarismos
são todos os arranjos de 5 posições usando 10 algarismos, que podem
ser com repetição ou não, menos aqueles que começam por zero. O
total de arranjos de 5 posições são arranjos com repetição AR510 = 10
5.
O total de arranjos de 5 algarismos que têm 0 na primeira posição
é AR410 = 10
4. Logo, usando a noção de complemento, tem-se que
105 − 104 = 100000− 10000 = 90000 números.
6
Gabaritos/Gabarito_AP2_18_1.pdf
Curso de Tecnologia em Sistemas de Computação
Disciplina Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
Gabarito da AP2 - Primeiro Semestre de 2018
Questões:
1. (1.2) Determine quantas são as soluções inteiras, não negativas da
equação:
x1 + x2 + x3 + x4 ≤ 25
tais que x2 > 1 ? Justifique.
Resposta: Como a variável x2 é maior que 1, ou seja, x2 é maior ou
igual a 2, precisamos reescrever a inequação em função de uma variável
não negativa. Seja x2 = x
′
2 + 2. Note que, como x2 ≥ 2, x′2 ≥ 0.
Fazendo a substituição na inequação de x2 por x
′
2 + 2 temos:
x1 + x
′
2 + 2 + x3 + x4 ≤ 25
x1 + x
′
2 + x3 + x4 ≤ 23
Para transformar esta inequação em uma equação, vamos acrescentar
uma variável f de folga. Esta variável tem o papel de completar o valor
que a expressão à esquerda assume de modo a igualá-lo ao resultado da
direita da inequação. Então, se, por exemplo, x1 +x
′
2 +x3 +x4 = 23, f
assume o valor 0. Se x1 +x
′
2 +x3 +x4 = 22, então f assume o valor 1 e
assim sucessivamente. Note que o maior valor que f pode assumir é 23.
Assim, estamos acrescentando à inequação a variável f ≥ 0 de modo a
obter a seguinte equação com variáveis inteiras e não-negativas:
1
x1 + x
′
2 + x3 + x4 + f = 23
Logo, o número de soluções inteiras não negativas de x1 + x2 + x3 +
x4 ≤ 25 com x2 > 1 corresponde ao número de soluções inteiras não
negativas da equação acima, que podemos obter utilizando o conceito
de Combinações com repetição. Portanto, temos CR235 = C
23
23+5−1 =
C2327 =
27!
23!4!
= 17550 soluções inteiras e não-negativas para a inequação
x1 + x2 + x3 + x4 ≤ 25, sendo x2 > 1.
2. (1.3) Determine o termo independente no desenvolvimento de
(
5x3 − 4
x2
)55
Justifique a resposta.
Resposta: A fórmula para o termo geral do desenvolvimento do Binômio
de Newton de (a + b)n é dada por: Tk+1 = C
k
n a
n−k bk, para k =
0, 1, · · · , n. Neste caso temos n = 55, a = 5x3 e b = − 4
x2
).
Tk+1 = C
k
55 (5x
3)55−k (− 4
x2
)k
= Ck55 (5)
55−k x165−3k (−1)k 4k
x2k
= Ck55 (5)
55−k (−1)k x165−3k 4k
x2k
= Ck55 (5)
55−k (−1)k 4k x165−3k
x2k
= Ck55 (5)
55−k (−1)k 4k x165−3k−2k
= Ck55 (5)
55−k (−1)k 4k x165−5k
Como queremos o termo independente, queremos o coeficiente de x0,
logo temos:
165− 5k = 0
5k = 165
k = 33
Portanto, T34 = C
33
55 (5)
55−33 (−1)33 433 = 55!
33!22!
522 (−1) 433 =
− 55!
33!22!
522 433.
2
3. (1.0) Use o Teorema das diagonais para calcular a seguinte soma:
C150 + C
2
51 + C
3
52 + · · ·+ C1160
Resposta: O teorema das diagonais nos diz que C0n + C
1
n+1 + C
2
n+2 +
. . . + Crn+r = C
r
n+r+1
C150 + C
2
51 + C
3
52 + · · ·+ C1160 =
= C150 + C
2
51 + C
3
52 + · · ·+ C1160 + C049 − C049 =
= C049 + C
1
50 + C
2
51 + C
3
52 + · · ·+ C1160︸ ︷︷ ︸
Pelo teorema das diagonais, quando n=49 e r=11
− C049 =
= C1149+11+1 − C049 =
= C1161 − C049 =
= 61!
11!50!
− 49!
0!49!
=
= 61!
11!50!
− 1
4. (1.0) Encontre a fórmula fechada da relação de recorrência:
an = 2an−1 − 1 para todo número natural n,
a0 = −1
Justifique.
Resposta: Utilizando
o método da Substituição regressiva temos:
3
an = 2 an−1 − 1
= 2 (2 an−2 − 1) − 1
= 22 an−2 − 2 − 1
= 22 (2 an−3 − 1) − 2 − 1
= 23 an−3 − 22 − 21 − 20
...
= 2i an−i − 2i−1 − 2i−2 − . . . − 22 − 21 − 20
Fazendo n− i = 0 temos que i = n e sabendo que a0 = − 1, temos:
an = 2
n a0 − 2n−1 − 2n−2 − . . . − 22 − 21 − 20
= − 2n − 2n−1 − 2n−2 − . . . − 22 − 21 − 20
= − ( 20 + 21 + 22 + . . . + 2n−2 + 2n−1 + 2n )︸ ︷︷ ︸
soma dos n + 1 primeiros termos de uma P.G de razão 2.
= −
(
2n+1 − 20
2 − 1
)
Portanto, a fórmula fechada para a relação de recorrência é an = 1 −
2n+1, n ≥ 0, a0 = − 1.
5. (1.3) Seja G um grafo planar conexo com sequência de grau de vértices
(1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5). Determine o número de arestas e o número
de faces de G. Justifique.
Resposta: Pelo Teorema do Aperto de Mãos, temos:∑
v∈V
d(v) = 2m
4
Como G possui a sequência de grau de vértices (1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5),
então:
1+2+2+2+2+2+3+3+3+4+4+5+5 = 2m⇒ 38 = 2m⇒ m = 19
Pelo teorema de Euler para grafos planares temos que em um grafo pla-
nar, f = m− n+ 2, onde f,m, n denotam respectivamente os números
de faces, arestas e vértices do grafo. Assim, G possui:
f = m− n + 2⇒ f = 19− 13 + 2⇒ f = 8
6. (4.2) As seguintes perguntas devem ser respondidas considerando o
grafo G = (V,E), sendo: V = {a, b, c, d, e, f, g} e E = {(a, b), (a, e), (a, f),
(a, g), (b, c), (c, d), (c, e), (c, f), (d, e), (d, g), (e, f), (f, g)}
Considere a seguinte representação gráfica:
a 
b 
c 
d e 
f 
g 
(a) G é bipartido? Justifique.
Resposta: NÃO, pois um grafo G é bipartido se e somente G não
possui ciclo ı́mpar, e neste caso o grafo G possui ciclo ı́mpar, como
por exemplo, a, e, f, a.
(b) O conjunto de vértices {a, e, f, g} é uma clique de G?
Resposta: NÃO, pois um subconjunto de vértices de um grafo G é
clique, se para quaisquer dois pares de vértices deste subconjunto,
estes são adjacentes. No conjunto de vértices {a, e, f, g} isto não
acontece, já que os vértices e e g não são adjacentes.
5
(c) G é euleriano? Justifique.
Resposta: NÃO, pois por teorema temos que um grafo G é eule-
riano se e somente se todo vértice de G possui grau par.
Os graus dos vértices d e g do grafo G possuem grau ı́mpar, isto
é, dG(d) = dG(g) = 3.
Logo, G não é euleriano.
(d) G é hamiltoniano? Caso seja, dê o ciclo hamiltoniano de G.
Resposta: SIM, pois podemos exibir o seguinte ciclo Hamiltoniano:
abcdefga.
(e) Qual o diâmetro de G e qual o centro de G? Justifique.
Resposta: Sabemos que:
• A distância entre vértices v, w, denotada por d(v, w) é o ta-
manho do menor caminho entre v e w, caso exista algum.
• A excentricidade de um vértice v, denotada por e(v), é a maior
distância de v a qualquer outro vértice do grafo.
• O diâmetro de um grafo G, denotado por diam(G), é o valor
da maior excentricidade de G.
• O centro de um grafo G, denotado por C(G), é o conjunto de
vértices com a menor excentricidade de G.
Assim, como e(a) = e(b) = e(c) = e(d) = e(e) = e(f) = e(g) = 2,
temos que diam(G) = 2 e C(G) = {a, b, c, d, e, f, g} = V (G).
(f ) Dê uma orientação às arestas de G (desenhe no grafo), de maneira
que o digrafo gerado por essa orientação seja fortemente conexo.
Justifique.
Resposta: Seja D o digrafo formado com uma orientação dada
pelas arestas de G:
• Um digrafo D é fortemente conexo quando para todo par de
vértices v, w ∈ V (G) existir um caminho em D de v para w
e também de w para v.
6
a 
b 
c 
d e 
f 
g 
Podemos observar que o digrafo D apresentado possui um ciclo
direcionado abcdefga e podemos partir de um vértice escolhido e
chegar a qualquer outro, basta percorrer o ciclo no sentido dado.
Logo, o digrafo D dado é fortemente conexo.
7