[Solutions] William Lowell Putnam Mathematical Competition 2016

1. Find the smallest positive integer $j$ such that for every polynomial $p(x)$ with integer coefficients and for every integer $k,$ the integer \[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.$
2. Given a positive integer $n,$ let $M(n)$ be the largest integer $m$ such that \[\binom{m}{n-1}>\binom{m-1}{n}.\] Evaluate \[\lim_{n\to\infty}\frac{M(n)}{n}.\]
3. Suppose that $f$ is a function from $\mathbb{R}$ to $\mathbb{R}$ such that \[f(x)+f\left(1-\frac1x\right)=\arctan x\]for all real $x\ne 0.$ (As usual, $y=\arctan x$ means $-\pi/2<y<\pi/2$ and $\tan y=x.$) Find \[\int_0^1f(x)\,dx.\]
4. 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?
5. 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 \[g^{m_1}h^{n_1}g^{m_2}h^{n_2}\cdots g^{m_r}h^{n_r}\]with $1\le r\le |G|$ and $m_n,n_1,m_2,n_2,\dots,m_r,n_r\in\{1,-1\}.$ (Here $|G|$ is the number of elements of $G.$)
6. Find the smallest constant $C$ such that for every real polynomial $P(x)$ of degree $3$ that has a root in the interval $[0,1],$ \[\int_0^1|P(x)|\,dx\le C\max_{x\in[0,1]}|P(x)|.\]
7. Let $x_0,x_1,x_2,\dots$ be the sequence such that $x_0=1$ and for $n\ge 0,$ \[x_{n+1}=\ln(e^{x_n}-x_n)\](as usual, the function $\ln$ is the natural logarithm). Show that the infinite series \[x_0+x_1+x_2+\cdots\]converges and find its sum.
8. Define a positive integer $n$ to be squarish if either $n$ is itself a perfect square or 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 integers between $1$ and $N,$ inclusive. Find positive constants $\alpha$ and $\beta$ such that \[\lim_{N\to\infty}\frac{S(N)}{N^{\alpha}}=\beta,\]or show that no such constants exist.
9. Suppose that $S$ is a finite set of points in the plane such that the area of triangle $\triangle 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.$
10. Let $A$ be a $2n\times 2n$ matrix, with entries chosen independently at random. Every entry is chosen to be $0$ or $1,$ each with probability $1/2.$ Find the expected value of $\det(A-A^t)$ (as a function of $n$), where $A^t$ is the transpose of $A.$
11. 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\le y\le x^3,$ then $$(f(x))^2\le f(y) \le (f(x))^3.$$
12. Evaluate \[\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k}\sum_{n=0}^{\infty}\frac{1}{k2^n+1}.\]

[DOWNLOAD SOLUTIONS ##download##]