Claudio, muito obrigado. Você pode me recomendar um livro que fale mais profundamente sobre números complexos?
>From: Claudio Buffara
>Reply-To: obm-l@mat.puc-rio.br
>To:
>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 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.
>
Protect your PC - Click here 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 é
=========================================================================