Cezar Lupu

Home » Uncategorized » The 2016 William Lowell Putnam Competition Exam at the University of Pittsburgh

The 2016 William Lowell Putnam Competition Exam at the University of Pittsburgh

The 77th annual William Lowell Putnam Mathematical Competition took place on December 5th in 705 Thackeray Hall. Eight Pitt students had the mission of solving the challenging Putnam problem sets. As usual, there were two sessions of 6 problems each. The official Pitt Team members were Alex Mang, Andrew Tindall and Jack Hafer. Other participating students were: Matthew Gerstbrein, Terry Tan, Andrew Klang, Tianke Li and Haoming Yan. Below one can find this year’s Putnam problems. Congratulations to all participants!

SESSION A:

Problem A1. Find the smallest positive integer j such that for every polynomial p(x) with integer coefficients and for every integer k, the integer

\displaystyle p^{(j)}(k)=\left. \frac{d^j}{dx^j}p(x) \right|_{x=k}

(the j-th derivative of p(x) at k) is divisible by 2016.

Problem A2. Given a positive integer n, let M(n) be the largest integer m such that

\displaystyle \binom{m}{n-1}>\binom{m-1}{n}.

Evaluate

\displaystyle\lim_{n\to\infty}\frac{M(n)}{n}.

Problem A3. Suppose that f is a function from \mathbb{R} to \mathbb{R} such that

\displaystyle f(x)+f\left(1-\frac{1}{x}\right)=\arctan x

for real x\neq 0. (As usual, y=\arctan x means -\frac{\pi}{2}<y<\frac{\pi}{2} and \tan y=x).

Find

\displaystyle \int_0^1f(x)dx.

Problem A4. Consider a (2m-1)\times(2n-1) rectangular region, where m and n are integers such that m,n\ge 4. The region is to be tiled using tiles of the two types shown:

putnam2016_3

(The dotted lines divide the tiles into 1\times 1 squares.) The tiles may be rotated and reflected, as long as their sides are parallel to the sides of the rectangular region. They must all fit within the region, and they must cover it completely without overlapping.

What is the minimum number of tiles required to tile the region?

Problem A5. Suppose that G is a finite group generated by the two elements g and h, where the order of g is odd. Show that every element of G can be written in the form

\displaystyle g^{m_{1}}h^{n_{1}} g^{m_{2}}h^{n_{2}}\ldots g^{m_{r}}h^{n_{r}}

with 1\leq r\leq |G| and m_{1}, n_{1}, m_{2}, n_{2}, \ldots m_{r}, n_{r}\in \{1, -1\}. (Here |G| is the number of elements of G.)

Problem A6. Find the smallest constant C such that every real polynomial P(x) of degree 3 that has a root in the interval [0, 1],

\displaystyle \int_0^1|P(x)|dx\leq C\cdot\max_{x\in [0,1]}|P(x)|.

SESSION B:

Problem B1. Let x_{0}, x_{1}, \ldots, x_{n}, \ldots be the sequence such that x_{0}=1 and for n\geq 0,

\displaystyle x_{n+1}=ln(e^{x_{n}}-x_{n}).

(as usual, the function ln is the natural logarithm). Show that the infinite series

\displaystyle x_{0}+x_{1}+x_{2}+\ldots

converges and find its sum.

Problem B2. Define a positive integer n to be squarish if either n is itself a perfect square of the distance from n to the nearest perfect square is a perfect square. For example, 2016 is squarish, because the nearest perfect square to 2016 is 45^2=2025 and 2025-2016=9 is a perfect square. (of the positive integers between 1 and 10, only 6 and 7 are not squarish.) For a positive integer N, let S(N) be the number of squarish between 1 and N inclusive. Find positive constants \alpha and \beta such that

\displaystyle\lim_{N\to\infty}\frac{S(N)}{N^{\alpha}}=\beta,

or show that no such constants exist.

Problem B3. Suppose that S is a finite set of points in the plane such that the area of the triangle \Delta ABC is at most 1 whenever A, B and C are in S. Show that there exists a triangle of area 4 that (together with its interior) covers the set S.

Problem B4. Let A be a 2n\times 2n matrix, with entries choasen indepedently at random. Every entry is chosen to be 0 or 1, each with probability \frac{1}{2}. Find the expected value of \det(A-A^{t}) (as a function of n), where A^{t} is the transpose of A.

Problem B5. Find all functions f from the interval (1, \infty) to (1, \infty) with the following property:

if x, y\in (1, \infty) and x^2\leq y\leq x^3, then (f(x))^2\leq f(y)\leq (f(x)^3.

Problem B6. Evaluate

\displaystyle \sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k}\cdot\sum_{n=0}^{\infty}\frac{1}{k2^n+1}.

OFFICIAL SOLUTIONS:


This slideshow requires JavaScript.

Advertisements

1 Comment

  1. […] Here are a few of the problems of the Putnam 2016 contest. I choose to only list problems which I managed to solve. Most of them are pretty straightforward, so maybe the solutions posted here may be very similar to the official ones. You can find a complete list of the problems on other sites, for example here. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: