ESCOLA SUPERIOR DE TECNOLOGIA DE SETÚBAL
DEPARTAMENTO DE MATEMÁTICA
MATEMÁTICA DISCRETA
1o TESTE (Turmas diurnas)
Curso: LEI
Data: 28 de Abril de 2009
2o Semestre
2008/2009
Duração: 2h
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,5]
1. O produto de três números inteiros consecutivos é divisível por 6:
[1,0]
2. Dados a; b 2 Z, não ambos nulos, mmc (a; b) = jabj sse mdc (a; b) 6= 1.
[1,0]
3. Dados c 2 Z e m 2 N; se 3c
[1,5]
4. O número de sequências binárias de comprimento 8 que começam com 00 ou terminam
em 1 é 26 + 27 .
2c (mod m) então mjc.
II
[1,5]
1. Mostre que, por indução em n, que 9j(10n
1
1), n
1.
[2,0]
2. Utilize o algoritmo de Euclides para calcular o mdc (900; 147) e, em seguida, determine
as soluções da equação diofantina 900x + 147y = 6.
[0,5] 3. (a) Enuncie o critério de divisibilidade por 11 e aplique-o para veri…car que 1617 é
divisível por 11.
[1,0] (b) Determine as decomposições de 200 e 1617 em factores primos e utilize-as para
mostrar que mdc (200; 1617) = 1.
III
[1,0]
1. Determine todas as soluções da congruência linear:
6x
[2,0]
3 (mod 21) :
2. Determine a menor solução positiva do sistema:
x
x
[2,0]
1(mod 5)
:
4(mod 7)
3. Enuncie o teorema de Fermat e utilize-o para obter o resto da divisão de de 245 + 392
por 23.
IV
[1,0]
1. Oito candidatos a um lugar são seriados num concurso. Admitindo que não há empates, determine o número de maneiras distintas de ordenar os cinco primeiros classi…cados.
[1,5]
2. Uma certa substância química é obtida pela mistura de 6 líquidos diferentes. O
processo de mistura consiste em adicionar sequencialmente cada um dos 6 líquidos
numa tina. Sabendo que dois destes líquidos não podem ser misturados imediatamente
um após o outro, de quantas maneiras se poderá realizar a mistura?
[2,5]
3. Determine o número de sequências, sobre o alfabeto fa; b; cg, de comprimento n
que começam com a ou b e terminam com b ou c.
2
2,