MAT1310 T1 2016 1 Gabarito

Prévia do material em texto

MAT1310 – Matema´tica Discreta
T1 – 5 de abril de 2016
Nome:
Matr´ıcula: Turma:
Sala: Ma´quina:
Voceˆ precisa informar corretamente o nu´mero da sala e da ma´quina em que esta´
fazendo a prova para que possamos localizar os seus arquivos e considera´-los na correc¸a˜o.
Este teste vale 3,0 pontos. Sua nota da G1 sera´ calculada assim: Seja
X = sua nota da P1. Seja Y = 0, 7X + T onde T e´ sua nota neste teste. Se
Y > X, sua nota sera´ Y . Sena˜o, sera´ X. Sempre que usar o computador para
resolver parte da questa˜o, na˜o apenas salve o arquivo no drive N: como tambe´m indique
escrevendo no papel o que foi feito. Suas respostas nume´ricas devem estar expandidas
e simplificadas.
Uma part´ıcula estando no ponto (x, y) do plano cartesiano pode se movimentar
dando “passos”de dois tipos permitidos: Ir para (x + 1, y) ou ir para (x, y + 1).
Quantos caminhos existem de (0,0) ate´ (4,4)? 70
Quantos caminhos existem de (0,0) ate´ (40,40)? 107507208733336176461620
Valor: 0.4 para os nu´meros + 0.4 para a justificativa.
Justificativa:
Cada caminho tem 8 (80) passos, sendo metade para cima e metade para a direita.
Portanto, as respostas sa˜o
(
8
4
)
e
(
80
40
)
(so´ precisamos escolher as posic¸o˜es dos passos para
cima, por exemplo). O Maple foi usado para calcular os nu´meros acima.
Agora, tambe´m e´ permitido um terceiro tipo de passo (“diagonal”): ir de (x, y) para
(x + 1, y + 1).
Quantos caminhos existem de (0,0) ate´ (4,4) permitindo os 3 tipos de passos? 321
Quantos caminhos existem de (0,0) ate´ (4,4) sem nenhum passo diagonal? 70
Quantos caminhos existem de (0,0) ate´ (4,4) com exatamente 1 passo diagonal? 140
Com exatamente 2 passos diagonais?90
Com exatamente 3 passos diagonais?20
Com exatamente 4 passos diagonais?1
Valor: 0.5 para os nu´meros acima + 0.5 para a justificativa.
Justificativa: Sem nenhum passo diagonal e´ o exerc´ıcio anterior. Com 1 passo di-
agonal, o caminho passa a ter 7 passos. Um deles e´ o escolhido para ser diagonal, e dos
outros 6, 3 devem ser para cima, portanto, 7
(
6
3
)
= 140. De forma similar, com k passos
diagonais, o caminho tem 2n− k passos, dos quais escolhemos k para serem diagonais,
e dos restantes 2n − 2k escolhemos n − k para serem para cima: (2n−k
k
)(
2n−2k
n−k
)
da´ os
nu´meros acima, e o nu´mero total de caminhos e´ a soma deles,
n∑
k=0
(
2n− k
k
)(
2n− 2k
n− k
)
.
Usamos no maple o comando seq(binomial(2*n-k,k)*binomial(2*n-2*k,n-k),k=0..n);
que, com n = 40, fornece os nu´meros:
107507208733336176461620,
2150144174666723529232400,
20698539808025863847863800,
127729450781151057249210800,
567732526361674666799251900,
1936266721486132547820606480,
5270948297378916380178317640,
11762965698397736168892152880,
21934708297183449808088278230,
34662255086907179943645674240,
46916094561292675951892243584,
54836993643069361502211713280,
55697960934566827322898612160,
49397286620701801607638588160,
38390854953615792507429137280,
26214361564287147207093027072,
15753823055461025965801098000,
8340259264655837276012346000,
3890650044976135731049851000,
1598535332570840147562078000,
577831214478475823831865900,
183438480786817721851386000,
51017944194176577494877000,
12391164856756530066222000,
2617724154680290342937250,
478669559712967376994240,
75315140514278083792800,
10124669095197876833600,
1153011507471995407600,
110101894612710436800,
8707404737345073760,
561768047570649920,
29019905518636890,
1172521435096440,
35953410713220,
803927196072,
12406283890,
121929080,
671580,
1640,
1
E trocando seq por sum, obtemos a soma.
Valor: 0.5 para esses nu´meros, incluindo a listagem acima no arquivo.
Quantos caminhos existem de (0,0) ate´ (40,40) permitindo os 3 tipos de passos?
378150244155138145169182750209
Determine tambe´m o nu´mero de caminhos com cada quantidade de passos diagonais,
a exemplo do que foi feito acima para o (4,4). A listagem do nu´mero de caminhos com
cada quantidade de passos diagonais na˜o deve ser copiada para o papel, mas deve estar
presente no seu arquivo.
Com exatamente 17 passos diagonais: 8340259264655837276012346000
Inclua no arquivo tambe´m um plot onde no eixo x se apresentam a quantidade de
passos diagonais (de 0 ate´ 40) e no eixo y o nu´mero de caminhos de (0,0) ate´ (40,40)
com cada quantidade de passos diagonais. Fac¸a abaixo um esboc¸o do gra´fico obtido
(ou seja, copie da tela para o papel). O que voceˆ observa neste gra´fico?
Comando: plot([seq([k,binomial(2*n-k,k)*binomial(2*n-2*k,n-k)],k=0..n)]);
Podemos observar que para valores entre, aproximadamente, 5 e 22, existe um grande
nu´mero de caminhos, crescendo e decrescendo muito ra´pido, mas que fora deste inter-
valo existem bem menos caminhos.
Valor: 0.5 para o gra´fico e descric¸a˜o acima + 0.2 para o nu´mero 12 correto.
Para qual quantidade de passos diagonais existe o maior nu´mero de caminhos de
(0,0) ate´ (40,40)? 12
Basta comparar os valores com 11, 12, e 13, para ver que o 12 e´ o ma´ximo.
Valor: 0.5 extra. (Valor total do teste: 3.5)
Vamos fazer mais um plot. No eixo x, teremos os nu´meros de 4 ate´ 40. No eixo y, a
quantidade de passos diagonais para a qual existe o maior nu´mero de caminhos entre
(0,0) e (x, x). Fac¸a abaixo um esboc¸o do gra´fico obtido (ou seja, copie da tela para o
papel). O que voceˆ observa neste gra´fico?
Primeiro, vamos pre´-calcular todos os valores, usando os comandos:
for n from 4 to 40 do:
for k from 0 to n do:
r[n,k]:=binomial(2*n-k,k)*binomial(2*n-2*k,n-k);
od; od;
Agora, vamos guargar, para cada n, qual valor de k possui o maior nu´mero de ca-
minhos, usando os comandos:
for n from 4 to 40 do:
t:=0;
for k from 1 to n do:
if r[n,k]>r[n,t] then: t:=k; fi;
od;
rr[k-1]:=t;
od;
Agora o plot:
plot([seq([k,rr[k]],k=4..40)]);
Podemos observar no gra´fico que ele se parece com uma reta de inclinac¸a˜o 0.3, exceto
pelo fato de que tem “degraus”, pois k precisa sempre ser inteiro.