[obm-l] Re: [obm-l] IMO - P1

[yurigomes@xxxxxxxxxxxxxx]

Oi Marcio,
 Soh hj eu li seu email, depois que eu tbm consegui fazer a questão. 
 Tem apenas um detalhe que vc não observou: os t_i´s devem ser distintos,
pq senão os dois conjuntos seriam iguais. 
 Seguindo a sua notação, sendo D_i=(D+ t_i)U(t_i- D), temos |D_i|<= 2.5050.
O t_(i+1) deve ser escolhido em 
       T = S\(S_1 U...U S_i U {t_1, t_2,...,t_i})
  Olha como o problema é impressionante: para garantir que t_100 pode ser
escolhido, devemos ter T não-vazio. Ora, 
|S_1 U...U S_99 U {t_1, t_2,...,t_99}|<= |S_1|+...+ |S_99|+ 99<=
      99.2.5050+ 99= 999900+ 99= 999999 < 1000000  (!!!!)
   Os números foram muitos bem escolhidos, e o problema ainda não perdeu
a elegância com números feios! NOvamente, parabéns Gugu.
  Ateh mais, 
  Yuri
-- Mensagem original --

>    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
>=========================================================================
>

[]'s, Yuri
ICQ: 64992515


------------------------------------------
Use o melhor sistema de busca da Internet
Radar UOL - http://www.radaruol.com.br



=========================================================================
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
=========================================================================