Lista de Exercicios Resolvidos Matematica Discreta Permutacoes Combinacoes e Inducao

Questões 1 6 5 Para cada item abaixo justifique sua resposta de forma direta e sucinta a Quantas palavras diferentes é possível formar rearranjando as letras da palavra MATEMATICA b Partindo de Brasília de quantas formas é possível visitar 5 capitais dentre os 27 estados e voltar a Brasília c De quantas formas kn pessoas podem sentarse em k mesas circulares e distinguíveis com n lugares cada E quando as mesas não são distinguíveis d Quantos números inteiros com n dígitos existem em que quaisquer dois dígitos consecutivos não são iguais e n pessoas estão sentadas ao redor de uma mesa redonda De quantas formas podemos escolher 3 pessoas de forma que nenhuma seja vizinha das demais f De quantas formas é possível distribuir n reais a k homens e ℓ mulheres de forma que cada mulher receba ao menos um real sem insistir o mesmo para os homens 2 10 Considere a tentativa de prova que segue Afirmação nn 1 é ímpar para todo n Prova Suponha que a afirmação é verdadeira para n 1 no lugar de n provamos a afirmação para n usando tal hipótese de indução Temos que nn 1 n 1n 2n Agora n 1n é ímpar por hipótese de indução e 2n é par Logo nn 1 é a soma de um número ímpar com um número par o que é claramente ímpar A afirmação que foi provada é obviamente inválida pois para n 10 temos que 10 11 110 que é par Aponte e justifique o que há de errado com a prova apresentada 3 15 O número de Bell Bₙ é igual ao número de todas as possíveis partições não triviais de um conjunto X com n elementos assumese B₀ 1 Prove que Bₙ₁ Σₖ₀ⁿ ₖˣⁿBₖ 4 15 Uma permutação π de 2n é boa se para algum i 2n vale que πi πi 1 mod 2 n Em caso contrário π é dita ruim Prove que para cada valor de n existem mais permutações boas do que ruins Dica considere os conjuntos Pᵢ π πi πi 1 mod 2 n mostre que Pᵢ 2n2n 2 e que Pᵢ Pⱼ₁ 5 15 Seja F uma família de ksubconjuntos de um nconjunto X tal que cada ℓsubconjunto de X está contido em pelo menos um membro de F Prove que F n k 6 15 Prove que qualquer sequência com mais de pqr números reais contém uma subsequência estritamente crescente de comprimento maior que p ou uma subsequência estritamente decrescente de comprimento maior que q ou uma subsequência constante todos os elementos com mesmo valor de comprimento maior que r 12 Cheat Sheet Princípio das Casas de Pombos Se um conjunto com pelo menos rs 1 elementos é particionado em r classes então ao menos uma classe recebe ao menos s 1 elementos Princípio de InclusãoExclusão Sejam A₁ A₂ Aₘ subconjuntos não necessariamente distintos de um conjunto A Temos que A A₁ A₂ Aₘ Σ Im 1IAᵢ em que Aø A e Aᵢ ᵢᵢ Aᵢ para I m Princípio de Indução forte nos naturais Seja Pn uma proposição com n ℕ Se Pa é verdade para algum a ℕ e Pk Pn para todo natural n k a então Pn é verdade para todo natural n a A versão fraca ocorre quando k n 1 Princípio de Contagem em Duas Formas Sejam A₁ A₂ Aₘ subconjuntos de um conjunto finito X e f X ℝ Σᵢ₁ᵐ ΣₓAᵢ fx ΣₓX Σᵢₓ fx De outra forma para uma matriz A aᵢⱼ de dimensões m n Σᵢ₁ᵐ Σⱼ₁ⁿ aᵢⱼ Σⱼ₁ⁿ Σᵢ₁ᵐ aᵢⱼ Teorema de Hall Uma sequência S₁ S₂ Sₘ de conjuntos finitos não necessariamente distintos possui um sistema de representantes distintos x₁ x₂ xₘ com xᵢ Sᵢ e xᵢ xⱼ para i j se e somente se para cada k m a união de quaisquer k conjuntos possui ao menos k elementos iI Sᵢ I para todo I m Proposição de Dilworth Para qualquer ordem parcial em um conjunto P com m rs 1 elementos existe uma cadeia com r 1 elementos ou uma anticadeia com s 1 elementos ou ambos Questão 1 a Para formar palavras diferentes a partir da palavra MATEMATICA primeiro contamos a quantidade de cada letra M 2 A 3 T 2 E 1 I 1 C 1 A palavra MATEMATICA tem 10 letras então sem considerar as repetições teríamos 10 maneiras de organizálas No entanto devido às repetições dividimos pelo número de maneiras que cada letra pode ser organizada entre si para evitar contagem duplicada Isso nos dá a seguinte equação 102 3 2 1 1 1 151200 b Primeiro temos que selecionar 5 cidades das 27 disponíveis o que pode ser feito de 27 5 Para cada uma dessas seleções há 5 maneiras de visitálas porque temos 5 cidades para escolher para a primeira visita 4 para a segunda 3 para a terceira 2 para a quarta e 1 para a última No total isso nos dá 27 5 5 80730 120 9687600 formas c Se as pessoas forem sentadas em k mesas circulares e distinguíveis com n lugares cada temos que considerar que a ordem em que as pessoas se sentam em uma mesa circular não importa ou seja se todos girarem uma posição ainda será a mesma configuração Portanto para cada mesa temos n1 maneiras de organizar as pessoas Como temos k mesas teríamos n1 kmaneiras de organizar as pessoas Agora se as mesas não são distinguíveis temos que dividir pelo número de maneiras de organizar as mesas que é k Isso nos dá n1 k k maneiras de organizar as pessoas quando as mesas não são distinguíveis d Quantos números inteiros com n dígitos existem em que quaisquer dois dígitos consecutivos não são iguais Para o primeiro dígito temos 9 opções pois não queremos começar com 0 Para cada dígito subsequente temos 9 opções também pois queremos evitar que o dígito seja igual ao anterior Portanto o total de números de n dígitos em que nenhum dígito consecutivo é igual é 9 n e n pessoas estão sentadas ao redor de uma mesa redonda De quantas formas podemos escolher 3 pessoas de forma que nenhuma seja vizinha das demais Se tivermos apenas 3 pessoas haverá apenas 1 maneira de escolher pois todas elas são vizinhas Se tivermos 4 pessoas ainda haverá apenas 1 maneira de escolher pois sempre teremos pelo menos um par de pessoas que são vizinhas No caso em que temos 5 pessoas existem 5 maneiras pois podemos escolher qualquer pessoa para ser a primeira e então as outras duas pessoas devem ser escolhidas entre as duas que não são vizinhas da primeira Para n 5 escolhemos primeiro uma pessoa de n maneiras possíveis Então temos n4 maneiras de escolher a segunda pessoa e finalmente n6 maneiras de escolher a terceira pessoa totalizando nn4n6 maneiras f De quantas formas é possível distribuir n reais a k homens e l mulheres de forma que cada mulher receba ao menos um real sem insistir o mesmo para os homens Primeiro vamos garantir que cada mulher receba pelo menos um real distribuindo l reais para as l mulheres Agora temos nl reais restantes para distribuir para kl pessoas Isto pode ser feito de nlkl1 kl1 nk1 kl1 maneiras usando uma variação do princípio de estrelas e barras Questão 2 A prova apresentada está incorreta em vários pontos A base da indução não foi provada Precisamos começar provando a afirmação para um caso base por exemplo n 1 A suposição de indução está mal formulada A suposição deve ser de que a afirmação é verdadeira para algum k não para n 1 Ou seja supor que kk 1 é ímpar A etapa de indução onde tentamos provar que a afirmação é verdadeira para n com base em supor de que é verdadeira para k está logicamente incorreta Você afirma que nn 1 n 1n 2n Mas esta equação é falsa Na verdade nn 1 n 1 1n 1 n 1n 2n 1 n 1 não n 1n 2n A conclusão de que a soma de um número ímpar e um número par é ímpar está errada Na verdade a soma de um número ímpar e um número par é sempre par Finalmente e mais criticamente a afirmação está de fato incorreta nn 1 é sempre par para qualquer inteiro n porque é o produto de dois inteiros consecutivos um dos quais deve ser par Então mesmo que a estrutura da prova fosse correta a afirmação é falsa Questão 3 O número de Bell Bn conta o número de formas diferentes de se particionar um conjunto de n elementos Queremos provar que Bn1 i0 n n iBi Para provar isso usaremos o princípio de contagem em duas formas Para um conjunto com n1 elementos podemos considerar como escolhemos um elemento específico digamos x 1ª forma de contagem o número de todas as possíveis partições de um conjunto com n1 elementos é Bn1 2ª forma de contagem para cada i 0in podemos escolher um conjunto de i elementos para o conjunto que contém x Isso pode ser feito de n i maneiras Agora temos um conjunto restante de n1 i1 n i elementos que podem ser particionados de Bi maneiras Portanto o número total de partições onde o conjunto que contém x tem i1 elementos é n iBi Somando para todos i de 0 a n obtemos i0 n n iBi Assim ambas as formas de contagem devem ser iguais logo Bn1 i0 n n iBi o que completa a prova Questão 4 A afirmação do problema nos dá uma maneira de classificar permutações π de 2n como boas ou ruins e nós queremos provar que há mais permutações boas do que ruins Aqui está uma maneira de fazer isso Dada a dica devemos considerar os conjuntos Piππ iπ i1mod 2n Para um dado i existem 2n maneiras de escolher πi e πi 1 mod2 de forma que a diferença seja exatamente n Depois de escolhermos esses dois elementos existem 2n 2 maneiras de permutar os elementos restantes Então de fato Pi2n 2n2 Agora devemos mostrar que para todo iPiPi1 Observe que se uma permutação π pertence a PiPi1então πi πi 1 mod2 n e πi1 mod2 πi2 mod2 n Isso implica que πi πi2 mod2 o que é impossível para uma permutação Portanto Pie Pi1 não têm elementos em comum Existem 2n conjuntos Pi para i de 1 a 2n e eles são todos disjuntos Então o número total de permutações boas é 2nPi2n2n 2n22n2n1 Por outro lado o número total de permutações de 2n é 2n A quantidade de permutações ruins é o número total de permutações menos o número de permutações boas ou seja 2n 2n2n 1 Dado que n1 temos que 2n 1 n Portanto 2n 2n2n 1 Isso implica que o número de permutações boas é maior que o número de permutações ruins concluindo a prova Questão 5 Para resolver esse problema podemos usar o Princípio da Contagem em Duas Formas Vamos considerar todos os lsubconjuntos de X Cada um desses lsubconjuntos está contido em pelo menos um dos ksubconjuntos na família F Então podemos associar cada l subconjunto de X a pelo menos um ksubconjunto de F Agora vamos considerar essa associação do ponto de vista dos ksubconjuntos de F Cada k subconjunto de F pode conter até k i lsubconjuntos Então pelo Princípio da Contagem em Duas Formas o número total de lsubconjuntos que é n ié no máximo a soma sobre todos os ksubconjuntos em F do número de lsubconjuntos que cada um pode conter Portanto temos que n i F k i Sendo F o número de ksubconjuntos em F Então rearranjando a equação obtemos F n i k i E essa é a afirmação que queríamos provar Questão 6 Para provar esta afirmação podemos usar o Princípio das Casas de Pombos Consideremos uma sequência S com pqr 1 números reais Vamos tentar criar uma partição desta sequência em pqr classes de acordo com a seguinte regra um número da sequência é colocado em uma classe baseada na maior subsequência em que ele pode ser inserido que seja ou crescente e de comprimento máximo p ou decrescente e de comprimento máximo q ou constante e de comprimento máximo r Pela nossa regra de classificação temos no máximo pqr classes pq classes para subsequências crescentes ou decrescentes de comprimento p ou q e r classes para subsequências constantes de comprimento r Agora pelo Princípio das Casas de Pombos se temos pqr 1 elementos para distribuir entre pqr classes então pelo menos uma classe deve conter 1 1 2 elementos Isso significa que temos uma subsequência que é ou crescente e de comprimento p 1 ou decrescente e de comprimento q 1 ou constante e de comprimento r 1 Portanto qualquer sequência com mais de pqr números reais contém uma subsequência estritamente crescente de comprimento maior que p ou uma subsequência estritamente decrescente de comprimento maior que q ou uma subsequência constante de comprimento maior que r E isso prova a afirmação Questão 1 a Para formar palavras diferentes a partir da palavra MATEMATICA primeiro contamos a quantidade de cada letra M 2 A 3 T 2 E 1 I 1 C 1 A palavra MATEMATICA tem 10 letras então sem considerar as repetições teríamos 10 maneiras de organizálas No entanto devido às repetições dividimos pelo número de maneiras que cada letra pode ser organizada entre si para evitar contagem duplicada Isso nos dá a seguinte equação 102 3 2 1 1 1 151200 b Primeiro temos que selecionar 5 cidades das 27 disponíveis o que pode ser feito de 27 5 Para cada uma dessas seleções há 5 maneiras de visitálas porque temos 5 cidades para escolher para a primeira visita 4 para a segunda 3 para a terceira 2 para a quarta e 1 para a última No total isso nos dá 27 5 5 80730 120 9687600 formas c Se as pessoas forem sentadas em k mesas circulares e distinguíveis com n lugares cada temos que considerar que a ordem em que as pessoas se sentam em uma mesa circular não importa ou seja se todos girarem uma posição ainda será a mesma configuração Portanto para cada mesa temos n1 maneiras de organizar as pessoas Como temos k mesas teríamos 𝑛 1𝑘 maneiras de organizar as pessoas Agora se as mesas não são distinguíveis temos que dividir pelo número de maneiras de organizar as mesas que é k Isso nos dá 𝑛1𝑘 𝑘 maneiras de organizar as pessoas quando as mesas não são distinguíveis d Quantos números inteiros com n dígitos existem em que quaisquer dois dígitos consecutivos não são iguais Para o primeiro dígito temos 9 opções pois não queremos começar com 0 Para cada dígito subsequente temos 9 opções também pois queremos evitar que o dígito seja igual ao anterior Portanto o total de números de n dígitos em que nenhum dígito consecutivo é igual é 9𝑛 e n pessoas estão sentadas ao redor de uma mesa redonda De quantas formas podemos escolher 3 pessoas de forma que nenhuma seja vizinha das demais Se tivermos apenas 3 pessoas haverá apenas 1 maneira de escolher pois todas elas são vizinhas Se tivermos 4 pessoas ainda haverá apenas 1 maneira de escolher pois sempre teremos pelo menos um par de pessoas que são vizinhas No caso em que temos 5 pessoas existem 5 maneiras pois podemos escolher qualquer pessoa para ser a primeira e então as outras duas pessoas devem ser escolhidas entre as duas que não são vizinhas da primeira Para n 5 escolhemos primeiro uma pessoa de n maneiras possíveis Então temos n4 maneiras de escolher a segunda pessoa e finalmente n6 maneiras de escolher a terceira pessoa totalizando nn4n6 maneiras f De quantas formas é possível distribuir n reais a k homens e l mulheres de forma que cada mulher receba ao menos um real sem insistir o mesmo para os homens Primeiro vamos garantir que cada mulher receba pelo menos um real distribuindo l reais para as l mulheres Agora temos nl reais restantes para distribuir para kl pessoas Isto pode ser feito de n l k l 1 k l 1 n k 1 k l 1 maneiras usando uma variação do princípio de estrelas e barras Questão 2 A prova apresentada está incorreta em vários pontos A base da indução não foi provada Precisamos começar provando a afirmação para um caso base por exemplo n 1 A suposição de indução está mal formulada A suposição deve ser de que a afirmação é verdadeira para algum k não para n 1 Ou seja supor que kk 1 é ímpar A etapa de indução onde tentamos provar que a afirmação é verdadeira para n com base em supor de que é verdadeira para k está logicamente incorreta Você afirma que nn 1 n 1n 2n Mas esta equação é falsa Na verdade nn 1 n 1 1n 1 n 1n 2n 1 n 1 não n 1n 2n A conclusão de que a soma de um número ímpar e um número par é ímpar está errada Na verdade a soma de um número ímpar e um número par é sempre par Finalmente e mais criticamente a afirmação está de fato incorreta nn 1 é sempre par para qualquer inteiro n porque é o produto de dois inteiros consecutivos um dos quais deve ser par Então mesmo que a estrutura da prova fosse correta a afirmação é falsa Questão 3 O número de Bell Bn conta o número de formas diferentes de se particionar um conjunto de n elementos Queremos provar que 𝐵𝑛1 𝑛 𝑖 𝐵𝑖 𝑛 𝑖0 Para provar isso usaremos o princípio de contagem em duas formas Para um conjunto com n1 elementos podemos considerar como escolhemos um elemento específico digamos x 1ª forma de contagem o número de todas as possíveis partições de um conjunto com n1 elementos é 𝐵𝑛1 2ª forma de contagem para cada i 0 𝑖 𝑛 podemos escolher um conjunto de i elementos para o conjunto que contém x Isso pode ser feito de 𝑛 𝑖 maneiras Agora temos um conjunto restante de n1 i1 n i elementos que podem ser particionados de 𝐵𝑖 maneiras Portanto o número total de partições onde o conjunto que contém x tem i1 elementos é 𝑛 𝑖 𝐵𝑖 Somando para todos i de 0 a n obtemos 𝑛 𝑖 𝐵𝑖 𝑛 𝑖0 Assim ambas as formas de contagem devem ser iguais logo 𝐵𝑛1 𝑛 𝑖 𝐵𝑖 𝑛 𝑖0 o que completa a prova Questão 4 A afirmação do problema nos dá uma maneira de classificar permutações π de 2n como boas ou ruins e nós queremos provar que há mais permutações boas do que ruins Aqui está uma maneira de fazer isso Dada a dica devemos considerar os conjuntos 𝑃𝑖 𝜋 𝜋𝑖 𝜋𝑖 1𝑚𝑜𝑑2 𝑛 Para um dado i existem 2n maneiras de escolher πi e πi 1 mod2 de forma que a diferença seja exatamente n Depois de escolhermos esses dois elementos existem 2n 2 maneiras de permutar os elementos restantes Então de fato 𝑃𝑖 2𝑛2𝑛 2 Agora devemos mostrar que para todo i 𝑃𝑖 𝑃𝑖1 Observe que se uma permutação π pertence a 𝑃𝑖 𝑃𝑖1 então πi πi 1 mod2 n e πi1 mod2 πi2 mod2 n Isso implica que πi πi2 mod2 o que é impossível para uma permutação Portanto 𝑃𝑖𝑒 𝑃𝑖1 não têm elementos em comum Existem 2n conjuntos 𝑃𝑖 para i de 1 a 2n e eles são todos disjuntos Então o número total de permutações boas é 2𝑛 𝑃𝑖 2𝑛 2𝑛2𝑛 2 2𝑛 2𝑛 1 Por outro lado o número total de permutações de 2n é 2n A quantidade de permutações ruins é o número total de permutações menos o número de permutações boas ou seja 2n 2n2n 1 Dado que 𝑛 1 temos que 2n 1 n Portanto 2n 2n2n 1 Isso implica que o número de permutações boas é maior que o número de permutações ruins concluindo a prova Questão 5 Para resolver esse problema podemos usar o Princípio da Contagem em Duas Formas Vamos considerar todos os lsubconjuntos de X Cada um desses lsubconjuntos está contido em pelo menos um dos ksubconjuntos na família F Então podemos associar cada lsubconjunto de X a pelo menos um ksubconjunto de F Agora vamos considerar essa associação do ponto de vista dos ksubconjuntos de F Cada k subconjunto de F pode conter até 𝑘 𝑖 lsubconjuntos Então pelo Princípio da Contagem em Duas Formas o número total de lsubconjuntos que é 𝑛 𝑖 é no máximo a soma sobre todos os ksubconjuntos em F do número de lsubconjuntos que cada um pode conter Portanto temos que 𝑛 𝑖 F 𝑘 𝑖 Sendo F o número de ksubconjuntos em F Então rearranjando a equação obtemos F 𝑛 𝑖 𝑘 𝑖 E essa é a afirmação que queríamos provar Questão 6 Para provar esta afirmação podemos usar o Princípio das Casas de Pombos Consideremos uma sequência S com pqr 1 números reais Vamos tentar criar uma partição desta sequência em pqr classes de acordo com a seguinte regra um número da sequência é colocado em uma classe baseada na maior subsequência em que ele pode ser inserido que seja ou crescente e de comprimento máximo p ou decrescente e de comprimento máximo q ou constante e de comprimento máximo r Pela nossa regra de classificação temos no máximo pqr classes pq classes para subsequências crescentes ou decrescentes de comprimento p ou q e r classes para subsequências constantes de comprimento r Agora pelo Princípio das Casas de Pombos se temos pqr 1 elementos para distribuir entre pqr classes então pelo menos uma classe deve conter 1 1 2 elementos Isso significa que temos uma subsequência que é ou crescente e de comprimento p 1 ou decrescente e de comprimento q 1 ou constante e de comprimento r 1 Portanto qualquer sequência com mais de pqr números reais contém uma subsequência estritamente crescente de comprimento maior que p ou uma subsequência estritamente decrescente de comprimento maior que q ou uma subsequência constante de comprimento maior que r E isso prova a afirmação