© Seja
um conjunto com
. Prove que se
é ímpar, então para todo
e
tem paridades diferentes e que portanto, a aplicação
é uma bijeção da coleção de subconjuntos de
de cardinalidade par para a coleção de subconjuntos de
de cardinalidade ímpar.
Passo 1
Beleza, vamos resolver esse exercício juntos! O problema fala sobre conjuntos e suas contagens. A gente tem um conjunto
com
, onde
é ímpar. A gente precisa provar duas coisas:
- Para todo subconjunto
de , os tamanhos de e de seu complementar têm paridades diferentes (ou seja, um tem tamanho par e o outro ímpar). - A aplicação
cria uma correspondência um a um (bijeção) entre todos os subconjuntos de com tamanho par e os com tamanho ímpar.
Vamos precisar entender conceitos básicos de conjuntos, complementos e paridade de números.
Passo 2
Primeiro, vamos entender o que significa o complementar de
, que é
. O complementar
contém todos os elementos de
que não estão em
. Matematicamente, isso é escrito como:
Isso nos ajuda a relacionar os tamanhos de
e
.
Passo 3
Sabemos que o total de elementos em
é
, então:
Como
é ímpar, queremos mostrar que
e
t��m paridades diferentes.
Passo 4
Vamos supor que
seja par. Então, podemos escrever
para algum inteiro
. Então:
Como
é ímpar e
é par, a diferença
será ímpar.
Agora, se
for ímpar, ou seja,
, então:
Como
é ímpar,
é par, e subtraindo
(que também é par) o resultado será par.
Passo 5
Portanto, mostramos que se
é par, então
é ímpar, e vice-versa. Isso significa que a aplicação
troca subconjuntos de par cardinalidade para ímpar e de ímpar para par.
Passo 6
Para mostrar que
é uma bijeção, precisamos mostrar que ela é injetora e sobrejetora.
-
Injetora: Se
, então . Tomando o complementar de ambos os lados, temos . Então, é injetora. -
Sobrejetora: Para qualquer subconjunto
com cardinalidade ímpar, existe um subconjunto com cardinalidade par tal que . Então, é sobrejetora.
Assim,
é uma bijeção.
Resposta
A aplicação
é uma bijeção entre os subconjuntos de
com cardinalidade par e os de cardinalidade ímpar quando
é ímpar.
Exercícios relacionados
(a) Seja
. Quantos subconjuntos de
contém o elemento
?
Calcule a quantidade de maneiras de colocar em um tabuleiro de xadrez dois bispos que não se ameacem.
Temos 20 presentes que podem ser distribuídos para 12 crianças. Não é exigido que toda criança obtenha algo: poderia acontecer de darmos todos os presentes à mesma criança. De quantas maneiras podemos distribuir os presentes?
© Quantos subconjuntos de um conjunto
com
elementos contém um elemento dado?