Re: [obm-l] Grafos e Casamentos

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

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.





----- Original Message -----
From: <peterdirichlet1985@zipmail.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Monday, March 31, 2003 2:23 PM
Subject: [obm-l] Grafos e Casamentos


> Turma,quem conhece o enunciado e a demonstraçao do Teorema dos
Casamentos?Estava
> tentando pensar nele ao ver esse problema:
>
> Numa festa ha 18 garotos e 18 garotas.Destas 36 pessoas,4 delas tem 2
amigos
> cada,16 tem 3 amigos cada e o resto tem 4 amigos cada.Qual o minimo de
casais
> amigos diferentes que pode haver na festa?
>
> Nao sei se tem algo a ver mas de qualquer modo tai.
>
>
> TEA WITH ME THAT I BOOK YOUR FACE
>
>
> ------------------------------------------
> Use o melhor sistema de busca da Internet
> Radar UOL - http://www.radaruol.com.br
>
>
>
> =========================================================================
> 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 é <nicolau@mat.puc-rio.br>
> =========================================================================

=========================================================================
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 é <nicolau@mat.puc-rio.br>
=========================================================================