Claudio, muito obrigado. Voc� pode me recomendar um livro que fale mais profundamente sobre n�meros complexos?
>From: Claudio Buffara <[EMAIL PROTECTED]>
>Reply-To: [EMAIL PROTECTED]
>To: <[EMAIL PROTECTED]>
>Subject: [obm-l] Teorema dos Casamentos
>Date: Wed, 02 Apr 2003 23:42:18 -0300
>
>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 [EMAIL PROTECTED] wrote:
>
>me intrometendo...
>
>Voc� pode me enviar a demonstra��o?
>
>Ricardo
> >From: "Cl�udio \(Pr�tica\)"
> >Reply-To: [EMAIL PROTECTED]
> >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.
>
for McAfee.com VirusScan Online
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista � <[EMAIL PROTECTED]>
=========================================================================
