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} 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:

(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.