2014 Putnam preparation

Back to the main page

Until further notice, we will meet Friday afternoons in 646 PGH at 4pm to discuss problems.

No meeting during the Thanksgiving break.

Putnam problems and solutions

• Here is the old "official" link with problems, solutions and scores; http://kskedlaya.org/putnam-archive/ and comments about its history (and future).
• For the problems with comments/solutions/etc., see this link at Art of problem solving. Search the web for "art of problem solving putnam".
  Thanks to Nikhil for this link.

UH problem of the week

• You can look at the UH Problem of the week (also http://www.facebook.com/uhmpow), which is aimed at graduate students but often suitable for Putnam as well.
  Undergraduate solvers may be eligible for prize money (see the web-site).

December 5, 4pm, 651 PGH (NEW ROOM; enter from 641)

• Linear Diophantine equations (continuation of this topic from some time ago)

November 21, 4pm, 646 PGH

• Pigeon Hole Principle: problems 33, 38 and 42 from the Putnam and Beyond book.
  • 33. Given 50 distinct positive integers strictly less than 100, prove that some two of them sum up to 99.
    Looks like this problem meant to say "sum of at most two", instead of "sum of two".
  • 38. Show that there is a positive term of the Fibonacci sequence that is divisible by 1000. [Note: this is also true for any integer instead of 1000.]
  • 42. There are \(n\) people at a party. Prove that there are two of them so that of the remaining \(n-2\) people, there are at least \(\floor(n/2) -1\) of them each of whom knows both or else knows neither of the two.

November 14, 4pm, 646 PGH

• We discussed linear Diophantine equations, continuing the October 10 topic. See more there, and at https://www.cs.cmu.edu/~adamchik/21-127/lectures/divisibility_5_print.pdf.

November 7, 4pm, 646 PGH

• Let \(a,b,c\) be positive real numbers such that \((a+1)(b+1)(c+1)\le 8\); prove that \(abc\le 1\).
  Hint: Lagrange multipliers is a general method for solving "extrema with constraints"; this problem also admits a more elementary solution.
• This is from the Problem of the week series.
  [Proposed by Sergey Sarkisov] You had a collection of critters weighing 3000 lbs, and 99% of their mass is water-weight. Then, they exercise, thus losing water until out of their total weight only 98% is water. How much do these critters now weigh?

October 31, 4pm, 646 PGH

• if you had multivariable calculus then #529 (page 183):
  Let \(\phi(x,y,z)\) and \(\psi(x,y,z)\) be twice continuously differentiable functions in the region \(\{ (x,y,z) : \frac{1}{2} < \sqrt{x^2+y^2+z^2} < 2 \}\). Prove that \[\int \int_S (\nabla \phi \times \nabla \psi ) \cdot n dS = 0.\]
  where \(S\) is the unit sphere centered at the origin, \(n\) is the normal unit vector to this sphere, and \(\nabla \phi\) denotes the gradient of \(\phi\).
• otherwise #524 (page 179):
  Let \(\left | x \right | < 1\). Prove that \[\sum_{n=1}^\infty \frac{x^n}{n^2} = - \int_0^x \frac{1}{t} \ln (1-t)dt .\]

October 24, 4pm, 646 PGH

• Problem #421 (page 141):
  Prove that there are no positive numbers \(x\) and \(y\) such that \(x2^y +y2^{-x} = x+y\).

October 17, 4pm, 646 PGH

• Problem #409 (page 137 of the book):
  How many real solutions does the equation \(\sin(\sin(\sin(\sin(\sin(x)))))=\frac{x}{3}\) have?

October 10, 4pm, 646 PGH

• Problem 795 from Putnam and Beyond (problem 796 is related):
  Let \(a, b, c, d\) be integers with the property that for any two integers \(m\) and \(n\) there exist integers \(x\) and \(y\) satisfying \[ a x + b y =m \qquad c x + d y =n \] Prove that \(ad-bc = \pm 1\).
• Basic Diophantine result. Note the following result, which can be proven using the Division with Remainder Theorem:

  For integer \(a, b, c\), the equation \[ ax + b y =c \] has integer solutions \(x\) and \(y\) iff \(gcd(a, b)\) divides \(c\).

  Sketch of proof:

  • That \(gcd(a, b)\) must divide \(c\) is easy to see.
  • To prove that this is also sufficient, we claim that the \(gcd(a, b)\) can be written in this form, so this is also true for any multiple of \(gcd(a, b)\).
  • Non-constructive proof. Consider all the positive integers that can we written as \(ax + b y\) for \(x\) and \(y\) integer (why are there any such positive numbers?). Let \(d\) be the smallest such number, so \(d=a x + b y \gt 0\) for some integers \(x, y\).
    We will show that \(d\) divides both \(a\) and \(b\), so divides the \(gcd(a, b)\) as well. Since \(gcd(a, b)\) divides \(d\) by the "necessary" part, we conclude that \(d=\pm gcd(a, b)\), and we are done.
    Write the Division with Remainder for \(a\) divided by \(d\) \[ a=q d + r, \qquad 0\le r \lt |d| = d \] Then can write \[ r = a-q d = a- q (ax + b y) = a (\dots ) + b (\dots) \] (compute what's in the parentheses), which contradicts the choice of \(d\) unless \(r=0\). So \(d\) divides \(a\).
    Similarly, \(d\) divides \(b\).
  • Constructive proof; computing the \(gcd\) by division with remainder (faster, for large numbers, than factoring, see e.g. this wikipedia link).
    This is Euclid's algorithm; can assume WLOG that both integers are positive.
    • Given positive integers \(a\) and \(b\), divide with remainder the larger by the smaller, say \[ a = q b + r,\qquad 0 \le r < b \] Then \(r = a - q b\).
    • Repeat the above step for the divisor (above is \(b\)) and the remainder (above is \(r\)) until the remainder is zero.
      Each time rewrite the new remainder as a linear combination of \(a\) and \(b\).
    • The last nonzero remainder is \(gcd(a,b)\).
    Here is the computation for \(gcd(13,15)\): \[ 15=1*13 +2 \implies 2 = 15 - 1*13\\ 13=6*2 +1 \implies 1 = 13 - 6*2 = 13 - 6 * (15-13) = 7*13-6*15\\ 2= 2*1 +0 \] so the \(gcd\) is 1, and is given by \(1=7*13-6*15\)

• The Smith normal form. A much stronger (but not much harder to prove) result is the http://en.wikipedia.org/wiki/Smith_normal_form for integer matrices:

  Any \(m \times n\) matrix with integer entries can be written as a product \(M D N\) of matrices with integer entries where \(M\) and \(N\) are invertible over the integers matrices (hence square with determinant \(\pm1\)) and \(D\) is "diagonal" of size \(m \times n\). More can be said about the diagonal entries of \(D\), see the Wikipedia page.

• The Smith normal form solves the problem quickly. But can solve it with the above "basic" Diophantine result too.

October 3, 4pm, 646 PGH

• This past week's problem comes from Putnam and Beyond, item #385:
  Let \(f(x) = \sum_{k=1}^n a_k \sin(kx)\), with \(a_1, a_2, ..., a_n \in \mathbb{R}, n \ge 1\). Prove that if \(f(x) \le |\sin x |\) for all \(x\in \mathbb{R}\), then \[ \left | \sum_{k=1}^n ka_k \right |\le 1. \]

September 25, 5pm, 646 PGH

• Prove that \[ [x] + \left[x+ \frac{1}{n}\right] + ....+ \left[x+ \frac{n-1}{n}\right] = [nx] \] where \([\ ]\) denotes the floor function, \(x\) is real and \(n\) an integer.
• Next week we plan to also discuss questions in knot theory, please read that section from the Putnam and Beyond book.

September 18, 3pm, 646 PGH

• Show that \[ 1 + \frac{1}{1+\frac{1}{1+\dots}}= \sqrt{1+{\sqrt{1+ \sqrt{1+\cdots }}}} = \frac{1+\sqrt{5}}{2} \]

September 12, 4pm, 646 PGH

• From page 187 of the Putnam and Beyond book:
  
  Let \(x_1, ..., x_n\) be arbitrary real numbers. Prove the inequaliy \[ \frac{x_1}{1+x_1^2} + \frac{x_2}{1+x_1^2+x_2^2} + \cdots + \frac{x_n}{1+ x_1^2 \cdots + x_n^2 } < \sqrt{n} \]
• A problem from the "Problem of the week" series.