[obm-l] Teorema dos Casamentos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Teorema dos Casamentos

> Caro Ricardo:
>
> Segue abaixo a demonstracao.
>
> Teorema dos Casamentos:
> 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:
> Inducao completa em n (numero de conjuntos):
>
> n = 1: obvio
>
> Hipotese de Inducao: o teorema eh verdadeiro para 1 <= n <= m-1.
>
> Consideremos m conjuntos A(1), ..., A(m) tais que a uniao 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 uniao dos m-1 conjuntos A(1), ..., A(m-1) contem pelo menos m elementos, a uniao de A(1) - {a}, ..., A(m-1) - {a} ira conter, no minimo, 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 <= m)
>
> ----------
>
> CASO 2: Existem: (i) um inteiro k (1 <= k <= m-1) e (ii) k conjuntos tais que a sua união contem exatamemente 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 uniao contem k elementos.
>
> Suponhamos que dentre os m-k conjuntos restantes, existam j ( 1 <= j <= m-k) cuja uniao contenha menos do que j elementos que sejam distintos dos k elementos escolhidos acima. 
>
> Entao, a uniao dos k conjuntos iniciais com estes j conjuntos ira conter menos do que k + j elementos, o que contradiz a hipotese do teorema sobre estes conjuntos.
>
> Logo, dentre os m-k conjuntos restantes, a uniao de quaisquer j ( 1 <= j <= m-k) ira conter pelo menos j elementos e todos eles serao distintos dos k elementos escolhidos inicialmente.
>
> Assim, podemos tambem aplicar a hipotese de inducao a estes m-k conjuntos e escolher um elemento distinto de cada um deles. Alem do mais, podemos fazer isso de forma que estes elementos sejam distintos dos k elementos escolhidos inicialmente.
>
> Em suma, tambem neste caso eh possivel escolher m elementos distintos, sendo um de cada um dos A(i) (1 <= i <= n) 
>
> *** FIM ***
>
> Um abraco,
> Claudio.

on 02.04.03 08:09, Ricardo Prins at ricardoprins@hotmail.com wrote:

> me intrometendo... 
>
> Você pode me enviar a demonstração? 
>
> Ricardo
> >From: "Cláudio \(Prática\)" 
> >Reply-To: obm-l@mat.puc-rio.br 
> >To: 
> >Subject: Re: [obm-l] Grafos e Casamentos 
> >Date: Mon, 31 Mar 2003 15:57:27 -0300 
> > 
> >Oi, JP: 
> > 
> >O enunciado do Teorema dos Casamentos é o seguinte: 
> >Sejam A(1), A(2), ..., A(n) conjuntos tais que a união da quaisquer k deles 
> >(1 <= k <= n) contém no mínimo k elementos distintos. Então é possível 
> >selecionar n elementos distintos, sendo um de cada conjunto. 
> > 
> >A demonstração padrão é por indução completa em n, e trata dois casos 
> >separadamente: 
> >i) Para cada k (1 <= k < n), a união de cada k conjuntos contém pelo menos 
> >k+1 elementos; 
> >ii) Existem k (1 <= k < n) e k conjuntos tais que a sua união tem 
> >exatamemente k elementos. 
> > 
> >Se você quiser, depois eu posso mandar a demonstração. 
> > 
> >Um abraço, 
> >Claudio.