90
edits
Changes
no edit summary
13. Escreva um procedimento Maple para gerar permutações aleatórias como descritas no exercício 144 da página 2988 do livro.
=='''Exemplos Extras'''==
==='''Exemplos extras da seção 4.1'''===
'''EXEMPLO (E1, pag 302)'''
Há 3 voos disponiveis de Indianapolis para St.Louis e, independentemente de quais desses voos será escolhidos, há 5 voos disponiveis de St.Louis para Dallas.De quantas maneiras uma pessoa pode voar de Indianapolis para St.Louis para Dallas?
Solução: Uma vez que existe 3 maneiras para fazer a primeira parte da viajem e 5 maneiras de continuar com a segunda parte da viagem, independentemente de qual vôo for feita para a primeira etapa da viagem, pela regra do produto há 3 x 5 =15 maneiras de fazer toda a viagem.
'''EXAMPLE (E2, pag 302)'''
Um certo tipo de botao de uma fechadura de porta exige que voce insira um codigo antes que a fechadura abra.O bloqueio tem 5 botoes, numerados de 1 a 5.
(a) Se voce escolher um código de entrada que consiste de uma sequencia de 4 digitos, com números repetidos permitidos, quantos códigos de entrada são possíveis?
(b) Se voce escolher um código de entrada que consiste de uma sequencia de 4 digitos, sem repetir os números, quantos códigos de entrada são possíveis?
Solução: Precisa-se preencher os espaços em branco,mas cada espaço deve ser preenchido com inteiros diferentes de 1 a 5.Usando a regra do produto pode ser aplicado 5! = 5x4x3x2x1 = 120 maneiras.
'''EXAMPLE (E3, page 302)'''
Conte os numeros de instruções de impressão nesse algoritmo:
de i=1 até n
inicio
de j=1 ate n
print hello
de k=1 ate n
print hello
fim
Solução: Para cada valor de i,tanto o laço do 'j' como o do 'k' sao executados. Assim a cada i, o número de declarações de impressão executado é 2Xn .Portanto o numero total de instruções de impressao executados é 2xn² .
'''EXEMPLO (E4, page 302)'''
Conte os numeros de instruções de impressão nesse algoritmo:
de i=1 até n
inicio
de j=1 ate n
print hello
de k=i+1 ate n
print hello
fim
Solução: Para cada valor de i,tanto o laço do 'j' como o do 'k' sao executados. Assim a cada laço do i, o número de declarações de impressão executado é i no primeiro laço mais n-i no segundo laço. Portanto para cada i, o numero de impressoes é i + (n-i) = n.
'''EXEMPLO (E5, pag 306)'''
Encontre o numero de palavras com 10 letras sem repeti-las:
(a) que não tenha vogais.
(b) que começam com uma vogal.
(C) que tenha C e V nas extremidades (em qualquer ordem).
(d) que tenha vogais nas duas primeiras posições.
Solução: para resolver o problema é ter em mente uma fila de dez espaços em branco :
a) Cada um dos 10 espaços em branco da cadeia deve conter 1 das 21 consoantes,sem repeti-las.Pela regra do produto: 21 X 20 X 19 X 18 X ... X 12.
b)Existem 5 possibilidades da primeira letra ser uma vogal.Se a vogal for colocada no primeiro espaço em branco existem 25 maneiras para preencher no segundo espaço,24 maneiras de preencher o terceiro espaço,etc . 5 x 25 x 24 x 23 x ... x 18 x 17.
c)Primeiramente contamos o número de maneiras de preencher os 10 espaços começando com C e terminando com V,o numero de manerias de preencher as oito letras restantes é 24 x 23 x ... x 18 x 17;
C _ _ _ _ _ _ _ _ V
Da mesma forma,o número de palavras,porem agora,começando com V e terminado com C, 24 x 23 x ... x 18 x 17;
V _ _ _ _ _ _ _ _ C
Logo,pela regra da soma :
(24 x 23 x ... x 18 x 17) + (24 x 23 x ... x 18 x 17) = = 2 x (24 x 23 x ... x 18 x 17)
d) Primeiramente vamos contar o número de maneiras de colocar as vogais nos dois primeiros espaços em branco.Podemos escolher qualquer uma das 5 vogais para a primeiro espaço e das 4 vogais restantes para o 2 espaço : 5 x 4=20 maneiras de colocar duas vogais nas duas primeiras posições.
Em seguida, vamos preencher os 8 espaços restantes com 24 letras que faltam.Sendo feito da seguinte forma : 24 x 23 x ... x 18 x 17 maneiras.
Portanto, o número de maneiras de colocar vogais nois dois primeiros espaços e oito letras nos restantes dos espaços é: 5 x 25 x 24 x 23 x ... x 18 x 17
'''EXAMPLE (E6, page 306)'''
10 homens e 10 mulheres estão em uma fila:
(a) encontre quantas possibilidades pode ser formada a fila.
(b) encontre quantas possibilidades pode ser formada a fila se duas pessoas do mesmo sexo não podem ficar lado a lado;
(c) encontre quantas possibilidades pode ser formada a fila se Beryl, Carol, e Darryl querem ficar juntas nesta sequencia (Carol, Beryl, and Darryl; ou Darryl, Beryl, e Carol).
Solução:
a)Há 20 pessoas;Portanto eles podem ser colocados em uma fila: 20 x 19 x 18 x....x 1 = 20!
b)se duas pessoas do mesmo sexo não podem ficar lado a lado;Entao há dois padroes possiveis, usando M para Masulino e F para Feminino:
MFMFMFMFMFMFMFMFMFMF e FMFMFMFMFMFMFMFMFMFM.
Se contar o numero de maneiras de se obter a primeira possibilidade, dobramos ela para chegarmos ao resultado final.O Primeiro homem pode ser escolhido em 10 maneiras, a Primeira mulher pode ser escolhida de 10 Maneiras, o homem Segundo pode ser escolhido de 9 maneiras, etc.Assim,pela regra do produto temos :
10 x 10 x 9 x 9 x ... x 2 x 2 x 1 x 1 ou (10!)² maneiras.
c)Considerando primeiro os arranjos onde Beryl,Carol e Darryl ficam um ao lado do outro,nessa ordem.Colocando as outras 17 pessoas na fileira.o que pode ser feito em 17! Maneiras.Nao importa como as 17 pessoas sao colocadas na fila,Beryl,Carol e Darryl,pode ser inserido,nessa ordem,entre duas das 17, ou então colocado em uma das duas extremidades.
No entanto, uma vez que escolher um local para colocar Beryl, Carol, e Darryl, existem 3! = 6 maneiras de colocar Beryl, Carol, e Darryl nesse ponto --- BCD, BDC, CBD, CDB, DBC, DCB.
Portanto, a resposta é obtida colocando os outros 17 em uma fileira; escolher um dos 18 pontos para Beryl, Carol, e Darryl; e organizar os três em um local (em 3! maneiras). Assim, a resposta é: 17! x 3!
'''EXEMPLO (E7, página 308)'''
Encontre o número de palavras 10 letras :
(a) não contenha vogais.
(b) começar com uma vogal.
(c) ter vogais nas duas primeiras posições.
(d) começar com C e terminam com V.
(e) começar com C ou terminar com V.
para resolver o problema é ter em mente uma fila de dez espaços em branco :
a) Cada um dos 10 espaços em branco da cadeia deve conter 1 das 21 consoantes,como podemos repeti-las.Pela regra do produto: 21 X 21 X 21 X 21 X ... X 21 = 21^10 ;
b)Há cinco opções para uma vogal ser colocada na primeira posição, e não há restrições sobre os outros nove letras,por isso : 5 x 26^9
c)Se essas vogais devem estar nas duas primeiras posições e as letras podem ser repetidas, obtém-se o produto: 5² x 26^8
d)Se a palavra tem a forma : C....V existem 26 maneiras para preencher cada uma dos oito espaços. Portanto, há 26^8 palavras desta forma.
e)Precisa-se usar o princípio da inclusão-exclusão para evitar a dupla contagem.Sendo A¹ o conjunto de todas as palavras com 10 letras que começam com C e A² o conjunto de todas as palavras com 10 letras que terminam com V: A¹ U A² = |A¹|+|A²| - |A¹ n A²| = 26^9 + 26^9 - (26^8);
===Exemplos da Seção 4.2===
'''EXEMPLO (E1, pág 314)'''
Provar que em qualquer grupo de três números inteiros positivos, existem pelo menos dois, cuja a soma é par.
Solução:
Considere dois compartimentos, classificado em Par e Ímpar. Se três inteiros positivos são colocados nestes compartimentos, um deles deve ter pelo menos dois inteiros (digamos A e B) no mesmo compartimento. Assim, A e B são ou ambos par ou impar. Em ambos os casos, A + B é PAR.
'''EXEMPLO (E2, pág 314)'''
Se forem escolhidos inteiros positivos aleatoriamente, qual é o número mínimo que podemos garantir que dois dos números escolhidos sejam congruentes módulo 6.
Solução:
Para que A e B serem congruentes módulo 6, temos de ter a mod 6 = b mod 6. Mas existem 6 possibilidades para x mod 6: 0, 1, 2, 3, 4, ou 5. Portanto, 7 inteiros positivos devem ser escolhidos de modo a garantir que, pelo menos, dois sejam congruentes módulo 6.
'''EXEMPLO (E3, página 314)'''
Prove que em qualquer conjunto de 700 palavras em inglês, deve haver pelo menos duas que começam com o mesmo par de letras (na mesma ordem), por exemplo, ST OP e STAndard.
Solução: O número de possíveis pares de letras que podem aparecer nas duas primeiras posições é 26 x 26=676.Assim, qualquer conjunto de 677 ou mais palavras deve ter pelo menos duas palavras com o mesmo par de letras no início da palavra.
(OBS:. Na realidade, o número 700 pode ser substituída com um número muito menor, uma vez que muitas combinações de letras não aparecem como as duas primeiras letras de uma palavra, por exemplo, não há palavras inglesas que começam com NQ, RR, ou TZ).
'''EXEMPLO (E4, página 315)'''
Cada tipo de peça de uma máquina feita em uma fábrica é carimbada com um código do formulário de letter-digit-digit, onde os dígitos podem ser repetidos. Prove que, se 8000 peças são feitas, então, pelo menos, quatro delas devem ter o mesmo código carimbadas.
Solução: O numero de codigos possiveis 26 x 10 x 10 = 2600. Desde que,8000 > 3 x 2600,pelo menos 4 tenham o mesmo codigo.
'''EXEMPLO (E5, página 315)'''
Cada aluno é classificado como um membro de uma das seguintes classes: Freshman, Sophomore, Junior, Senior. Encontrar o número mínimo de estudantes que devem ser escolhidos de modo a garantir que, pelo menos, oito pertencem à mesma classe.
Solução:De um grupo de 28 estudantes podem ser 7 pertencentes a cada classe.Mas se há 29 estudantes, pelo menos 8 devem ser membros da mesma classe.Portanto, o número mínimo de estudantes que deve ser escolhido é de 29.
Em outras palavras, nós estamos olhando para o número mínimo N tal que <math>|\frac{N}{4} | = 8</math>. O numero minimo é 29.
===Exemplos adicionais relativas a Seção 4.3===
'''EXEMPLO (E1, pág 321)'''
Uma classe tem 30 alunos matriculados. De quantas maneiras pode-se:
(a) Colocar 4 alunos em uma fila para uma foto?
(b) Colocar todos os 30 alunos em uma fila para uma foto?
(c) Colocar todos os 30 alunos em duas filas de 15 cada para uma foto?
Solução:
(a) Precisamos preencher a seguinte linha de quatro espaços em branco: 30 x 29 x 28 x 27. Este é o número de permutações de 4 a partir de um conjunto de 30, que é P( 30 ,4 );
b)A resposta pode ser visualizado como o número de maneiras para preencher uma fila com 30 lacunas com os 30 estudantes, que é 30! , ou P( 30, 30 );
c) Podemos ver que o número de maneiras para preencher em duas filas,é cada uma com 15 espaços em branco, com os alunos 30:
Podemos então, começar por preencher a linha de inferior, o que pode ser feito de 30 x 29 x 28 x … x 17 x 16 maneiras. Em seguida, preencher linha superior, que pode ser feito de 15! = 15 x 14 x 13… x 2 x 1 maneiras. Portanto a resposta é (30 x 29 x 28 x … x 17 x 16) x (15 x 14 x 13 x … x 2 x 1) = 30!
'''EXEMPLO (E2, página 324)'''
Um certo tipo de botão de uma fechadura de porta exige que você insira um código antes que a fechadura abra.O bloqueio tem 5 botoes, numerados de 1 a 5.O bloqueio é programado para reconhecer seis códigos de 4 dígitos diferentes, podendo repetir os algarismos de cada código. Quantos conjuntos diferentes de códigos reconhecíveis existem?
Solução:
Há 5⁴=625 possíveis códigos com quatro dígitos. Portanto, há C(625,6) conjuntos diferentes de códigos reconhecíveis.
EXEMPLO (E3, página 324)
…..
'''EXAMPLE (E4, page 324)'''
Quantas maneiras existem de escolher uma comissão de cinco pessoas consistindo de três mulheres e dois homens de um grupo de dez mulheres e sete homens?
Solução: O número de maneiras de escolher três mulheres é C( 10,3 ) e o numero de maneiras de escolher 10 homens é C(7,2).Usando a regra do produto para escolher três mulheres e dois homens é C( 10,3 ) x C(7,2) = 2,520.
'''EXEMPLO (E5, page 324)'''
Sendo o conjunto S = {1,2,3,...,19}. Encontre o número de subconjuntos de S com numeros iguais de inteiros pares e impares.
Solução:
Note que, existem 10 inteiros ímpares e 9 inteiros pares em S. Os subconjuntos a serem contados deve consistir de k inteiros ímpares e k inteiros pares, onde k=1,2,3,...,9. Portanto, pela regra do produto, o número de cada tipo é C(10, k) x C(9,k). Portanto, pela regra da soma, a resposta é C(10, k) x C(9,k) + C(10, k) x C(9,k)
'''EXEMPLO (E6, page 324)'''
Encontre maneiras de dividir um baralho de 52 cartas, em:
a)Em 4 pilhas iguais, classificado em A,B,C,D;
b)Em 4 pilhas iguais, sem classificação;
Solução:
a) Cada pilha deve conter 52/4 = 13 cartas. Na sequencia, empilharemos A,em seguida B, depois C, e finalmente D. Então teremos C(52,13) maneiras de obter a pilha de A, C(39,13) maneiras de obter a pilha de B, C(26,13) maneiras de obter a pilha de C, e C(13,13)=1 maneiras de obter a pilha de D.Portanto pela regra do produto,teremos :
C(52,13) x C(39,13) x C(26,13) x C(13,13) = <math>\frac{52!}{13!.29!} .\frac{39!}{13!.26!} .\frac{26!}{13!.13!} .\frac{13!}{13!.0!} = \frac{52!}{(13!)^4} </math>
b) Se nas 4 pilhas não houver classificação,então podemos permutar as quatro pilhas em 4! Maneiras. Daí a resposta é a mesma do iten anterior dividido por 4!:
'''EXEMPLO (E7, page 324)'''
Supunha que S = {1,2, . . ., 25} . Encontre o numero de subconjuntos de tamanho 5,tal que T:
a) consista de 2 numeros impares e 3 numeros pares.
b) consiste de exatamente três números primos.
c) tenha a soma dos seus elementos, menor que 20.
d) tem, pelo menos, um número par na mesma.
Solução:
a) Há 13 numeros impares; podemos escolher dois em C(13,2) maneiras.Há 12 numeros pares; podemos escolher 3 em C(12,3) maneiras. Usando a regra do produto para encontrar o número de subconjuntos T, temos subconjuntos.
b) Os numeros primos em S são 2,3,5,7,11,13,17,19, and 23, então temos C(9,3) maneiras de selecionar 3 desses numeros.Mas também precisa selecionar 2 dos 16 números compostos para fazer T ter tamanho cinco;então C(16,2) maneiras para isso.Portanto pela regra do produto temos C(9,3) x C(16,2)=10.080 subconjuntos possiveis T.
c) Há poucos subconjuntos com esta propriedade. Então é melhor neste caso, contar diretamente o conjunto de cinco números cuja soma é inferior a 20:
1,2,3,4,5, 1,2,3,4,6, 1,2,3,4,7,
1,2,3,4,8, 1,2,3,4,9, 1,3,4,5,6.
Assim, existem seis desses subconjuntos possiveis.
d) É mais fácil para contar o número total de subconjuntos de tamanho 5, e depois subtrair o número de subconjuntos sem números pares neles: