[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Ainda Sylvester / Conway



Title: Help
Caro Paulo Santa Rita:
 
Andei pesquisando um pouco ontem � noite e esbarrei num resultado que pode demonstrar o lema 4 e, portanto, completar a demonstra��o do teorema de Conway. Trata-se do TEOREMA DOS CASAMENTOS, que diz o seguinte:
 
"Sejam B(1), B(2), ..., B(M) conjuntos tais que a uni�o da quaisquer k deles (1 <= k <= M) cont�m no m�nimo k elementos distintos. Ent�o � poss�vel selecionar M objetos distintos, sendo um de cada conjunto"
 
Seja X = { 1, 2, ..., N } e sejam A(1), A(2), ..., A(M) subconjuntos pr�prios de X tais que cada par (n�o ordenado) de elementos de X pertence a exatamente um destes subconjuntos.
 
LEMA 4:
Se M <= N, ent�o � poss�vel escolher M elementos DISTINTOS de X (digamos x(1), x(2), ..., x(M) ) tais que, x(j) n�o pertence a A(j), 1 <= j <= M. 
 
DEM:
Para cada j, 1 <= j <= M, defina B(j) = X - A(j).  Como cada A(j) � pr�prio, B(j) <> vazio.
A id�ia � provar que os B(j) satisfazem �s condi��es do TEOREMA DOS CASAMENTOS.
 
Dado k, com 1 <= k <= M, seja I um subconjunto qualquer de { 1, 2, ..., M } com k elementos.
 
Pela defini��o de B(j), e levando em conta que A(j) e B(j) s�o subconjuntos de X, teremos:
 
UNI�O B(j)  =  UNI�O [ X - A(j) ]   =   X  -  INTERSE��O A(j) 
   j em I                 j em I                                          j em I
 
Se k = 1, ent�o, como cada B(j) � n�o vazio, naturalmente cont�m 1 ou mais elementos.
 
Se k = M, ent�o I = { 1, 2, ..., M }. Assim, INTERSE��O A(j) = vazio.
                                                                          j em I                               
Caso contr�rio, existiria "a" em X tal que R(a) = M, em contradi��o ao LEMA 2.
 
Assim, | UNI�O B(j) | = | X | = N >= M.
                  j em I 
 
Finalmente, se 2 <= k <= M-1, ent�o como cada par de elementos de X est� contido num �nico A(j), temos que, quisquer que sejam i e j, com 1 <= i < j <= M, a interse��o de A(i) e A(j) � vazia ou unit�ria.
 
Assim, se I tem 2 ou mais elementos, ent�o INTERSE��O A(j) � vazia ou unit�ria.
                                                                         j em I
 
Conclus�o: | UNI�O B(j) | >= N - 1 >= M - 1 >= k.
                       j em I
 
Assim, os B(j), 1 <= j <= M, satisfazem �s condi��es do TEOREMA DOS CASAMENTOS. Portanto, existem M elementos distintos x(1), ..., x(M) tais que x(j) pertence a B(j), 1 <= j <= M.
 
Como, para cada j, B(j) = X - A(j), conclu�mos que existem M elementos distintos x(1), ..., x(M), pertencentes a X, tais que, para cada j, x(j) n�o pertence a A(j) e o LEMA 4 est� provado.
***********
 
Agora, resta esperar para ver a demonstra��o "m�gica", de 1 linha, que o Conway deu para o teorema original.
 
Um abra�o,
Claudio Buffara.