Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    U of I Mock Putnam Exam SEPT. 29, 2009 Solutions

    Uploaded by

    Gag Paf
    This document contains solutions to 6 problems from mock Putnam exams. 1) A polynomial P(x) with integer coefficients is such that none of P(1) through P(2009) are divisible by 2009. It is shown that this implies P(n) is never 0. 2) The solution to a functional equation involving an integral is found to be f(x) = √2009ex. 3) It is shown that any permutation of the positive integers contains a triple with a constant difference between consecutive terms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    U of I Mock Putnam Exam SEPT. 29, 2009 Solutions

    Uploaded by

    Gag Paf
    6 views3 pages
    This document contains solutions to 6 problems from mock Putnam exams. 1) A polynomial P(x) with integer coefficients is such that none of P(1) through P(2009) are divisible by 2009. It is shown that this implies P(n) is never 0. 2) The solution to a functional equation involving an integral is found to be f(x) = √2009ex. 3) It is shown that any permutation of the positive integers contains a triple with a constant difference between consecutive terms.

    Original Description:

    integral contest

    Original Title

    mock09sol

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains solutions to 6 problems from mock Putnam exams. 1) A polynomial P(x) with integer coefficients is such that none of P(1) through P(2009) are divisible by 2009. It is shown that this implies P(n) is never 0. 2) The solution to a functional equation involving an integral is found to be f(x) = √2009ex. 3) It is shown that any permutation of the positive integers contains a triple with a constant difference between consecutive terms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    6 views3 pages

    U of I Mock Putnam Exam SEPT. 29, 2009 Solutions

    Uploaded by

    Gag Paf
    This document contains solutions to 6 problems from mock Putnam exams. 1) A polynomial P(x) with integer coefficients is such that none of P(1) through P(2009) are divisible by 2009. It is shown that this implies P(n) is never 0. 2) The solution to a functional equation involving an integral is found to be f(x) = √2009ex. 3) It is shown that any permutation of the positive integers contains a triple with a constant difference between consecutive terms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    U OF I MOCK PUTNAM EXAM

    SEPT. 29, 2009


    Solutions

    1. Suppose P (x) is a polynomial with integer coefficients such that none of the values
    P (1), . . . , P (2009) is divisible by 2009. Prove that P (n) 6= 0 for all integers n.
    Solution. We use the fact that, for any integers a, b and m 1, a b mod m
    implies P (a) P (b) mod m. This follows from the general properties of congruences.
    Given an integer n, let r {1, 2, . . . , 2009} be such that n r mod 2009. Then, by
    the above fact and the given hypothesis, P (n) P (r) 6 0 mod 2009, and hence
    P (n) 6= 0.

    2. Find a function f (x) that satisfies, for all x 0,


    sZ
    x
    f (x) = (f (t)2 + f 0 (t)2 )dt + 2009.
    0

    Solution. [Problem B1, Putnam 1990] Square the given equation and differentiate
    to get
    2f (x)f 0 (x) = f (x)2 + f 0 (x)2 ,
    or
    (f (x) f 0 (x))2 = 0,
    which is equivalent to f 0 (x) = f (x). The latter equation has solution f (x) = Cex ,
    where C is an arbitrary constant. Substituting this into the original equation, we get
    s Z
    x p
    Cex = C 2 2(Cet )2 dt + 2009 = C 2 e2x C 2 + 2009,
    0

    and choosing C = 2009, we see that this equation is satisfied. Thus, f (x) = 2009ex
    is the desired solution.

    3. Let A = (a1 , a2 , a3 , . . .) be a permutation of the positive integers. (In other words, ak


    is a positive integer for each k, and for each positive integer n, there exists exactly
    one k such that ak = n.) Prove that A contains a triple (ai , aj , ak ) with i < j < k
    and aj ai = ak aj = d > 0.
    Solution. Let j be the least integer such that aj > a1 , and let k be the unique
    index such that ak = 2aj a1 . Since 2aj a1 > aj > a1 , it follows from the definition
    of the index j that k > j. The triple (a1 , aj , ak ) has the required properties.
    4. Let b1 , . . . , bn be integers greater than 1, and let B = b1 . . . bn denote their product.
    Let di be the number of digits of B expressed in base bi . For example, if b1 = 10,
    b2 = 3, b3 = 2, then B = 10 3 2 = (60)10 = (2020)3 = (111100)2 , so d1 = 2, d2 = 4,
    d3 = 6. Show that
    d1 + + dn > n2 .

    Solution. First note that a positive integer m expressed in a base b 2 has d digits
    if and only if bd1 m < bd , or equivalently, d 1 ln m/ ln b < d.
    Now, set i = ln bi and note that
    n
    X n
    X
    ln B = ln(b1 . . . bn ) = ln bj = j .
    j=1 i=j

    By the above inequality,


    n
    ln B 1 X
    di > = j .
    ln bi i
    j=1

    Summing over i = 1, 2, . . . , n and using the arithmetic-geometric mean inequality


    twice, we get

    n n
    ! n
    X X 1 X
    di > j

    i=1 i=1 i j=1

     1/n X n
    1 1
    n ... j
    1 n
    j=1

    n
    !1 n
    1 X X
    n i j = n2 .
    n
    i=1 j=1

    Note: Instead of two applications of the AGM inequality, we could have used the
    arithmetic-harmonic mean inequality:
    n
    ! n
    !1
    1 X 1X 1
    i .
    n n i
    i=1 i=1

    A third method is to use Cauchys inequality in the form


    n
    !2 n
    ! n !
    2
    X 1/2 1/2
    X 1 X
    n = i i i .
    i
    i=1 i=1 i=1

    5. Show that any positive integer containing exactly 2009 digits (in decimal), none of
    whose digits is zero, is either divisible by 2009, or can be changed to an integer that
    is divisible by 2009 by replacing some, but not all, of its digits by 0.

    1
    Solution. Let n = a1 a2 . . . a2009 be the given integer, let n0 = 0, and for k =
    1, 2, . . . , 2009 let nk denote the number obtained by replacing all but the first k digits
    of n by the digit 0, i.e., nk = a1 a2 . . . ak 00 . . . 0. By the pigeon hole principle, two of
    the 2010 numbers n0 , n1 , . . . , n2009 , say nk1 and nk2 with k2 > k1 , must be congruent
    modulo 2009. It follows that the difference nk2 nk1 is divisible by 2009. Now nk2 nk1
    is the number obtained from n by replacing the first k1 and the last (2009 k2 ) digits
    by 0. Since k2 > k1 , we have k1 + (2009 k2 ) < 2009, so not all of the 2009 digits are
    replaced by zero. Thus, the number nk2 nk1 has the required properties.

    6. Let A be an infinite set of positive integers, and let A(n) denote the number of
    elements of A that are n. Suppose that the series
    X1
    a
    aA

    converges. Show that limn A(n)/n = 0.


    Solution. [Problem B5, Putnam 1969] We argue by contradiction. Suppose A(n)/n
    does not tend to 0. Then there exists  > 0 and an infinite sequence n1 < n2 < of
    positive integers such that A(nk )/nk  for all k. Let N be a fixed positive integer.
    Since nk as k , we have nk > N for all large enough k. For such k we have
    X 1 X 1 A(nk ) A(N ) A(N )
     .
    a nk nk nk
    aA aA
    N <ank N <ank

    Letting k , we conclude
    X 1
    .
    a
    aA,a>N
    P
    Since N was arbitrary, the series aA 1/a cannot be convergent.

    You might also like