[obm-l] Sobre o Problema 112 da Eureka! (matriz nXn, elementos -1,0,1)

["Johann Peter Gustav Lejeune Dirichlet" <peterdirichlet2003@xxxxxxxxx>]

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