Matemática Finita

Matemática Discreta 1 Seja i o número de pessoas que descem na paragem A então temos 15 i formas distintas de descerem i passageiros na paragem A Todos os 15 i passageiros restantes devem descer na paragem B logo só existe uma forma de isto acontecer Assim para cada i temos 15 i 1 formas distintas para que os passageiros saem do autocarro Como sempre há alguém para descer em cada uma das paragens temos que 1 i 14 Portanto a solução é 15 i 14 i1 Resposta D 2 i Verdadeiro Seq8 é o conjunto das sequências de 8 bits e cada sequência de 8 bits representa um número de 0 a 255 totalizando 256 elementos ii Verdadeiro P81 tem cardinalidade 2⁸ 256 256 portanto podemos definir uma bijeção iii P41 P41 2⁴ x 2⁴ 2⁸ 256 Seq8 portanto também podemos definir uma bijeção Resposta D 3 Se g Q X é sobrejetiva então Q X Além disso se g o f é injetiva então Q Y Logo X Q Y Resposta D Nas questões seguintes justifique cuidadosa e detalhadamente todos os cálculos raciocínios e afirmações que efetuar 4 O problema só com os algarismos 1 2 3 e 4 quantos números de 8 dígitos podemos construir de modo que cada um dos algarismos 1 2 3 e 4 apareça pelo menos uma vez foi resolvido por um estudante da seguinte maneira Comecese por distribuir os algarismos 1 2 3 e 4 pelas primeiras quatro posições com o que fica garantido que cada um destes algarismos aparece pelo menos uma vez Há 4 maneiras diferentes para o fazer As restantes quatro posições das unidades dezenas centenas e dos milhares podem ser ocupadas por qualquer um dos algarismos 1 2 3 4 num total de 4⁴ possibilidades A solução do problema é assim igual a 4 x 4⁴ 6144 Analise esta resposta e caso necessário corrijaa 5 Nas duas alíneas seguintes utilize as igualdades binomiais listadas na pág 45 da Secção 12 do manual 51 Por aplicação direta da expansão fatorial provase que n 1 2 n 2 n² n 1 Contudo sem se utilizar a expansão fatorial esta mesma igualdade pode ser verificada pelo método de indução matemática Apresente esta verificação 52 Calcule k nk n n k0 6 Sejam m n N 0 61 Quantas funções bijetivas distintas f n n é que existem 62 Dada uma função f X Y pode sempre definirse uma nova função F X fX sobrejetiva por Fx fx x X Considerando o conjunto de todas as funções injetivas f n m quantas funções bijetivas F distintas podem definirse FIM Página 4 de 4 Enunciado 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 Dentro de um autocarro estão 15 passageiros que irão sair nas paragons A ou B Sabendo que sai sempre alguém em cada uma das paragons e que o autocarro fica sem passageiros na paragem B o número de maneiras distintas para que os diferentes passageiros saiam do autocarro é igual a A 15 i15 j 0ij15 ij15 B 15 i15 i j 0ij15 ij15 C 15 i 15 i j 0ij15 ij15 D 15 i 14 i1 2 Considere as seguintes afirmações i Existe uma bijeção entre 256 e Seq8 ii Existe uma bijeção entre P8 e 256 iii Existe uma bijeção entre P4 x P4 e Seq8 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 Dados dois conjuntos não vazios X e Y sabese que f Q X é uma função sobrejetiva e que g X Y é uma função tal que a função composta g o f é injetiva Relativamente aos conjuntos X e Y podemos garantidamente afirmar A X Y B X Y C X Y D X Y Página 3 de 4 4 A resposta esta incompleta pois o estudante considerou apenas as possibilidades em que 1 2 3 4 ocupam as quatro primeiras posições Ele deveria escolher 4 dentre as 8 usando a combinações 8 4 e então prosseguir com o raciocínio utilizado Portanto a solução é 8 4 4 44 430080 5 51 Para n2 temos 3 2 2 2 3 1 4 22 h1 é verdade se 1 2 0 Suponha que a afirmação é verdadeira para nk ou seja k1 2 k 2 k2 Vamos mostrar que é verdadeira para n k1 Temos k2 2 k1 2 k1 1 k1 2 k1 2 Triangulo de Pascal k1 1 k 1 k 2 k1 2 Hipótese de indução k1 1 k 1 k2 k1 k k2 k2 2k 1 k12 Portanto a afirmação é verdadeira para todo n2 n1 Se considerarmos 1 2 0 4 52 k0n knkn k0n k2 n2 k0n k2 k0n n2 k0n k1 2 k 2 n1n2 0 i2n i 2 k0n k 2 n1n2 Propriedades Triangulo de Pascal Coluna n2 3 n1 3 n1n2 n2n1n3 n1nn13 n1nn n1nn26 n16 6n6 n1n4n16 4n3 3n2 n6 61 O número de bijeções será a quantidade de permutações de 1n ou seja n 62 Em uma função injetiva o números da imagem tem apenas um correspondente no dominio ou seja a imagem de f tem tamanho n Portanto o número de funções injetivas é m n Assim pela definição de F temos que a quantidade de bijeções F será m n Quantidade de conjuntos fX de tamanho n dentro do conjunto Y de tamanho m