|
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.
|