Re: [obm-l] IMO - P1

["Marcio Afonso A. Cohen" <marciocohen@xxxxxxxxxxxxxx>]

    Acho que consegui fazer  o 1o. Confiram ai e vejam se tem algum furo. O
2o eu realmente nao estou conseguindo.. Estou com alguma esperanca de fazer
o 5.. (o 3 eu tentei tmb, mas minhas contas estao muito grandes). Mandem
seus comentarios sobre a prova!
P1:
    Note que (Ai inter Aj) != vazio sse existirem m,n tais que a_m + t_i =
a_n + t_j , i.e, a_m - a_n = t_j - t_i.
    Vamos construir os t's indutivamente garantindo que isso nao acontece.
Existem binomial (101,2) = 5050 diferencas possiveis no conjunto A. Chame de
D={D1,D2,...D5050} o conjunto dessas diferencas (claro que algumas delas
podem ser iguais, mas temos |D| <= 5050).
1. Escolha um t1 qualquer de S.
2. Agora quero garantir que t2-t1 e t1-t2 nao estao em D. Para isso, basta
escolher um elemento de S que nao esteja em
X1 = {t1+D1,t1+D2,...,t1+D5050}U{t1-D1, t1-D2,...,t1-D5050}. (pq se t2-t1
esta em D, entao t2=t1+Dk para algum k).
Isso eh facil pq |X1|<=2.5050 < |S|.

3. Agora vou escolher t3 em S garantindo que t3-t1, t1-t3, t3-t2, t2-t3 nao
estao em D.
Para isso, t3 nao pode estar em X1 e tmb nao pode estar em
X2 = {t2+D1,t2+D2,...,t2+D5050}U{t2-D1, t2-D2,...,t2-D5050}.
Isso eh facil, pq |X1 U X2| <= 4.5050 < |S|

Em geral, depois de escolhidos t1,t2,...,t_k-1, vou escolher t_k em S de
modo que ele nao esteja em nenhum dos conjuntos X1,X2,...,X_(k-1).
Para k<=100, isso eh sempre possivel, pq |X1 U X2 U ... U X_(k-1)| <=
2*(k-1)*5050 <= 2*99*5050 = 999900 < 10^6 = |S|.
(obs: X_s = {ts + D}U{ts-D}, na notacao usuao de x+A onde x eh um elemento e
A um conjunto).


Pronto. Foram escolhidos 100 t's tal que nao existe uma quadrupla (m,n,i,j)
tq a_m - a_n = t_j - t_i. (pois t_j - t_i esta sempre fora de D), e portanto
nunca se tem a_m + t_i = a_n + t_j, ou seja, as intersecoes sao todas vazias
de fato.

    Abracos.



----- Original Message -----
From: <gugu@impa.br>
To: <obm-l@mat.puc-rio.br>
Cc: <obm@impa.br>; <edmilson@etapa.com.br>
Sent: Monday, July 14, 2003 3:38 PM
Subject: [obm-l] Problemas da IMO


>
>
> Prova da IMO retirada do Site http://www.mathlinks.go.ro/
>
> O Problema 1 é nois que mandou...
>
>
> First Day - 44th IMO 2003 Japan
>
> 1. Let A be a 101-element subset of the set S={1,2,3,...,1000000}. Prove
that
> there exist numbers t_1, t_2, ..., t_{100} in S such that the sets
>
> Aj = { x + tj | x is in A } for each j = 1, 2, ..., 100
>
> are pairwise disjoint.
>
>
> 2. Find all pairs of positive integers (a,b) such that the number
>
> a^2 / ( 2ab^2-b^3+1) is also a positive integer.
>
> 3. Given is a convex hexagon with the property that the segment connecting
the
> middle points of each pair of opposite sides in the hexagon is  sqrt(3) /
2
> times the sum of those sides' sum.
>
> Prove that the hexagon has all its angles equal to 120.
>
>
> Second Day - 44th IMO 2003 Japan
>
> 4. Given is a cyclic quadrilateral ABCD and let P, Q, R be feet of the
> altitudes from D to AB, BC and CA respectively. Prove that if PR = RQ then
the
> interior angle bisectors of the angles < ABC and < ADC are concurrent on
AC.
>
> 5. Let x1 <= x2 <= ... <= xn be real numbers, n>2.
>
> a) Prove the following inequality:
>
> (sum  ni,j=1 | xi - xj | ) 2 <= 2/3 ( n^2 - 1 )sum ni,j=1 ( xi - xj)^2
>
> b) Prove that the equality in the inequality above is obtained if and only
if
> the sequence (xk) is an arithemetical progression.
>
> 6. Prove that for each given prime p there exists a prime q such that
n^p - p
> is not divisible by q for each positive integer n.
>
>
>
> -------------------------------------------------
> This mail sent through IMP: http://horde.org/imp/
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> =========================================================================
>

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================