Lista de Exercicios Resolvidos - Logica Matematica e Combinatoria

1 10 Via aplicação das regras de equivalências lógicas indiqueas ié sem construir tabelas verdade mostre que a p q p q r p q r b p q p q r p q 2 10 Defina o operador nand de not and por p q p q para proposições p q Represente as operações abaixo utilizando somente este novo operador a p b p q c p q d p q e p q Conclua que é uma base completa de operadores lógicos 3 10 Determine se cada uma das expressões abaixo são satisfatíveis a p q r p q s p q s p r s p q r p r s b p q r p q s q r s p r s p q s p q r p q s p r s 4 10 Temos um conjunto V n de compostos químicos que precisam ser acondicionados em k caixas com n k 1 inteiros No entanto certos pares não ordenados de compostos descritos por E V2 não podem compartilhar uma mesma caixa sob o risco de reagirem e causarem explosões Para n e k fornecidos formule o problema acima como uma questão de satisfatibilidade de expressões proposicionais descrevendo em detalhes cada cláusula utilizada Sua descrição deve mostrar que cada solução à satisfatibilidade corresponde a uma solução de empacotamento e viceversa 5 5 Sejam B A dois conjuntos fixados com k n elementos respectivamente Determine C A C B 1 Isto é quantos subconjuntos de A possuem interseção unitária com B 6 5 Determine o número de pares ordenados A B em que A B n 7 5 Seja k 2n De quantas formas podemos distribuir k moedas idênticas a n pessoas se cada uma deve receber ao menos 2 moedas 8 5 De quantas formas podemos colocar 8 torres em um tabuleiro de xadrez 8 8 de forma que quaisquer duas delas não se ataquem 9 5 Sejam A B C três conjuntos e suponha que A C Prove que A B C A B C Forneça um exemplo que mostre que a condição A C não pode ser ignorada 10 20 Forneça provas combinatórias sem usar n choose m nmm para as relações abaixo a Para 0 k n n choose 2 k choose 2 k n k n k choose 2 b n choose k nk n 1 choose k 1 c Para 0 ℓ k n n choose k k choose ℓ n choose ℓ n ℓ choose k ℓ d k0m p choose kq choose m k p q choose m 11 5 Quantas permutações de n existem tais que nenhuma entrada é maior que ambos os seus vizinhos Nota considere que a condição é trivialmente satisfeita para as entradas mais à esquerda e mais à direita 12 5510 Para uma permutação π X X denote por πk a késima composição de π consigo mesma isto é π1 π e πk π πk1 A ordem da permutação π é o menor k 1 tal que πk id a permutação identidade que mapeia cada elemento de X a si mesmo a Determine a ordem da permutação 2 3 1 5 4 7 8 9 6 Notação a1 a2 an com ai n distintos significa que πi ai para i n b Mostre que cada permutação π de um conjunto finito possui uma ordem finita bem definida c Mostre como computar a ordem à partir dos comprimentos dos ciclos de π 13 10 Seja 𝓕 2n com n 1 tal que A B para quaisquer A B 𝓕 distintos a Mostre que 𝓕 2n1 b Construa uma coleção de exemplos em que para cada n fixado ocorre a igualdade em a a Regras de equivalências utilizadas comutatividade da disjunção lei de De Morgan e eliminação de dupla negação p V q V p q r q V p V p q r comutatividade da disjunção q V p V p q r lei de De Morgan p V q V p q r comutatividade da disjunção p V p q r V r lei de De Morgan p q r V p V r comutatividade da disjunção p V r V r lei da negação dupla p V r V r lei de negação p V r identidade da disjunção p V g V r já que g é equivalente a p pela informação fornecida no problema b Regras de equivalências utilizadas modus ponens contraposição lei de De Morgan eliminação de dupla negação p V q p q r p q r p V q contraposição p V q p q r lei de De Morgan p q p r q r lei de De Morgan p q r q r distributividade da conjunção sobre a disjunção p q r q r lei de De Morgan p q r q r distributividade da negação sobre a disjunção p q r eliminação da duplicação p g já que g é equivalente a q r pela informação fornecida no problema a p p p b p V q p q p p q q c p q p q p q p q d p q p V q p p q e p q p q q p p p q q q p Assim todas as operações lógicas podem ser representadas utilizando apenas o operador nand Dessa forma podemos concluir que é uma base completa de operadores lógicos Para determinar se cada uma das expressões é satisfatível podemos tentar encontrar uma atribuição de valores de verdade verdadeiro ou falso às proposições p q r s g que torna toda a expressão verdadeira a p V q V r p V g V s p V q V s p V r V s p V q V r p V r V s Podemos usar a tabela verdade para verificar se há uma atribuição que torna toda a expressão verdadeira No entanto como há 5 proposições a tabela verdade teria 25 32 linhas o que seria muito demorado de construir e avaliar Em vez disso podemos tentar encontrar uma solução por meio de dedução lógica Por exemplo notamos que a primeira cláusula p V q V r contém a proposição r enquanto a segunda cláusula p V g V s contém a proposição g Isso significa que para toda a atribuição de valores de verdade que torna a primeira cláusula verdadeira deve haver uma atribuição diferente que torna a segunda cláusula verdadeira Essa observação pode ser estendida às outras cláusulas No geral se uma cláusula contém uma proposição que não aparece em outra cláusula então essa proposição deve ser verdadeira ou falsa para que a cláusula seja verdadeira Portanto se não houver atribuição de valores de verdade que satisfaça todas as cláusulas isso significará que a expressão não é satisfatível Podemos fazer uma verificação mais detalhada das cláusulas A primeira cláusula p V q V r é verdadeira se r for verdadeira independentemente dos valores de p e q A segunda cláusula p V g V s é verdadeira se g for verdadeira e nem s nem p forem verdadeiros A terceira cláusula p V q V s é verdadeira se p for verdadeira e nem q nem s forem verdadeiros A quarta cláusula p V r V s é verdadeira se nem p nem r nem s forem verdadeiros A quinta cláusula p V q V r é verdadeira se p e q forem verdadeiros e r for falso A sexta cláusula p V r V s é verdadeira se p for verdadeira e nem r nem s forem verdadeiros Podemos agora tentar combinar essas cláusulas para encontrar uma atribuição de valores de verdade que satisfaça todas elas Por exemplo se assumirmos que p é verdadeiro então a terceira cláusula é verdadeira e a sexta cláusula é verdadeira o que significa que r é falso Isso por sua vez implica que a quinta cláusula é falsa pois p e q são verdadeiros e r é falso No entanto a primeira cláusula ainda precisa ser satisfeita o que significa que r deve ser verdadeiro Mas isso entra em conflito com a segunda cláusula que exige que g seja verdadeiro e s e p sejam falsos Portanto não há atribuição de valores de verdade que satisfaça todas as cláusulas o que significa que a expressão não é satisfatível b p V q V r p V q V s g V r V s p V r V s p V g V s p V q V r p V q V s p V r V s Podemos usar a mesma abordagem para verificar se esta expressão é satisfatível Primeiro analisamos cada cláusula A primeira cláusula p V q V r é verdadeira se pelo menos uma das proposições p q ou r for verdadeira A segunda cláusula p V q V s é verdadeira se p for verdadeira e nem q nem s forem verdadeiros A terceira cláusula g V r V s é verdadeira se pelo menos uma das proposições g r ou s for verdadeira A quarta cláusula p V r V s é verdadeira se pelo menos uma das proposições r ou s for verdadeira e p for falso A quinta cláusula p V g V s é verdadeira se pelo menos uma das proposições g ou s for verdadeira e p for falso A sexta cláusula p V q V r é verdadeira se p for verdadeira e pelo menos uma das proposições q ou r for verdadeira A sétima cláusula p V q V s é verdadeira se pelo menos uma das proposições p q ou s for verdadeira A oitava cláusula p V r V s é verdadeira se pelo menos uma das proposições p r ou s for verdadeira Podemos agora tentar combinar essas cláusulas para encontrar uma atribuição de valores de verdade que satisfaça todas elas Uma atribuição possível é p verdadeiro q falso r falso s verdadeiro g falso Com essa atribuição todas as cláusulas são verdadeiras o que significa que a expressão é satisfatível Portanto a resposta para a expressão b é que ela é satisfatível Para formular o problema de acondicionamento de compostos químicos em caixas como uma questão de satisfatibilidade de expressões proposicionais podemos utilizar variáveis booleanas para representar se um composto está presente ou não em uma determinada caixa Seja Xi j a variável que representa se o composto i está presente na caixa j de forma que Xi j1indica que o composto i está na caixa j e Xi j0 indica o contrário Agora para garantir que pares de compostos descritos por E não compartilhem uma mesma caixa podemos adicionar cláusulas que proíbam a atribuição de valores verdadeiros para as variáveis que representam esses pares em um mesmo j Uma forma de fazer isso é utilizar a seguinte cláusula para cada par i j em E Xi jv X j k Ou seja a cláusula a cima indica que se os compostos i e j estiverem em uma mesma caixa então o composto j e um outro composto k que pode ser qualquer outro composto exceto i não podem estar na mesma caixa Para garantir que cada composto seja acondicionado em uma única caixa devemos adicionar cláusulas que garantam que cada composto i esteja presente em exatamente uma caixa Uma forma de fazer isso é utilizar a seguinte cláusula para cada i Xi1V Xi 2V V Xik Xi1V Xi 2 Xi1V Xi3 X ik1V Xik A cláusula acima indica que o composto i deve estar presente em pelo menos uma caixa e que ele não pode estar presente em mais de uma caixa As cláusulas que relacionam a negação das variáveis em diferentes caixas garantem que o composto i não possa estar presente em mais de uma caixa ao mesmo tempo Assim a satisfatibilidade das cláusulas acima garante que existe um empacotamento possível que não leva a reações perigosas entre compostos químicos Por sua vez se uma solução de empacotamento é possível as variáveis booleanas podem ser atribuídas de forma que as cláusulas são satisfeitas Portanto cada solução à satisfatibilidade correspondente a uma solução de empacotamento e viceversa Vamos começar observando que para um elemento x de B existem exatamente nk elementos em A que não pertencem a B Portanto para um subconjunto C de A C B 1 se e somente se C contém exatamente um elemento de B e nk1 elementos que não pertencem a B Assim o número de subconjuntos de A que têm interseção unitária com B é igual ao número de maneiras de escolher um elemento de B e nk1 elementos que não pertencem a B Isso pode ser feito em k 1 nk nk1knk1maneiras Portanto o número de subconjuntos de A com intersecção unitária com B é knk1 Para determinar o número de pares ordenados AB em que A Bn podemos observar que Existem 2 n subconjuntos de n Para cada elemento i em n ele pode estar ou não estar em A e em B Portanto existem 2 24 possibilidades para cada elemento i Como A é um subconjunto de B para cada elemento i em n se i pertence a B então ele também deve pertencer a A Isso significa que se decidirmos incluir i em B não podemos escolher não incluir i em A Com base nessas observações podemos contar o número de pares ordenados AB da seguinte maneira Para cada subconjunto de n podemos escolher quais elementos estarão em A Isso pode ser feito de 2 nmaneiras Para cada elemento i em n temos 3 possibilidades i não está em B i está em B mas não em A i está em B e em A Portanto para cada subconjunto de n existem 3 n maneiras de escolher quais elementos estão em B considerando que cada elemento tem 3 possibilidades Como A é um subconjunto de B se um elemento está em B e em A ele é automaticamente escolhido como um elemento de A Portanto para cada subconjunto de n a escolha de B determina a escolha de A Portanto o número total de pares ordenados AB é 2 n3 n Podemos resolver este problema usando o princípio da inclusãoexclusão Primeiro considere a quantidade de maneiras de distribuir k moedas idênticas para n pessoas sem restrições Isso é simplesmente kn1 n1 ou seja escolher n1 posições para as divisões entre as moedas Agora queremos subtrair o número de maneiras em que pelo menos uma pessoa recebe menos de 2 moedas Existem n maneiras de escolher uma pessoa que recebe menos de 2 moedas e k2n1 maneiras de distribuir as moedas restantes para as outras pessoas note que subtraímos 2 moedas de cada uma dessas pessoas No entanto ao subtrair essas quantidades contamos duas vezes as maneiras em que duas ou mais pessoas recebem menos de 2 moedas Precisamos adicionálos de volta ao nosso total Existem n 2 maneiras de escolher duas pessoas que recebem menos de 2 moedas e k4n2 maneiras de distribuir as moedas restantes para as outras pessoas Continuando com o princípio da inclusãoexclusão obtemos a seguinte fórmula para o número de maneiras de distribuir k moedas idênticas para n pessoas cada uma recebendo pelo menos 2 moedas kn1 n1 nk2n1 n 2k4 n2 Substituindo k 2n nesta fórmula obtemos a resposta final kn1 n1 n k2n 1 n 2k4n2 kn1 n1 n k2n1 n 2k4 n2 Podemos simplificar ainda mais essa fórmula Primeiro observe que n 2n n1 2 Podemos substituir isso na fórmula kn1 n1 nk2n1 n n1 2 k4n2 kn1 n1 nknn1 Portanto o número de maneiras de distribuir k moedas idênticas para n pessoas cada uma recebendo pelo menos 2 moedas onde k 2n é kn1 n1 nknn1 Para que duas torres não se ataquem elas não podem estar na mesma linha horizontal na mesma linha vertical e nem na mesma diagonal Podemos começar colocando a primeira torre em qualquer uma das 64 casas do tabuleiro Em seguida a segunda torre não pode ser colocada em nenhuma das casas que estejam na mesma linha horizontal na mesma linha vertical ou na mesma diagonal que a primeira torre Como há 8 colunas e 8 linhas e cada torre ataca todas as casas em sua linha horizontal e em sua linha vertical há 14 casas proibidas na horizontal e 14 casas proibidas na vertical incluindo a casa da primeira torre Além disso há 13 casas proibidas em cada uma das diagonais da primeira torre Portanto há 64 14 14 13 13 10 casas possíveis para a segunda torre Para a terceira torre há ainda menos casas possíveis pois ela não pode estar em nenhuma das casas que já estão em uma linha horizontal linha vertical ou diagonal com as duas primeiras torres Assim o número de casas possíveis para a terceira torre é ainda menor do que para a segunda torre Continuando esse processo para cada uma das 8 torres o número total de disposições possíveis é 10 x 8 x 6 x 5 x 3 x 2 x 1 x 1 28800 Portanto há 28800 maneiras de colocar 8 torres em um tabuleiro de xadrez de forma que quaisquer duas delas não se ataquem Para provar que ABC ABC precisamos mostrar que qualquer elemento que está em ABC também está em ABC e viceversa Vamos começar mostrando que qualquer elemento em ABC também está em ABC Se x está em ABC então x está em A ou x está em BC Se x está em A então x está em AB e também está em C já que A está contido em C Portanto x está em ABC Se x está em BC então x está em B e x está em C Portanto x está em ABC Portanto qualquer elemento em ABC também está em ABC Agora vamos mostrar que qualquer elemento em ABC também está em ABC Se x está em ABC então x está em C e x está em AB Se x está em A então x está em ABC Se x está em B então x está em BC e portanto x está em ABC Portanto qualquer elemento em ABC também está em ABC Assim mostramos que ABC ABC Agora para fornecer um exemplo que mostra que a condição A C não pode ser ignorada podemos considerar os conjuntos A 1 2 3 B 2 3 4 C 1 2 3 4 Neste exemplo temos A C mas ainda assim ABC e ABC não são iguais ABC 1 2 3 4 pois BC 2 3 e A2 34 1 2 3 4 ABC 1 2 3 pois AB 1 2 3 4 e 1 2 3 4C 1 2 3 a Podemos provar essa relação usando o princípio da contagem e a identidade binomial Vamos considerar um conjunto de n elementos e escolher dois deles para formar um par O número de maneiras de escolher dois elementos distintos de um conjunto de tamanho n é dado por n escolher 2 que pode ser escrito como n 2n2 Por outro lado podemos contar o número de pares de elementos escolhidos de duas maneiras diferentes Primeiro podemos escolher k elementos do conjunto de tamanho n e escolher dois deles para formar um par O número de maneiras de fazer isso é k escolher 2 que pode ser escrito como k 2k2 Então existem k k1 2 maneiras de escolher um par de k elementos Em segundo lugar podemos escolher dois elementos do conjunto de tamanho n sem considerar de qual subconjunto eles são escolhidos O número de maneiras de fazer isso é n escolher 2 que é o mesmo valor que calculamos anteriormente Agora podemos igualar esses dois valores para obter a relação desejada k k1 2 nk nk1 2 n n1 2 Simplificando obtemos k nk n 2 nk 2 k 2 Portanto temos n 2 k 2k nk nk 2 Essa é a relação que queríamos provar b Considere um conjunto de n elementos e queremos escolher k deles O lado esquerdo da equação n k representa o número de maneiras de escolher k elementos de um conjunto de n elementos ou seja o número de ksubconjuntos de um conjunto com n elementos Podemos calcular isso da seguinte maneira primeiro escolhemos um elemento para ser o primeiro do subconjunto há n maneiras de fazer isso em seguida escolhemos k1 elementos restantes do conjunto de n1 elementos restantes há n1 k1maneiras de fazer isso Portanto temos n kn n1 k1 O lado direito da equação é dado por nk n1 k1Podemos ver que o termo n k é o resultado de dividir o número de maneiras de escolher um elemento do conjunto de n elementos pelo número total de maneiras de escolher k elementos Em seguida o termo n1 k1 representa o número de k1subconjuntos do conjunto de n1 elementos restantes após a escolha do primeiro elemento Agora para provar a relação podemos mostrar que os dois lados da equação acima são iguais n kn n1 k1equação1 n kn k n1 k1equação2 Multiplicando a equação 2 por k temos k nkn n1 k1 Substituindo a equação 1 na equação acima temos k n1 k1n n1 k1 Isso pode ser simplificado para n1 k1n k n1 k1 Portanto os dois lados da equação são iguais e a relação é verdadeira Essa é uma prova combinatória porque mostramos que ambos os lados da equação representam a contagem do mesmo número de objetos ou eventos usando argumentos baseados em combinações ou escolhas de elementos de conjuntos c Podemos pensar em escolher dois subconjuntos disjuntos de um conjunto com n elementos O primeiro subconjunto tem k elementos e o segundo subconjunto tem l elementos Podemos contar o número de maneiras de fazer isso de duas maneiras diferentes e igualar as expressões resultantes Por um lado podemos escolher primeiro o subconjunto maior com k elementos e em seguida escolher um subconjunto menor com l elementos a partir dos elementos restantes Existem n k maneiras de escolher o subconjunto maior e k l maneiras de escolher o subconjunto menor Assim o número total de maneiras de escolher dois subconjuntos disjuntos é n k k l Por outro lado podemos escolher primeiro o subconjunto menor com l elementos e em seguida escolher um subconjunto maior com k elementos a partir dos elementos restantes Existem n l maneiras de escolher o subconjunto menor e nl kl maneiras de escolher o subconjunto maior Assim o número total de maneiras de escolher dois subconjuntos disjuntos é n l nl kl Como as duas expressões contam o mesmo número de maneiras de escolher dois subconjuntos disjuntos elas devem ser iguais Portanto temos a relação desejada n k k l n l nl kl d Uma prova combinatória para a identidade k0 m p k q mk pq m é fornecida pelo Teorema do Binômio de Newton Considere pq m que representa o número de maneiras de escolher m elementos de um conjunto com p q elementos Podemos expandir essa expressão usando o Teorema do Binômio de Newton pq m k0 m m k p kq mk Aqui m k representa o coeficiente binomial que conta o número de maneiras de escolher k elementos de um conjunto com m elementos Podemos reescrever o coeficiente binomial m k como um produto de coeficientes binomiais menores m k pq1 k1 pq1 k Substituindo isso na equação anterior temos pq m k0 m pq 1 k1 pq1 k p kq mk Reorganizando os termos obtemos pq m k0 m p k q mk pq 1 k1 pq1 k Agora usamos a identidade n k1 n k k nk1 Substituindo isso na equação anterior obtemos pq m k0 m p k q mk k pqk Multiplicando ambos os lados por pq temos pq m1pq k0 m p k q mk k pqk Agora usamos o fato de que a derivada do lado esquerdo é igual a m1 pq m enquanto a derivada do lado direito é pq k0 m p k q mk pq pqk 2 Igualando as duas derivadas obtemos m1pq mpq k 0 m p k q mk k pqk 2 Dividindo ambos os lados por pq m temos m1 pq pq k0 m p k q mk k pqk 2 Finalmente chegamos à identidade desejada k0 m p k q mk pq m k0 m p k q mk k pqk 2 Que é uma expressão combinatória para a identidade original k0 m p k q mk pq m Essa prova combinatória usa o Teorema do Binômio de Newton e algumas propriedades dos coeficientes binomiais para derivar a identidade desejada a partir da expansão de pq m A identidade relaciona o número de maneiras de escolher k elementos de um conjunto com p elementos e mk elementos de um conjunto com q elementos ao número total de maneiras de escolher m elementos de um conjunto com pq elementos A expressão final envolve uma soma ponderada dessas contagens que é expressa em termos de k pqk 2 Essas permutações são chamadas de permutações estritamente crescentes ou permutações 132 pois a condição pode ser reescrita como não há subsequência 132 onde 1 é o menor número 3 é o maior e 2 é o número do meio O número de permutações estritamente crescentes de n é dado pelo nésimo número de Catalan Cn que tem a seguinte fórmula Cn 2n nn1 Por exemplo para n 3 temos C3 23 331720 624 5 As cinco permutações estritamente crescentes de 3 são 1 2 3 1 3 2 2 1 3 3 1 2 3 2 1 Para n 4 temos C4 24 4 41 70 Existem 70 permutações estritamente crescentes de 4 a Para encontrar a ordem da permutação 2 3 1 5 4 7 8 9 6 precisamos encontrar o menor k tal que π kid onde π é a permutação dada e id é a permutação identidade Começamos calculando as primeiras potências de π π 22135 47896 π 3321458967 π 413254 9678 π 5213456789 π 61235 46897 π 7312459786 π 82315 47896 Observe que π 61235 46897 e π 82315 47896 são iguais à permutação original π Portanto a ordem da permutação π é 8 b Para mostrar que cada permutação π de um conjunto finito possui uma ordem finita bem definida observe que existem apenas um número finito de maneiras de rearranjar os elementos do conjunto Além disso como π é uma bijeção ela deve levar cada elemento para um outro elemento do conjunto e não pode haver elementos sobrando ou faltando Portanto cada aplicação de π a partir de um elemento resulta em uma nova permutação que é diferente da original e eventualmente chegaremos à permutação identidade que é a permutação original aplicada k vezes Como existem apenas um número finito de permutações eventualmente chegaremos a uma permutação que já foi vista antes e a ordem da permutação será finita c Podemos calcular a ordem da permutação π à partir dos comprimentos dos ciclos de π Observe que a ordem de um ciclo de comprimento k é k já que aplicar o ciclo k vezes resulta na permutação identidade Além disso uma permutação pode ser decomposta em ciclos disjuntos Portanto se os comprimentos dos ciclos disjuntos de π são k 1k2k m então a ordem de π é o mínimo múltiplo comum mmc de k 1k2k m Isso ocorre porque aplicar π um número de vezes que não é um múltiplo do mmc não resultará na permutação identidade Podemos usar o algoritmo de Euclides para calcular o mmc de k 1k2k m Para calcular o mmc de k 1k2k m começamos encontrando o máximo divisor comum mdc de k 1e k2 usando o algoritmo de Euclides mdc k1k 2k3mdc k1mdc k2k 3 Continuamos até que tenhamos o mdc de todos os comprimentos dos ciclos disjuntos Então o mmc é dado por mmc k1k2km k1k2k m mdc k1k2km Por exemplo considere a permutação π 2 4 1 6 53 7 Os ciclos disjuntos são 2 4 6 5 1 e 3 7 com comprimentos 5 e 2 respectivamente O mdc de 5 e 2 é 1 então o mmc é dado por mmc 52 52 1 10 Portanto a ordem da permutação π é 10 Podemos verificar isso calculando as potências de π até chegar na permutação identidade π 22156 4 π 325461 π 424651 π 51256 4 π 615462 π 714 652 π 816254 π 912465 π 101526 4 π 1116524 π 1212654 Portanto a ordem de π é 10 como esperado a Vamos provar por indução em n que se f 2 n é uma coleção de conjuntos binários distintos que possuem interseção não vazia dois a dois então f 2 n1 Para o caso base n 1 temos que f 0 ou f 1 e em ambos os casos f22 0 Agora vamos supor que a afirmação é verdadeira para n1 e provar para n Seja f 2 n uma coleção de conjuntos binários distintos que possuem interseção não vazia dois a dois Vamos considerar o conjunto X01 n1 de todos os possíveis elementos de tamanho n1 Para cada x X vamos definir o conjunto Ax2 n como o conjunto de todos os elementos que começam com x Formalmente Axx y y 2 n1 Note que Ax2 n1 pois há 2 escolhas para cada posição dos elementos de y Vamos mostrar que dois elementos distintos de f não podem começar com o mesmo elemento x X Suponha por contradição que existem Axe A y em f com x y Como Axe A y têm interseção não vazia deve existir algum elemento z que está em ambos Sem perda de generalidade podemos supor que o primeiro bit de z é 0 caso contrário basta trocar x e y Então z A xe z A y o que implica que z x vy w para alguns vw2 n1 Mas isso significa que xy w e como x e y têm o mesmo tamanho w deve começar com 1 No entanto isso implica que w A y e portanto zy w A y uma contradição Como f consiste de conjuntos que começam com cada elemento de X e dois conjuntos distintos não podem começar com o mesmo elemento de X concluímos que f X2 n1 Isso conclui a prova por indução b Para construir um exemplo em que ocorre a igualdade em a vamos considerar n 2 Seja f 0 1 01 É fácil verificar que f é uma coleção de conjuntos binários distintos que possuem interseção não vazia dois a dois Além disso f 42 21 como esperado