Sequências Infinitas e Função Desvio - Lista de Exercícios

Em cada questão de escolha múltipla são apresentadas quatro opções das quais uma e só uma é verdadeira 1 Definimos o espaço das sequências infinitas com dois símbolos 0 e 1 por Σ₂ s₀s₁s₂ sk 0 ou 1 e consideramos a seguinte função desvio definida por σ Σ₂ Σ₂ s₀s₁s₂ s₁s₂s₃ cujo efeito é desviar a sequência para a esquerda suprimindo a primeira entrada exemplo σ0011000101 011000101 A A função σ é invertível B A função σ é sobrejetiva C A função σ é injetiva D Nenhuma das opções anteriores é verdadeira 2 Consideremos Σ₂ e σ como definidos acima Dado x Σ₂ e n N dizemos que x é um ponto periódico de período n para σ se σⁿx x Por exemplo existem dois pontos periódicos de período 1 a saber 0000 sequência só de zeros e 1111 sequência só de uns Outro exemplo de ponto periódico neste caso de período 2 é o ponto 010101 s₀ 0 s₂n1 1 e s₂n 0 onde n N Denote por Perₙσ o conjunto dos pontos periódicos de período n para σ Observe que por exemplo Per₁σ Per₂σ se for periódico de período 1 então será periódico de período 2 A n N Perₙσ 2ⁿ¹ B Se x Per₃σ então x Per₅σ C Σ₂ não possui pontos não periódicos ou seja ₙN Perₙσ Σ₂ D Nenhuma das opções anteriores é verdadeira Página 3 de 5 3 Considere agora o espaço das sequências infinitas com 5 símbolos 0123 e 4 denotado por Σ₅ e a função desvio σ definida analogamente como acima Seja A Σ₅ Per₄σ o conjunto definido pelas sequências sem dígitos pares B Σ₅ Per₄σ o conjunto definido pelas sequências sem dígitos ímpares e C B o conjunto definido pelas sequências sem dígitos iguais consecutivos A 5 A B B A C C A B Σ₅ D Nenhuma das opções anteriores é verdadeira 4 Seja Σ₂ definido acima e considere a correspondência Φ Σ₂ R s₀s₁s₂ ⁿᵢ₀ si 2i que nos fornece a escrita de um número na base binária A A sequência que está associada ao número real 38 tem apenas quatro dígitos 1 e todos os restantes 0 B Σ₂ não é um conjunto enumerável C O número ½ tem um representante em Σ₂ através da correspondência Φ D Nenhuma das opções anteriores é verdadeira Nas perguntas 5 a 8 justifique cuidadosa e detalhadamente todos os cálculos raciocínios e afirmações que efetuar 5 Considere n 4 Mostre usando indução matemática que o número de permutações de elementos de n é estritamente maior do que a cardinalidade do conjunto formado por todos os subconjuntos de n ie n Pn Página 4 de 5 6 Sejam dados os conjuntos finitos I e J onde I i e J j a Quantas funções distintas f I J é possível definir b Se j i quantas funções injetivas distintas f I J é possível definir 7 Quantos sacos diferentes de dez amêndoas se podem fazer com amên doas de quatro cores distintas 8 Três casais amigos reservaram seis lugares contíguos no cinema De quantas maneiras se podem sentar nesses lugares de forma a que ne nhum dos casais tenha os seus elementos lado a lado FIM Página 5 de 5 Resolução Matemática Discreta 1D Nenhuma das opções anteriores é verdadeira 2A n N Pernσ 2n1 3 D Nenhuma das opções anteriores é verdadeira 4 C O número 12 tem um representante em Σ2 através da correspondência Φ 5 Por indução matemática 1 Para o caso base n4 Temos que n 4 24 e P4 24 16 Como 24 16 a afirmação é verdadeira para n4 2 Suponha que a afirmação é verdadeira para um certo valor k 4 ou seja k Pk 3 Vamos mostrar que a afirmação também é verdadeira para k1 Observe que o número de permutações de k1 é k1 vezes maior do que o número de permutações de k pois podemos escolher um elemento para ser o primeiro em k1 maneiras diferentes Portanto temos que k1 k1Pk onde k1Pk é o número de permutações de k1 em que o elemento k1 é o último Agora vamos comparar k1 com Pk1 Observe que cada subconjunto de k pode ser estendido de duas maneiras diferentes para obter um subconjunto de k1 ou seja adicionando ou não o elemento k1 Portanto Pk1 2Pk pois cada subconjunto de k corresponde a dois subconjuntos de k1 Substituindo essa expressão em k1 k1Pk obtemos k1 k12Pk 2k1Pk Pk1 Portanto a afirmação também é verdadeira para k1 Concluindo por indução matemática a afirmação é verdadeira para todo n 4 6 a Para cada elemento de I podemos escolher um elemento de J para ser sua imagem Como temos j opções para cada um dos i elementos de I o número de funções distintas f I J é igual a ji b Se j i podemos escolher um elemento de J diferente para ser a imagem de cada um dos i elementos de I sem repetição de imagens pois as funções são injetivas O número de escolhas possíveis para a primeira imagem é j Para a segunda imagem temos j1 opções restantes em J j menos o elemento já escolhido para a terceira imagem temos j2 opções em J j menos os dois elementos já escolhidos e assim por diante até a iésima imagem que tem ji1 opções em J Portanto o número de funções injetivas distintas f I J é igual a j x j1 x j2 x x ji1 j ji onde denota o fatorial 7 Se temos amêndoas de 4 cores distintas e queremos fazer sacos de 10 amêndoas podemos utilizar o princípio da contagem para encontrar a resposta Para cada amêndoa em um saco existem 4 opções de cores diferentes que podemos escolher Como queremos formar sacos de 10 amêndoas teremos um total de 410 opções possíveis já que cada amêndoa pode ter 4 opções de cor No entanto a ordem em que colocamos as amêndoas no saco não importa então cada saco pode ser contado de várias maneiras diferentes dependendo da ordem das amêndoas Para evitar contar sacos diferentes que contenham as mesmas amêndoas precisamos dividir o número total de opções pelo número de maneiras diferentes que podemos arranjar as 10 amêndoas dentro do saco O número de maneiras diferentes que podemos arranjar as 10 amêndoas dentro do saco é dado por 10 ou seja o fatorial de 10 Portanto o número total de sacos diferentes que podemos fazer com amêndoas de quatro cores distintas é 410 10 Isso dá um resultado aproximado de 167960 sacos diferentes 8 Considerando a ideia de separar cada casal em duas pessoas independentes teremos 6 pessoas para sentar em 6 lugares contíguos Se considerarmos que cada pessoa pode sentar em qualquer uma das 6 cadeiras teríamos um total de 6 720 possibilidades No entanto precisamos descontar as possibilidades em que pelo menos um casal senta lado a lado Existem 3 casais e cada um tem 2 pessoas então podemos considerar que temos 3 unidades para sentar onde cada unidade é composta por 2 pessoas de um mesmo casal Como cada unidade tem 2 pessoas podemos colocálas de 2 2 maneiras diferentes Agora precisamos sentar essas 3 unidades em 6 lugares contíguos Podemos fazer isso de 4 maneiras diferentes 1 Colocar as 3 unidades nos 3 primeiros lugares e as outras 3 pessoas nos 3 últimos lugares 2 Colocar as 3 unidades nos 3 últimos lugares e as outras 3 pessoas nos 3 primeiros lugares 3 Colocar 2 unidades nos 3 primeiros lugares e a terceira unidade nos lugares 4 e 5 As outras duas pessoas vão para o último lugar 4 Colocar 2 unidades nos 4 últimos lugares e a terceira unidade nos lugares 2 e 3 As outras duas pessoas vão para o primeiro lugar Para cada uma dessas 4 maneiras podemos permutar as pessoas dentro de cada unidade de 2 pessoas de 2 maneiras Portanto o número total de maneiras de sentar as 6 pessoas de forma que nenhum casal fique lado a lado é 4 x 2 x 2 x 2 48 Portanto existem 48 maneiras diferentes para os seis amigos se sentarem de acordo com as restrições dadas