O quarto problema da IMO 2000

[Bruno Leite <superbr@xxxxxxx>]

Oi pessoal

Eu ACHO que consegui fazer o problema quatro da IMO 2000 e estou enviando-o
para a lista para saber se esta tudo certinho.

Eu vou precisar de um lemazinho:

Se A esta contido em {1,2,3,...,100} e B esta contido em {1,2,3,...,100},
entao 

#{x+y | x pertence a A e y pertence a B}>=#A+ #B -1

Prova: Seja i=#A e j=#B. Eh so'  ordenar os elementos de B e fazer inducao
sobre j.

----------

Agora, sejam A , B e  C conjuntos disjuntos 2 a 2 tais que A U B U
C={1,2,3,...,100}. Sejam #A=a, #B=b e #C=c. Eh claro que a+b+c=100.
Dados 2 conjuntos P e Q vou definir S(PQ) como sendo #{x+y | x pertence a P
e y pertence a Q}

Entao S(AB)+S(BC)+S(AC)>=a+b-1+b+c-1+a+c-1=197.
Sabemos que os possíveis valores da soma dos cartoes escolhidos pelo membro
da platéia estao entre 3 e 199 (ou seja, sao 197 valores)
Portanto todos os valores de {3,4,5,...199} devem ser "atingidos" pelas
somas, ou haverá somas idênticas entre pares diferentes de conjuntos, e aí
o mágico nao pode adivinhar nada. Como em particular 3 deve ser "atingido",
1 e 2 devem estar em conjuntos diferentes. Analogamente, 4, 199 e 198 devem
ser atingidos e por isso 1 e 3 pertencem a conjuntos diferentes, 100 e 99
também, 100 e 98 também.

Podemos supor por simetria que 1 pertence a A.
Caso 1: 2 pertence a B e 3 pertence a C

Eh facil ver que isso gera a seguinte particao:
A={1,4,7,10,...,100}
B={2,5,8,11,...,98}
C={3,6,9,12,...,99}
que eh uma solucao do problema.(Basta provar que 4 TEM que pertencer a A, 5
TEM que pertencer a B, etc, e generalizar)

Caso 2: 2 pertence a B e 3 pertence a B.
Dividimos em tres sub-casos:
a)100 pertence a C

Temos entao obrigatoriamente 99 e 98 pertencentes a B
Agora, 97 nao pode pertencer a C ou a soma 197 nao poderá mais ser
atingida. Mas se 97 pertence a A, entao temos que 96 pertence a A, 95
pertence a A, etc... 4 pertence a A. Mas isso eh absurdo pois teremos duas
somas iguais envolvendo conjuntos diferentes: 100+3=99+4. Por isso 97
pertence a B.

Aplicando varias vezes essa ideia chegaremos à seguinte partição:
A={1}
B={2,3,4,...98,99}
C={100}
que eh a outra solucao do problema

b)100 pertence a A
Isso leva a um absurdo:
Seja x o maior elemento de C. É facil eliminar as possibilidades de x+1
pertencer a  A ou a B. Logo x+1 pertence a C, mas isso contradiz o fato de
x ser o maior elemento de C.

c)100 pertence a B
Usando o mesmo raciocinio (supor x=max(C) etc) chegamos a outro absurdo.


Portanto as unicas solucoes sao 

A={1,4,7,10,...,100}
B={2,5,8,11,...,98}
C={3,6,9,12,...,99}

e

A={1}
B={2,3,4,...98,99}
C={100}

salvo as simetrias entre A, B e C.

------------
Bruno Leite