Home > Analysis, Geometry, Olympiad, Problem Solving > Some of the easy Putnam 2016 Problems

Some of the easy Putnam 2016 Problems

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.

A1. Find the smallest integer ${j}$ such that for every polynomial ${p}$ with integer coefficients and every integer ${k}$, the number

$\displaystyle p^{(j)}(k),$

that is the ${j}$-th derivative of ${p}$ evaluated at ${k}$, is divisible by ${2016}$.

Hints. Successive derivatives give rise to terms containing products of consecutive numbers. The product of ${j}$ consecutive numbers is divisible by ${j!}$. Find the smallest number such that ${2016 | j!}$. Prove that ${j-1}$ does not work by choosing ${p = x^{j-1}}$. Prove that ${j}$ works by working only on monomials…

A2. Given a positive integer ${n}$ let ${M(n)}$ be the largest integer ${m}$ such that

$\displaystyle {m \choose n-1} > { m-1 \choose n}.$

Evaluate

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

Hints: Write formulas for binomial coefficients and simplify what is possible. What remains should be an inequation of degree ${2}$ in terms of ${m}$. Find the largest positive root of the equation and the largest ${m}$ should be the integer part of that root. Using the fact that the integer part of ${x}$ is equivalent to ${x}$ as ${x \rightarrow \infty}$ we can conclude.

A3. Suppose that ${f}$ is a function from ${\Bbb{R} \rightarrow \Bbb{R}}$ such that

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

for all real ${x \neq 0}$. Find ${\int_0^1 f(x) dx}$.

Hints: Use a classical trick of replacing ${x}$ by ${1-1/x}$. This makes the second argument equal to ${-1/(x-1)}$. Note that making now ${x \mapsto -1/(x-1)}$ the second argument becomes ${x}$. This will give three equations which allow us to find a formula for ${f(x)}$.

B1. Let ${(x_n)}$ be a sequence such that ${x_0=1}$ and for ${n \geq 0}$

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

Show that the infinite series ${x_0+x_1+x_2+...}$ converges and find its sum.

Hints: First note that ${e^x\geq x+1}$ and see that ${x_n \geq 0}$. Exponentiate to find ${e^{x_{n+1}} = e^{x_n}-x_n}$ which will give the monotonicity of the sequence (and the convergence) and also a telescopic expression for ${x_n}$. Summing ${x_n}$ becomes a simple expresion in terms of the limit of ${x_n}$.

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

Hints: I was surprised to see this, since it is a classical problem… Just pick the triangle ${ABC}$ with vertices in ${S}$ which has the largest area… Then consider the triangle whose midpoints are ${A,B,C}$. This triangle will contain ${S}$.

One way to make this more challenging would be to consider a bounded set ${S}$ in the plane, not necessarily finite… I’ll come back in the next days with more solutions. Problem A4 was particularily interesting and I’ll dedicate a post in order to present it.