Sexta, 23 Fevereiro 2018 14:09

QUESTÕES PUC-RIO - TEOREMA DOS CASAMENTOS

Escrito por

Hoje iremos abordar o Teorema dos Casamentos, uma questão abordada em um fórum de debate matemático da Puc-Rio, de forma simples darei dois exemplos de como o Teorema pode ser aplicado na resolução de problemas.

Preparados? Então vamos a explicação:

Sejam A(1), A(2), ..., A(n) conjuntos tais que a união da quaisquer i deles

(1 <= i <= n) contém no mínimo i elementos distintos.

Então é possível  selecionar n elementos distintos, sendo um de cada conjunto.

Dem:

Indução completa em n (número de conjuntos):

n = 1: óbvio

Hipotese de Inducao: o teorema eh verdadeiro para 1 <= n <= m-1.

Consideremos m conjuntos A(1), ..., A(m) tais que a união de quaisquer k deles (1 <= i <= m) contenha pelo menos i elementos distintos.

Temos dois casos a considerar:

CASO 1:

Para cada k (1 <= k <= m-1), a união de quaisquer k conjuntos contém pelo menos k+1 elementos.

Nesse caso, escolha um elemento qualquer de A(m) - digamos "a".

Como a união dos m-1 conjuntos A(1), ..., A(m-1) contém pelo menos m elementos, a união de A(1) - {a}, ..., A(m-1) - {a} ira conter, no mínimo, m-1 elementos.

Assim, pela hipotese de inducao, podemos escolher um elemento distinto de cada um destes conjuntos.

Estes m-1 elementos, juntamente com "a", serao m elementos distintos, cada um escolhido de um dos A(i) (1 <= i <= )

CASO 2:

Existem: (i) um inteiro k (1 <= k <= m-1) e (ii) k conjuntos tais que a sua união contem exatamente k elementos.

Como 1 <= k <= m-1, podemos aplicar a hipotese de inducao e escolher um elemento distinto de cada um dos k conjuntos cuja união contem k elementos.

Suponhamos que dentre os m-k conjuntos restantes, existam j ( 1 <= j <= m-k) cuja união contenha menos do que j elementos que sejam distintos dos k elementos escolhidos acima.

Então, a união dos k conjuntos iniciais com estes j conjuntos irá conter menos do que k + j elementos, o que contradiz a hipótese do teorema sobre estes conjuntos.

Logo, dentre os m-k conjuntos restantes, a união de quaisquer j ( 1 <= j <= m-k) irá conter pelo menos j elementos e todos eles serão distintos dos k elementos escolhidos inicialmente.

Assim, podemos também aplicar a hipotese de inducao a estes m-k conjuntos e escolher um elemento distinto de cada um deles. Além do mais, podemos fazer isso de forma que estes elementos sejam distintos dos k elementos escolhidos inicialmente.

Em suma, também neste caso é possível escolher m elementos distintos, sendo um de cada um dos A(i) (1 <= i <= n)


Confira esse debate no fórum Puc-Rio: http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200304/msg00050.html

Ler 109 vezes Última modificação em Quarta, 11 Abril 2018 17:33

Deixe um comentário

Certifique-se de preencher os campos indicados com (*). Não é permitido código HTML.