Olá pessoas!
Alguem se lembra daquele problema da Cone Sul?
Aqui uma pequena modificacao:
"
Preencher uma matriz n por n com os elementos de {-1,0,1}
tal que o conjunto das somas dos elementos
de cada uma das filas tenha 2n elementos
(todos diferentes, pela definicao de conjunto :P)
"
Bem, é particularmente fácil resolver este problema para n par (uma inducao
simplezinha...)
A parte que está me enchendo a paciência é demonstrar que nao funciona para
os ímpares.
Eu reuni alguns resultados (quem ainda esta pensando e nao quer ver, pare de
ler aqui!)
Enfim...
Algumas coisas sao faceis de prever no caso n ímpar...
Seja n=2k+1.
As possíveis somas vao desde 1+1+1+...+1=n até -1-1-1-...-1=-n,
um total de 2n+1 elementos (lembre-se do zero!). Chamemos este confunto de
X[n]
Como sao 2n filas, isto significa que um e só um dos elementos de X[n] nao
aparece.
Como o problema é "invariante" se multiplicarmos os elementos da matriz por
-1, podemos supor que n aparece como uma das somas.
Se o 0 aparecesse como uma das somas, temos um absurdo. De fato, a soma das
somas das linhas é igual a soma da soma das colunas. Logo a soma das somas
de todas as filas
é par. Mas se o 0 aparece e o n aparecem, temos que o -n nao aparace, e a
soma dos elementos é n (os diferentes de 0 se cancelam), um numero impar.
Logo o 0 nao aperece, ou seja, os numeros 1,2,...,n e os seus opostos
aparecem nas somas das filas.
Podemos nos aproveitar da comutatividade e fixar alguns valores. Por
exemplo, vendo o caso n=5, podemos supor que o 5 é a soma da primeira linha
(caso contrario e so trocar linhas e colunas!):
1 1 1 1 1
a b c d e
f g h i j
k l m n o
p q r s t
Mas aí é fácil ver que o -5 só pode ir embaixo do 5:
1 1 1 1 1
-1 -1 -1 -1 -1
f g h i j
k l m n o
p q r s t
E o 4 teria que vir logo depois:
1 1 1 1 1
-1 -1 -1 -1 -1
1 1 1 1 0
k l m n o
p q r s t
O -4 viria abaixo, mas temos que ver dois casos:
1 1 1 1 1
-1 -1 -1 -1 -1
1 1 1 1 0
-1 -1 -1 -1 0
p q r s t
ou
1 1 1 1 1
-1 -1 -1 -1 -1
1 1 1 1 0
-1 -1 -1 0 -1
p q r s t
Mas é fácil ver que nenhum dos casos dá certo, mas é puramente BPB (braçal
pra burro...).
De resto nao descobri mais nada!
Bem, alguém tem outras idéias?
--
Ideas are bulletproof.
V
