ESCOLA SUPERIOR DE TECNOLOGIA DE SETÚBAL
DEPARTAMENTO DE MATEMÁTICA
MATEMÁTICA DISCRETA
EXAME –ÉPOCA de RECURSO
Curso: LEI
Data: 25 de Julho de 2009
2o Semestre
2008/2009
Duração: 2h30m
Instruções:
Leia atentamente a prova nos 15 minutos previstos para esse efeito.
Poderá colocar dúvidas nesse período.
Não deverá responder a diferentes grupos de questões numa mesma folha
de resposta.
É obrigatória a apresentação de um documento de identi…cação.
O abandono da sala em caso de desistência só poderá efectuar-se decorrida uma hora a partir do início da prova.
Não se aceitam respostas escritas a lápis.
Justi…que convenientemente todas as respostas.
I
Diga, justi…cando adequadamente, se as seguintes proposições são verdadeiras ou falsas:
[1,0]
1. A equação diofantina 25x + 30y = 1001 tem uma in…nidade de soluções.
[1,0]
2. Se 28x
[1,0]
3. Há 63 42 maneiras distintas de formar comissões com 3 professores e 2 alunos de entre
6 professores e 4 alunos.
[1,5]
4. Um grupo de cinco pessoas troca apertos de mão entre si. Então, o número de pessoas
que dá um número ímpar de apertos de mão pode ser 0, 2 ou 4.
16 (mod 32) então 7x
4 (mod 8) :
II
[1,5]
1. Mostre por indução que, para todo o número natural n; n2 + n é par.
[1,5]
2. Determine o resto da divisão de 191000 por 13.
1
[2,0]
3. Determine, utilizando o teorema chinês dos restos, a menor solução positiva do seguinte
sistema:
8
< x 3 (mod 3)
x 7 (mod 5) :
:
5x 9 (mod 7)
III
[1,5]
1. Antes do início de uma partida de futebol é habitual que os 4 árbitros e os 11 jogadores
de cada equipa tirem uma foto. De quantas maneiras diferentes se podem dispor em
…la os 26 elementos de forma que os 4 árbitros …quem ao centro e os jogadores de cada
equipa …quem juntos?
[1,5]
2. Enuncie o teorema binomial e utilize-o para determinar o coe…ciente de x
1
p1
x
1
do binómio
5
:
[1,0]
3. Numa sondagem realizada em 1000 lares portugueses, observou-se que 90% deles têm
televisão, 71% têm telefone …xo e que 65% têm televisão e telefone …xo. Qual é a
percentagem daqueles lares que não têm televisão nem telefone …xo?
[1,0]
4. Suponha que estão a realizar este exame de Matemática Discreta 85 alunos. Mostre
que pelo menos 5 alunos irão ter a mesma nota …nal.
IV
1. Considere o seguinte grafo ponderado G:
b
d
a
c
f
e
g
[1,5] (a) Determine a matriz de adjacência de G e utilize-a para obter o número de passeios
de comprimento 2 de b para g:
[1,5] (b) Determine, aplicando o algoritmo de Kruskal, uma árvore de suporte de custo
mínimo de G e indique o respectivo custo. (NOTA: descreva cuidadosamente os
passos realizados por aquele algoritmo.)
2. Considere uma árvore T com 14 vértices, os quais são apenas de grau 1 ou de grau 5.
[1,5] (a) Quantos vértices de T têm grau 5?
[1,0] (b) Determine o número de arestas do grafo complementar de T e indique, justi…cando, se este grafo é regular.
2