|
Caro Paulo Santa Rita:
Eis aqui um resumo da discuss�o at� agora sobre o problema de
Conway:
O PROBLEMA:
Dados um conjunto X com N elementos e M subconjuntos pr�prios de X tais que
cada par (n�o ordenado) de elementos de X pertence a exatamente um destes
subconjuntos, prove que M >= N.
AS SUAS DUAS PISTAS:
LEMA 1: Para todo "a" pertencente a X, se R(a) � o n�mero
de subconjuntos que cont�m "a", ent�o 2 <= R(a) < M.
LEMA 2: Se A(i) � um dos subconjuntos dados e "a" n�o pertence a A(i),
ent�o R(a) > |A(i)|.
J� concordamos que estes dois lemas podem ser provados sem muita
dificuldade. O grande m�rito do Conway foi perceber que estes eram
os fatos relevantes para a solu��o do problema.
O que eu fiz em seguida foi inventar mais dois lemas (apesar de n�o ter
conseguido demonstrar o segundo).
Seja X = { 1, 2, ..., N } e sejam A(1), A(2), ..., A(M) os subconjuntos
pr�prios de X.
LEMA 3:
R(1) + R(2) + ... + R(N) = |A(1)| + |A(2)| + ... + |A(M)|
DEM:
Contar de duas formas o n�mero de pares ordenados ( i , A(j) ), 1
<= i <= N e 1 <= j <= M, tais que "i" pertence a A(j).
(i) Para cada "i", existem R(i) subconjuntos A(j) tais que "i"
pertence a A(j).
Assim, o n�mero de pares ordenados � igual a R(1) + R(2) + ... +
R(N);
(ii) Para cada "j", o subconjunto A(j) possui | A(j) | elementos.
Assim, o n�mero de pares ordenados � igual a |A(1)| + |A(2)| + ... +
|A(M)|.
Essa id�ia de contar pares ordenados eu tirei de um problema sobre o
princ�pio das gavetas (dados 2^(N-1) + 1 subconjuntos de um conjunto de N
elementos, existem dois destes subconjuntos tais que um � uma parte pr�pria
do outro)
********
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:
Como, para todo j, A(j) � um subconjunto PR�PRIO de X, sempre ser� poss�vel
escolher um elemento x(j) tais que x(j) n�o pertence a A(j).
Resta, portanto, mostrar que os x(j) podem ser escolhidos distintos dois a
dois, e foi aqui que eu me compliquei....mas tenho a sensa��o de que o resultado
� verdadeiro. Acho que em algum lugar pode entrar o LEMA 1 ( 2 <= Ra < M
).
********
De posse destes 4 lemas (supondo, � claro, que o �ltimo seja realmente
verdadeiro), a demonstra��o do teorema pode ser conclu�da por contradi��o:
Suponhamos que M < N.
A partir do LEMA 4, supondo escolhidos os M elementos distintos de X (
x(1) , x(2), ..., x(M) ), tais que x(j) n�o pertence a A(j), 1 <= j <= M,
formamos a soma:
R(x(1)) + R(x(2)) + ... + R(x(M)), a qual, pelo LEMA 2, � maior do que
|A(1)| + |A(2)| + ... + |A(M)|.
Por outro lado, temos naturalmente:
R(1) + R(2) + ... + R(N) > R(X(1)) + R(x(2)) + ... + R(x(M)), j� que,
por hip�tese, M < N, e pelo LEMA 1, R(i) >= 2 para cada "�".
Ou seja: R(1) + ... + R(N) > |A(1)| + ... + |A(M)|, o que contradiz
o LEMA 3.
Assim, somos for�ados a concluir que M >= N.
Coment�rios ser�o muito bem vindos.
Um abra�o,
Claudio Buffara.
|