2009 Putnam results

De ontem (via Qiaochu Yuan,  Annoying Precision ):

 Art of Problem Solving, Dr. Kent Merryfield    

[   Birch & Swinnerton Dyer ], Fri Mar 18, 2010: 

    
   “ Team ranks:

    1. MIT (Qingchun Ren, Bohua Zhan, Yufei Zhao)

    2. Harvard (Iurie Borieco, Arnav Tripathy, Alex Zhai)

    3. Caltech (Jason Bland, Sam Elder, Gjergji Zaimi)

    4. Stanford (Young Hun Jung, Seok Hyeung Lee, Jeffrey Wang)

    5. Princeton (Peter Diao, Adam Hesterberg, John Parton)

 
    Honorable mention:

    Duke

    U. of Maryland

    U. of Toronto

    U. of Virginia

    U. of Waterloo

 
    Putnam Fellows (in alphabetical order):

    William Johnson, U. of Washington (Seattle)

    Xiaosheng Mu, Yale

    Qingchun Ren, MIT

    Arnav Tripathy, Harvard

    Yufei Zhao, MIT

 

    Group N1:

    Yakov Berchenko-Kogan, Caltech

    Sergei Bernstein, MIT

    Jason Bland, Caltech

    Kestutis Cesnavicius, Rice

    Palmer Mebane, Harvey Mudd

    John Pardon, Princeton

    Jacob Steinhardt, MIT

    Yi Sun Harvard

    Alex Zhai, Harvard

    Bohua Zhan, MIT

 

    Group N2:

    Yi-Wei Chan, Illinois

    Jeffrey Chen, Stanford

    Miles Edwards, Indiana

    Sam Elder, Caltech

    Zhou Fan, Harvard

    Whan Ghang, MIT

    Seok Hyeong Lee, Stanford

    Panupong Pasupat, MIT

    Colin Sandon, MIT

    Eric Stansifer, Caltech

 
    The Elizabeth Lowell Putnam Prize doesn’t seem to have been awarded. “

Putnam problem of the day (by the HMD dated March 1, 2008)

pdf: included in Caderno (see “caderno” page) 

On March 1st, 2008, the Putnam problem of the day displayed on the  Harvard’s Math Department site was stated as follows:

“ Evaluate

Express your answer in the form

,

where are integers. “ 

Solution

To evaluate the radicand I start by seeing that the continued fraction

satisfies

.

Thus,  since  the only solution left is

.

A few algebraic manipulations give

hence

In order to have

or equivalently,

with integers,  should also be an integer; therefore should be even. I assume that On the other hand  should be  Thus,

Since, for 

,

this possibility is excluded. It remains 

Now I confirm

So, the solution I came was

Remark: The calculation of

can be done by hand as follows

Update March, 20: you can compare with this solution   (Putnam 1995, Problem B5 )

Addendum of March 7, 2009: Comment/Proof of the convergence of the continued fraction by Vishal Lama (comment dated March 7, 2009)

“ In the solution presented in your post, denotes an expression that we can’t assume, beforehand, is a finite number. may perhaps be infinite! Therefore, the way to go about computing the expression (the infinite continued fraction) given in the problem is as follows.

The infinite continued fraction is defined as the limit of the sequence , where and for all . Then, we show that the sequence is bounded from below ( for all , which can be shown by a simple induction) and that it is also strictly decreasing (which can be shown using induction, again).  Now, we invoke the Monotone Convergence Theorem to conclude that the sequence does indeed have a (finite) limit, which we can now denote by . Once we establish that (which is the infinite continued fraction!) is finite, we can compute the way you did in your solution. Basically, we have to go through all that trouble just to prove that the given infinite continued fraction is indeed finite! Only after that can the computation begin! “

Part of my reply was: “I did not prove the convergence of the continued fraction. Thanks for doing it.
Basically I assumed that convergence based on a certain numerical evidence, but of course this evidence proves nothing.”

ADDENDUM of May 5, 2010: Alternatively we can prove the convergence applying the Śleszýnki-Pringsheim Theorem (a reference here,  wikipedia): if for all naturals , , then the continued fraction  converges. Since and , the theorem hypothesis is satisfied:

.

 

 

Problema Putnam de hoje (do HMD)

English version

pdf: ver caderno

No site do departamento do Harvard’s Math Department aparece hoje o seguinte enunciado (Putnam problem of the day):

« Evaluate

Express your answer in the form

,

where are integers. »

Resolução

NOTA PRÉVIA: a solução a que cheguei não teria sido possível de encontrar apenas com papel e lápis, pois alguns passos envolveram alguns cálculos numéricos feitos no Scientific Notebook. Se chegar a um método limpo, penso publicá-lo aqui. Efectivamente é possível calcular à mão as potências de um binómio com radicais, como se mostra na adenda de 9-3-2008.

Começo por calcular o radicando, notando que a fracção contínua

verifica

pelo que, como só poderá ser

e, após alguns cálculos

por este motivo

Para que

ou, de forma equivalente,

com inteiros, é necessário que seja inteiro, pelo que deve ser par. Vou admitir que por outro lado deverá ser igual a Então,

Como, para

excluo esta possibilidade. Resta

Vou confirmar

A solução pedida a que cheguei foi

Adendas de 9-3-2008 e 12-3-2008: O pdf foi actualizado em 12-3.

O  cálculo de

 

pode ser feito à mão da seguinte forma

Actualização de 19-3-2008: veja outra  resolução aqui (Putnam 1995, Problem B5 )

Adenda de 7-3-2009: Tradução do Comentário/Demonstração de Vishal Lama  da convergência da fracção contínua  (comentário de hoje)

« Na resolução apresentada no post, designa uma expressão que não podemos assumir à partida que  seja um número finito. pode eventualmente ser  infinito! Por isso, a maneira de anteceder o cálculo da expressão (da fracção contínua infinita) dada no problema é como segue.

A fracção contínua infinita é definida como sendo o limite da sucessão , em que e qualquer que seja . Depois, mostramos que a sucessão  é limitada inferiormente ( para todos os , o que se pode fazer por uma indução simples) e que é também estritamente decrescente (a indução pode usar-se também para o mostrar).  A seguir, recorremos ao teorema da convergência monótona ( Monotone Convergence Theorem) para concluir que de facto a sucessão tem um limite (finito), que podemos então designar por . Uma vez provado que  (ou seja, a fracção contínua infinita!) é finito, podemos calcular da maneira que fez na resolução. Basicamente é preciso ter todo este trabalho para demonstrar que efectivamente a fracção contínua infinita tem um falor finito! Só depois podemos começar o cálculo!  »

Uma parte da minha resposta foi: «Não demonstrei a convergência da fracção contínua. Obrigado por tê-lo feito.
Basicamente admiti a convergência baseado numa certa evidência numérica, mas claro que isso não prova nada.»

ADENDA de 6-05-10: Em alternativa, podemos demonstrar a convergência pelo teorema de Śleszýnki-Pringsheim (referência aqui,  wikipedia): se para todos os valores naturais de , se verificar , a fracção contínua é convergente. Ora como e , verifica-se a hipótese do teorema:

.