- (ITA/2006) Seja U um conjunto não vazio com n elementos,
. Seja S um subconjunto de
com a seguinte propriedade:
Então, o número máximo de elementos que S pode ter é
a)
b)
, se
for par, e (
)/2 se
for ímpar
c)
d)
e)
a)
b)
c)
d)
e)
Passo 1
O enunciado diz que
é um conjunto com
elementos e que
satisfaz: para quaisquer
, ou
ou
. Ou seja,
é uma cadeia (totalmente ordenada por inclusão) no reticulado de subconjuntos de
. Vamos ver qual é o tamanho máximo de uma cadeia em
.
Passo 2
Em qualquer cadeia por inclusão, os conjuntos têm cardinais estritamente crescentes (não pode haver dois com o mesmo número de elementos, pois aí nem um conteria o outro propriamente). Como os cardinais possíveis vão de
até
, há no máximo uma escolha para cada valor de cardinalidade. Logo,
Passo 3
Para mostrar que
é atingível, basta tomar uma cadeia que passe por todos os cardinais de
a
. Por exemplo, fixe uma enumeração de
e defina
Essa família tem exatamente
conjuntos, todos comparáveis por inclusão.
Resposta
c)