Putnam 2016

Random number: 08

4th December 2016

On Saturday the 3rd of December, I got my mind and body whipped so hard that everything inverted and was replaced in a flash of light in the event known as the Putnam. It's been a day however, so let's look back at the exam in an act of retrospection.

A1. 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) = \frac{d^j}{dx^j}p(x)\Big|_{x=k}$$ (the $j$-th derivative of $p(x)$ at $k$) is divisible by 2016.

My Cool Solution:

I claim that $j = 8$. Take an arbitrary polynomial $p(x) = a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$. Then we have that: $$\frac{d^8}{dx^8}p(x) = \sum_{m} a_m(m)(m-1)(m-2)...(m-6)(m-7)x^{m-8}$$ When evaluated at an integer $k$, it's clear that all of the terms in the sum above are integers, and that they divide eight consecutive integers. Out of these eight, at least 3 must be divisible by 2, and one of those by 4, meaning that each term is divisible by $2^5$. Also, at least two of the eight integers are divisible by 3, and one divisible by 7, which means that each term is divisible by 9 and 7. This means that each term in the sum is divisible by $2^5*9*7 = 2016$, hence the eighth derivative of any polynomial is divisble by 2016.

To prove that $j = 8$ is minimal, the polynomial $q(x) = x^7$ is a counterexample for $j = 1, 2, 3,...7$, as $$q^{(j)}(1) \text{ mod } 2016 \neq 0$$ And that concludes my beautiful proof.

A2. Given a positive integer $n$, let $M(n)$ be the largest integer $m$ such that $${{m}\choose{n-1}} > {{m-1}\choose{n}}$$ Evaluate $$\lim_{n \rightarrow \infty} \frac{M(n)}{n}$$

My Cool Solution:

$${{m}\choose{n-1}} > {{m-1}\choose{n}}$$ $$\frac{m!}{(n-1)!}{(m-n+1)!} > \frac{(m-1)!}{n!(m-n-1)!}$$ $$m^2 + (1-3n)m + (n^2 - n) < 0$$ For a given $n$, we can use the quadratic formula:

$$\frac{(3n-1) - \sqrt{5n^2-2n+1}}{2} < m < \frac{(3n-1) + \sqrt{5n^2-2n+1}}{2}$$ $$\frac{(3n-1) + \sqrt{5n^2-2n+1}}{2}-1 < M(n) < \frac{(3n-1) + \sqrt{5n^2-2n+1}}{2}$$ $$\frac{(3-\frac{1}{n}) + \sqrt{5-\frac{2}{n}+\frac{1}{n^2}}}{2}-\frac{1}{n} < \frac{M(n)}{n} < \frac{(3-\frac{1}{n}) + \sqrt{5-\frac{2}{n}+\frac{1}{n^2}}}{2}$$ Now we can apply the squeeze theorem, as the lower bound and upper bound both limit to the same number as $n \rightarrow \infty$. We find then that $$\lim_{n \rightarrow \infty} M(n) = \frac{3 + \sqrt{5}}{2}$$ And that concludes my beautiful proof.

A3. Suppose that $f$ is a function from $\mathbb{R}$ to $\mathbb{R}$ such that $$f(x) + f(1-\frac{1}{x}) = \text{arctan}(x)$$ for all real $x \neq 0$. (As usual, $y = \text{arctan}(x)$ means $-\pi /2 < y < \pi /2$ and $\text{tan}(y) = x$.) Find $$\int_0^1 f(x) dx$$

I'll write up the proof for this tomorrow.