Matemática Finita discreta

Em cada questão de escolha múltipla são apresentadas quatro opções das quais uma e só uma obedece às condições pedidas 1 O número de diferentes maneiras para distribuir 13 cds iguais e 7 livros diferentes por 5 pessoas é igual a A 20 5 B 1713 4 7⁵ C 1713 4 5⁷ D 13 k 7 5k 2 Nas afirmações seguintes X ℝ é um conjunto enumerável i X n ℚ para qualquer número natural n 1 ii X ℚ ℕ é enumerável iii X ℝ ℤ é enumerável A lista completa de afirmações verdadeiras é a seguinte A i e ii B i e iii C ii e iii D i ii e iii 3 Considere a seguinte afirmação onde X é um conjunto tal que X 1 O produto de duas funções injetivas f X ℝ e g X ℝ é uma função injetiva Sobre esta afirmação podemos afirmar A A afirmação é sempre verdadeira para X um conjunto finito B A afirmação é sempre verdadeira para X um conjunto numerável C A afirmação só pode ser verdadeira para X um conjunto infinito não enumerável por exemplo para X ℝ D Nenhuma das opções anteriores é verdadeira Página 3 de 4 Nas questões seguintes justifique cuidadosa e detalhadamente todos os cálculos raciocínios e afirmações que efetuar 4 Justifique a resposta à pergunta 3 5 Quantos números de 7 dígitos distintos podem ser formados com os algarismos 1 2 3 4 5 6 7 8 9 de modo que os dígitos 5 e 6 nunca fiquem consecutivos 6 Dado n ℕ 0 existem 3n funções distintas f n 3 Destas funções quantas são sobrejetivas 7 Por recurso ao método de indução matemática prove que nk k 2n1 n n ℕ Nas justificações identifique as igualdades binomiais da pág 45 do manual utilizadas FIM Página 4 de 4 Resolução Detalhada de Exercícios de Combinatória e Teoria dos Conjuntos Exercício 1 Problema O número de diferentes maneiras para distribuir 13 CDs iguais e 7 livros diferentes por 5 pessoas é igual a A 20 5 B 17134 7⁵ C 17134 5⁷ D 13 k 7 5k k0 Resolução Temos dois tipos de objetos para distribuir 13 CDs idênticos A distribuição é um problema de combinação com repetição 7 livros diferentes Cada livro pode ser dado a qualquer uma das 5 pessoas Parte 1 Distribuição dos CDs O número de maneiras de distribuir n objetos idênticos para k pessoas é dado por n k 1 k 1 Para nossos CDs 13 5 1 5 1 17 4 17134 Parte 2 Distribuição dos livros Cada um dos 7 livros diferentes pode ser dado a qualquer uma das 5 pessoas 5⁷ Total Pelo princípio multiplicativo 17134 5⁷ Resposta C Exercıcio 2 Problema Nas afirmacoes seguintes X R e um conjunto enumeravel i X n Q para qualquer numero natural n 1 ii X Q N e enumeravel iii X R Z e enumeravel Resolucao Analise das afirmacoes i X n remove um conjunto finito de X mantendoo enumeravel Mas dizer que esta contido em Q e falso ex X Q π ii Produto cartesiano de enumeraveis e enumeravel QN e enumeravel logo X Q N e enumeravel iii Intersecao de enumeravel com qualquer conjunto resulta em enu meravel ou finito Resposta C apenas ii e iii sao verdadeiras Exercıcio 3 Problema Considere a afirmacao sobre o produto de funcoes injetivas f g X R Resolucao A afirmacao e falsa em geral Contraexemplo para X finito Seja X 1 2 f1 1 f2 2 g1 1 g2 2 fg1 1 fg2 4 injetiva Mas com g1 2 g2 1 terıamos fg1 2 fg2 2 nao injetiva Para X infinito tambem existem contraexemplos Logo Resposta D Exercıcio 4 Justificativa detalhada para o Exercıcio 3 1 Definicao Uma funcao h e injetiva se ha hb a b 2 Contraexemplo generico Considere fx x e gx x em X R fgx x2 nao e injetiva por exemplo fg1 fg1 1 3 Conclusao A afirmacao nao e sempre verdadeira independentemente da cardinalidade de X 2 Exercício 5 Problema Quantos números de 7 dígitos distintos podem ser formados com os algarismos 19 sem ter 5 e 6 consecutivos Resolução 1 Total sem restrições P97983181440 2 Números com 5 e 6 consecutivos Tratar 56 ou 65 como um único dígito 2 possibilidades Agora temos 6 itens para arranjar o par 5 outros dígitos Número de opções 2P8622016040320 3 Total desejado 18144040320141120 Resposta 141120 Exercício 6 Problema Quantas funções fn3 são sobrejetivas Resolução Usando o Princípio da InclusãoExclusão 1 Total de funções 3ⁿ 2 Subtrair funções que omitem pelo menos um elemento 3choose12ⁿ3choose21ⁿ3choose30ⁿ 3 Fórmula final 3ⁿ32ⁿ31ⁿ Resposta 3ⁿ32ⁿ3 Exercício 7 Problema Prove por indução que nk choose k de k0 a n 2n1 choose n Prova Base n0 0 choose 011 choose 0 Hipótese de Indução Suponha válido para nm Passo Indutivo nm1 m1k choose k de k0 a m1 mk choose kmk choose k1 de k0 a m1 Lei de Pascal 2m1 choose m m1j choose j de j0 a m reindexando 2m1 choose m 2m2 choose m1 m1 choose m1 2m3 choose m1 usando Adição Paralela Conclusão A fórmula vale para todo n ℕ