p1 06 1

Prévia do material em texto

Matemática Discreta MAT1310 P1 2006.1 
Solução resumida 
 
 
1a) Achar uma fórmula para a soma dos cubos dos n primeiros números inteiros 
positivos que divididos por 3 deixam resto 1, começando com 10, isto é, 
103+133+163 + ... 
1b) Calcule o valor para n =100. 
Obs. Vamos representar por (a b) o coeficiente binomial. 
Seja a0=103, a1=133, a2=163,..., an=(3n+10)3. 
Seja Sn= a0+a1+a2+...+an. 
A soma dos n primeiros números pedida é Sn-1. Vamos achar uma fórmula para 
Sn e substituir n por n-1, ou subtrair an=(3n+10)3. 
 
Temos deltaSn= Sn+1-Sn= ab+1= (3n+13)3. Como é um polinômio de grau 3, 
sabemos que Sn será um polinômio de grau 4. Então: 
Sn= a(n 4)+b(n 3)+c(n 2)+d((n 1)+e(n 0). Para calcular a b c d e , fazemos 
n=0,1,2,3,4, ou usamos a expansão de Newton, que nos dá diretamente 
e= S0, d=deltaS0, c=delta2S0, b=delta3S0, a=delta4S0. 
 
Escrevendo a tabela de diferenças, vem : 
 
 
n 0 1 2 3 4 
S 103 103+133 103+133+163 
deltaS 133=2197 163=4096 193 =6859 10648 15625 
delta2S 1899 2763 3789 4977 
delta3S 864 1026 1188 
delta4S 162 162 
 
Então: Sn= 162(n 4)+864(n 3)+1899(n 2)+2197((n 1)+1000(n 0) 
Como a resposta é Sn-1, temos que a soma pedida é: 
 
Sn-1= 162(n-1 4)+864(n-1 3)+1899(n-1 2)+2197(n-1 1)+1000(n-1 0) 
 
b) basta fazer n=99 na fórmula de Sn, ou , o que dá no mesmo, fazer n=100 na 
fórmula de Sn-1, obtendo; 
S99=162x99x98x97x96/4! +864x99x98x97/3! +1899x99x98/2 +2197x99 
+1000= 754777000 
 
Alternativamente,defina a0=0, a1=103, an=(3n+7)3. Agora a soma pedida é Sn, e 
a tabela de diferenças tem uma nova coluna à esquerda ; 
 
 
 
n 0 1 2 3 4 
S 0 103 103+133 103+133+163 
deltaS 1000 133=2197 163=4096 193 =6859 10648 
delta2S 1197 1899 2763 3789 4977 
delta3S 702 864 1026 1188 
delta4S 162 162 162 
 
Então: Sn= 162(n 4)+702(n 3)+1197(n 2)+1000((n 1)+ 0(n 0). 
E fazendo n=100, obtemos o mesmo valor 754777000. 
Exercício: Demonstre diretamente que para todo n>0, 
162(n-1 4)+864(n-1 3)+1899(n-1 2)+2197(n-1 1)+1000(n-1 0)= 
= 162(n 4)+702(n 3)+1197(n 2)+1000((n 1)+ 0(n 0). 
Como ambos são polinômios de grau 4, basta verificar para 5 valores. 
 
 
2a.Ache os 5 primeiros termos da serie formal H , sabendo que sua inversa é 
1 - 2x + x2. 
 
Seja H=a0+a1x+a2x2+a3x3+a4x4+... Basta escrever (1-2x+x2)H=1, coletando 
termos: 
(1-2x+x2)( a0+a1x+a2x2+a3x3+a4x4+...)=1 
a0=1 
a1-2a0=0 
a2-2a1+a0=0 
a3-2a2+a1=0 
a4-2a3+a2=0 
Resolvendo o sistema, vem a1=2, a2=3, a3=4, a4=5. 
Outra solução é observar que 1-2x+x2=(1-x)2. Logo H=(1-x) -2,e expandir usando 
coeficientes binomiais (-2 n), com n=0,1 ,2 ,3, 4. 
 
 
 
 
3. Uma família composta de pai, mãe e 6 filhos senta-se diariamente a uma mesa 
retangular para as refeições (2 cabeceiras e 3 de cada lado) . De quantas 
maneiras diferentes eles podem sentar-se à mesa, sendo que os pais sempre 
ocupam as cabeceiras ( não necessariamente as mesmas) e os filhos nunca 
repetem o lugar que ocuparam no almoço do dia 1-1-2006 ? 
 
Considerando só as posições dos filhos, temos que calcular as permutações 
caóticas de 6 elementos, e depois multiplicar por 2 para levar em conta que os 
pais podem trocar de cabeceira. No fim somamos 1 se queremos contar também 
o almoço de 1-1-2006. 
Para calcular as permutações caóticas de 6 elementos, seja P o conjunto das 
permutações de {1,2,3,4,5,6}. Seja Ai o conjunto das permutações que fixam o 
elemento i. Dados 2 conjuntos A e B, vamos denotar sua interseção por A.B. 
Uma permutação é caótica, se não pertence a nenhum Ai,. Logo o que queremos 
é calcular a0=S0-S1+S2-S3+S4-S5+S6. 
S0=|P|=6!=720 ; 
S1=|A1|+|A2|+...+|A6|= 6x5! =720 
S2=|A1.A2|+|A1.A3|+...|A5.A6|=15x4! = 360 
S3=|A1.A2.A3|+...+|A4.A5.A6|=20x3! = 120 
S4=|A1.A2.A3.A4|+...+|A3.A4.A5.A6|=15x2!= 30 
S5=|A1.A2.A3.A4.A5|+...| A2.A3.A4.A5.A6|= 6 
S6=|A1.A2.A3.A4.A5.A6|=1 
Então, a0=720-720+360-120+30-6+1=265 
Logo há 530 maneiras sem contar a do almoço de 1-1-2006. 
 
 
 
 
4. Um clube tem 100 sócios e a diretoria vai ser escolhida dentre eles da 
seguinte maneira: 5 cargos serão preenchidos, mas o mesmo sócio pode ocupar 
um ou mais cargos. De quantas maneiras diferentes pode ser formada a 
diretoria? 
 
. Vamos representar por (a b) o coeficiente binomial. 
Considerando todos os cargos iguais, temos combinação com repetição de 100 
elementos 5 a 5, e sabemos que isto é o coeficiente de x5 na expansão de 
(1-x)-100. o que dá (-1)5 (-100 5)=100x101x102x103x104/5!=91.962.520 
Outra interpretação; os cargos são todos diferentes; então há 100 escolhas para 
cada cargo, e a resposta é 1005=10.000.000.000.