Re: Putnam 2001

[Carlos Stein Naves de Brito <carlosstein@xxxxxxxxxx>]

E ai Marcio,
andei tentando os problemas, confere com suas respostas o que fiz ate
agora...
A2 voce faz recorrencia em Pn(a probabilidade pedida para n moedas),
fica Pn=P(n-1)*(1- 1/(2n+1)) + (1 - P(n-1))*(1/(2n+1))
, pois calcula a prob deve continuar impar, ou de virar impar.
ai minha resposta deu Pn= 1/2 - 1/6( (2n-1)/(2n+1) )^n-1

A3
Igualando a 0 para achar raizes da equacao, voce acha sqrt(8m), logo
colocamos  m=2n^2, para algum n(a principio real). ai resolvendo voce acha
as 4 raizes, e vendo os 3 casos ve que serve n=k ou n=sqrt(2)k, k natural.
logo m=4k^2 ou m=2k^2, para todo k natural.

A4 Se eu entendi certo bissecta quer dizer divide ao meio, certo?
Essa eu fiz de um jeito que eu gosto muito, que é usar pesos nos vertices e
estudar o centro de massa do sistema, que é unico, e isso muitas vezes ajuda
na colinearidade e/ou concorrencia. percebi inicialmente que o triangulo RST
esta com os vertices nas bases medias do ABC. Ai coloquei pesos que deixavam
o centro de massa nessas bases e estudava as proporcoes que o RST dividia os
lados do tringulo formado pelas bases medias(de area 1/4).
achei essas proporcoes certinhas. sabendo as proporcoes voce usa o calculo
da area a*b*sena/2 pois calcula com os lados inteiro, entao a area vale 1/4,
ai depois so com a proporcao pedida, e vc acha a proporcao de area dos
triangulos dos cantos, fora de RST, dentro do triangulo medio.
Cada uma das tres areas deu (sqrt(5) - 2)/4. assim o resultado é 1/4 -
3*(sqrt(5)/4 - 2/4). deu 7/4 - 3*sqrt(5) / 4.
nao expliquei bem, me pergunte se quiser saber detalhes..


A5
mod a:
-1 == 2001 => 2002 == 0, logo a|2002.

mod 3:
se a=3k:
-1 == 2001 => -1 == 0 mod 3. absurdo.
se a=3k+2:
2^n+1 == 2001 == 0 absurdo denovo
se a=3k+1:
1 - (-1)^n == 2001 == 0 lgo n tem que ser par.

mod a+1:
(-1)^n+1==2001, como n é par, -1==2001 => 2002 == 0, logo a+1|2002.

mas os unicos divisores consecutivos a e a+1 de 2002 sao 13 e 14.
lgo a=13. n=2 serve. se aumentamos o n em 1, a diferenca diminui(um
multiplica por a, outro por a+1) assim a solucao é unica.

B1
esse acho que todo mundo ja viu antes, cada casa é x*n + y(x e y variam de 1
a n). o vermelho soma n/2 vezes cada x e n/2 vezers cada y. ai é facil fazer
a soma. preto é analogo.

 
B3
<n> vale x, se so se x^2-x+1<n<x^2+x(2x valores). assim para esse intervalo
temos a soma de PG: (2^x + 1/2^x)( 1/2^(x^2 -x +1) * ((1/2)^2x - 1)/(-1/2),
fazendo a simplificacao temos: 2*2^(-x^2), com x variando de 0 a infinito.
logo a soma fica 2*(1/2^0 + 1/2^1 + 1/2^4 + ... ) mas parei por ai, alguma
ideia?

B4
digamos que a interseccao contenha certo p/q, p e q primmos entre si. ele é
imagem de f^n para todo n. logo ha um x tq x - 1/x = p/q. tirando minimo e
resolvendo temos em bascara sqrt(p^2 + (2q)^2)
assim p e 2q satisfazem condicoes para serem pitagoricos, como 2q é par sera
da forma 2uv, e p é u^2 - v^2. (nao ha o d, fator comum). substituindo isso
e resolvendo se acha x=u/v. como p/q era imagem de f^2, u/v sera imagem de
f, logo faremos a mesma coisa, achando v=v', depois analogamente v'=v'',
infinitamente.
mas temos q=uv=u*u'v'=uu'u''v''= ... logo tem infinitos fatores, absurdo, a
nao ser que os u' sejam 1, mas testando 1 em p, nao ha possibilidade.
logo a interseccao é vazia.

vou tentando os outros depois, nao achei muitos avancos, a da funcao B5
parece uma que ja surgiu na lista, na qual a funcao parece uma recorrencia,
mas nao descobri muita coisa.
Abraço,
Carlos


> From: "Marcio" <mcohen@iis.com.br>
> Reply-To: obm-l@mat.puc-rio.br
> Date: Sun, 2 Dec 2001 15:26:30 -0200
> To: <obm-l@mat.puc-rio.br>
> Subject: Fw: Putnam 2001
> 
> Aqui estao as questoes do Putnam 2001. Ainda nao tive tempo para pensar em
> todas. O autor desse email parece ser muito bom, mas mesmo assim ele disse
> que ainda nao conseguiu fazer 3 questoes, como vcs podem ver ai em baixo.
> Eu ja tentei fazer as questoes desde a A1 ateh A5. A A5 ainda me restam 6
> valores de x para considerar, nao estou conseguindo elimina-los. As solucoes
> para os problemas A eu achei na internet em algum lugar, nao me lembro
> exatamente onde ("putnam 2001 problems" no google deve mostrar o site).
> Descobri que eu deixei de considerar um caso importante na solucao do A3. A
> minha solucao do A4 ficou meio grande, e deu resposta diferente da desse
> site. Com certeza a minha esta errada, mas ainda nao achei aonde (eu fiz por
> vetores, deu uma conta grande, mas diferente da que ta la).
> O A5 eu ainda nao li a solucao. O A6 eu vou tentar agora, mas eh improvavel
> eu obter algum avanco, haja vista que o autor do email ainda nao conseguiu
> fazer. Se eu descobrir algo mando pra lista! Os 3 primeiros sao bem mais
> faceis..
> Tentem fazer tmb!
> Os problemas B's eu tento outro dia :)
> 
> Eu nao estou cronometrando, mas acho que um dos principais obstaculos dessa
> prova eh o tempo. Vc tem que pensar em 6 questoes no curto periodo de 3
> horas.
> 
> Como curiosidade, um dos americanos que fecharam a IMO esse ano, ja foi
> (antes de entrar para a universidade!) um fellow putnam, o q significa que
> ele conseguiu ficar entre as 5 melhores pontuacoes individuais do putnam
> (nao sei em q ano foi isso).
> 
> Abracos,
> Marcio
> 
> ----- Original Message -----
> From: <rusin@math.niu.edu>
> To: <mcohen@iis.com.br>
> Sent: Sunday, December 02, 2001 1:19 PM
> Subject: Re: Putnam 2001
> 
> 
>> Here are the questions to the 62nd annual Putnam exam, held today
>> (Dec 1 2001).  You have 6 hours; good luck :-)
>> 
>> I will post the answers I have as soon as I can type them up.
>> (Right now I lack answers to  A6, B5, B6 .)
>> 
>> There are links to Putnam problems and solutions at
>> http://www.math.niu.edu/~rusin/problems-math/
>> 
>> 
>> 
>> A1. Consider a set  S  and a binary operation  *  on  S  (that is, for
>> each  a, b  in  S,  a*b  is in  S).  Assume that  (a*b)*a = b  for all
>> a, b  in  S.  Prove that  a*(b*a) =b  for all a, b  in  S.
>> 
>> A2. You have coins  C1, C2, ..., C_n.  For each  k,  coin  C_k  is biased
>> so that, when tossed, it has probability  1/(2k+1)  of falling heads.
>> If the  n  coins are tossed, what is the probability that the
>> number of heads is odd? Express the answer as a rational function of  n.
>> 
>> A3. For each integer  m,  consider the polynomial
>> P_m(x) = x^4 - (2m+4) x^2 + (m-2)^2
>> For what values of  m  is  P_m(x)  the product of two nonconstant
>> polynomials with integer coefficients?
>> 
>> A4. Triangle  ABC  has area  1.  Points  E,F,G  lie, respectively, on
>> sides  BC, CA, AB  such that  AE  bisects  BF  at point  R,
>> BF bisects  CG  at point  S,  and  CG  bisects  AE  at point  T.
>> Find the area of triangle  RST.
>> [Illustration deleted.]
>> 
>> A5. Prove that there are unique positive integers  a, n  such that
>> a^(n+1) - (a+1)^n = 2001.
>> 
>> A6. Can an arc of a parabola inside a circle of radius  1 have length
>> greater than  4 ?
>> 
>> B1. Let  n  be an even positive integer. Write the numbers  1, 2, ..., n^2
>> in the squares of an  n x n  grid so that the  k-th row, from left to
>> right, is
>> (k-1)n + 1,  (k-1)n + 2, ..., (k-1)n + n.
>> Color the squares of the grid so that half of the squares in each row
>> and in each column are red and the other half are black (a checkerboard
>> coloring is one possibility). Prove that for each such coloring, the
>> sum of the numbers on the red squares is equal to the sum of the numbers
>> on the black squares.
>> 
>> B2. Find all pairs of real numbers  (x,y)  satisfying the system of
> equations
>> 
>> 1/x + 1/(2y) = (x^2 + 3 y^2) ( 3 x^2 + y^2 )
>> 1/x - 1/(2y) = 2(y^4 - x^4)
>> 
>> B3. For any positive integer  n  let  <n>  denote the closest integer
>> to  sqrt(n).  Evaluate
>> \sum_{n=1}^{\infty}  ( 2^{<n>} + 2^{-<n>} ) / 2^n
>> 
>> B4. Let  S  denote the set of rational numbers different from -1, 0, and
> 1.
>> Define  f : S --> S  by  f(x) = x - 1/x . Prove or disprove that
>> \intersect_{n=1}^{\infty}  f^(n) (S) = \emptyset,
>> where  f^(n) = f o f o  ... o f   (n  times).
>> 
>> (Note:  f(S)  denotes the set of all values  f(s)  for  s \in  S. )
>> 
>> B5. Let  a  and  b  be real numbers in the interval  (0, 1/2)  and
>> let  g  be a continuous real-valued function such that
>> g(g(x)) = a g(x) + b x  for all real  x.  Prove that  g(x) = c x  for
>> some constant  c.
>> 
>> B6. Assume that  (a_n)_{n >= 1}  is an increasing sequence of positive
>> real numbers such that  lim_{n->\infty}  a_n / n = 0.  Must there
>> exist infinitely many positive integers  n  such that
>> a_{n-i} + a_{n+i} < 2 a_n  for  i = 1, 2, ..., n-1 ?
>> 
>