Bom dia, colendos e doutos colegas da lista!
Recebi de um amigo um problema da IMO, (longlist IMO 1977 - Romênia) Dados
37 pontos no espaço com coordenadas inteiras, prove que pelo menos um dos
triângulos formados por três desses pontos possui o baricentro com
coordenadas inteiras.
Já achei um descuido enorme da banca não restringir, sendo que não existem
três pontos colineares. Caso contrário podemos ter uma infinidade de pontos
sem formar um triângulo, quanto mais ter o baricentro com coordenadas
inteiras. E.g,. k(a,b,c) sendo k, a, b, c E Z.
Um outro ponto é que minha solução apontou apenas para necessidade de 29
pontos e o problema propõe 37, fiquei em dúvida se minha solução está
correta. Vamos à solução:
Sejam as coordenadas representadas em mod3, onde os ternos sem a vírgula,
na base 3 representam números de 0 a 26 ou seja A={(0,0,0), (0,01),(0,02),
(0,1,0),..., (2,2,0), (2,21), (2,2,2)}, essas são as casas dos pombos.
Seja P(x1,x2,x3), o complemento de P, representado por C(P)=(w1,w2,w3) |
x1+w1=x2+w2=x3+w3=0 mod3; onde o igual substitui o sinal de congruência,
devido a dificuldade de edição.
P(x1,x2,x3)=W(w1,w2,w3) mod3 se x1=w1 mod3, x2=w2 mod3 e x3=w3 mod3.
Proposições:
a) Sejam P1<> (0,0,0) mod3 e P2<> (0,0,0) mod3; P1<>P2 mod3 ==> P1+P2<>P1
mod3 e P1+P2<>P2mod3
b) P1<>P2 ==> C(P1) <>C(P2);
Não vou mostrar pois é simples.
Nosso alvo é ter 3 pontos P1(x1,y1,z1); P2(x2,y2,z2, P3(x3,y3,z3) |
C(P1+P2)=P3. Note que P1=P2=P3 mod3 é um caso particular dessa condição.
Lema: Se existem pelo menos 15 pontos distintos (não côngruos mod3) do
conjunto A entre os pontos do espaço então existe pelo menos um triângulo,
cujas coordenadas do baricentro são inteiras.
(i) Primeiro caso: (,0,0,0) não está na lista dos 15 pontos.
então formamos 14 pares de pontos, [P1,P2], [P1,P3], [P1,P4]...[P1,P14],
[P1,P15] onde as somas dos pares são todas não côngruas mod3, duas a duas.
logo, basta que encontremos apenas um complemento de uma das somas que
teremos um triângulo com o baricentro tendo suas coordenadas inteiras. Mas
como temos 14 somas diferentes, temos 14 complementos diferentes a serem
procurados. Uma vez que há 15 pontos distintos entre os pontos do espaço,
só há 12 pontos distintos que não estão relacionados. Como são 14
complementos distintos e só há chance de 12 não estarem selecionados, então
há pelo menos um triângulo desejado.
(ii) Segundo caso (0,0,0) está lista dos 15 pontos. Logo vou chamá lo de P1
e temos [P1,P2], [P1,P3], [P1,P4]...[P1,P14], [P1,P1], logo as somas darão
P2, P3, P4,...,P13, P14, P15 todos distintos
Logo temos 14 pares esperando por apenas um complemento. Como C(P)<>P ,
P<>0 mod3 e só temos 12 pontos para que sejam os complementos, logicamente
há pelo menos um complemento entre os 15 pontos e há como se formar um
triângulo, como desejado.
Caso eu tenha 29 pontos para não escolher 15 pontos diferentes eu tenho de
escolher 14 pontos distintos repetindo-os 1 vez, ou seja, cada casa de
pombos terá dois pontos. Aí, no 29o, não há para onde correr, ou se
posiciona três pontos em uma mesma casa está gerado um triângulo com
baricentro de coordenadas inteiras, ou se escolhe um ponto distinto e
teremos um triângulo com o baricentro de coordenadas inteiras, fulcrado no
lema acima.
Essa solução está correta?
A propósito, o número 15 surgiu de tendo n pontos distintos, podemos gerar
n-1 pares distintos, com a soma de seus componentes distintas. Portanto
teríamos que ter n-1 complementos, e se n-1>27-n, está solucionado ...2n>28
==> n>14, como nE Z n>=15.
Outro ponto, alguém possui o caminho da solução oficial?
Cordialmente,
PJMS.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
