Exercício Resolvido 2: (ITA 2006) Seja U um conjunto não vazio com n elementos, ≥n 1 . Seja S um subconjunto de P(U) com a seguinte propriedade: ∈ ...

Para resolver esse exercício, vamos analisar a propriedade que o conjunto S possui. Temos que se A está em S, então todo subconjunto de A ou A complementar está em S. Além disso, se A e B estão em S, então A intersecção B e A união B também estão em S. Vamos considerar o caso em que n é par. Se S contém um conjunto A com n/2 elementos, então S não pode conter nenhum subconjunto de A ou A complementar, pois ambos têm n/2 elementos. Portanto, S só pode conter conjuntos com menos de n/2 elementos. Como existem 2^n subconjuntos de U, e cada subconjunto com k elementos contribui com (n k) subconjuntos para S, temos que o número máximo de elementos em S é a soma dos coeficientes binomiais (n k) para k variando de 0 a n/2-1. Essa soma é igual a 2^(n-1), então a alternativa correta é a letra d) 2n-1. Para o caso em que n é ímpar, podemos considerar um conjunto A com (n+1)/2 elementos. Da mesma forma que antes, S não pode conter nenhum subconjunto de A ou A complementar. Além disso, S não pode conter nenhum conjunto com (n-1)/2 elementos, pois esse conjunto contém um subconjunto de A complementar com (n+1)/2 elementos. Portanto, S só pode conter conjuntos com menos de (n-1)/2 elementos ou mais de (n+1)/2 elementos. A soma dos coeficientes binomiais correspondentes é novamente 2^(n-1), então a alternativa correta é novamente a letra d) 2n-1.