putnam – Power Overwhelming

(EDIT: These solutions earned me a slot in N1, top 16.)

I solved eight problems on the Putnam last Saturday. Here were the solutions I found during the exam, plus my repaired solution to B3 (the solution to B3 I submitted originally had a mistake).

Some comments about the test. I thought that the A test was mostly very easy: problems A1, A3, A4 were all routine, and problem A5 is a little long-winded but nothing magical. Problem A2 was tricky, and took me well over half the A session. I don’t know anything about A6, but it seems to be very hard.

The B session, on the other hand, was completely bizarre. In my opinion, the difficulty of the problems I did attempt was

$\displaystyle B4 \ll B1 \ll B5 < B3 < B2.$

1. Problems

1.1. Day A

Points ${A}$ and ${B}$ are on the same branch of the hyperbola ${xy=1}$ . Point ${P}$ is selected between them maximizing the area of ${\triangle ABP}$ . Show that the area of region bounded by the hyperbola and ${AP}$ equals the area of region bounded by the hyperbola and ${BP}$ .
Define ${a_0 = 1}$ , ${a_1 = 2}$ and ${a_n = 4a_{n-1} - a_{n-2}}$ . Find an odd prime dividing ${a_{2015}}$ .
Compute
$\displaystyle \log_2 \prod_{a=1}^{2015} \prod_{b=1}^{2015} \left( 1 + e^{\frac{2\pi i a b}{2015}} \right).$
Let ${f(x) = \sum_{n \in S_x} 2^{-n}}$ where ${S_x = \{ n \in \mathbb Z^+ \mid \left\lfloor nx \right\rfloor \text { even} \}}$ . Compute ${\inf_{x \in [0,1)} f(x)}$ .
Let ${q \ge 1}$ be an odd integer and define
$\displaystyle N_q = \# \left\{ 0 < a < q/4 \mid \gcd(a,q) = 1 \right\}.$

Prove ${N_q}$ is odd if and only if ${q = p^k}$ for some prime ${p \equiv 5,7 \pmod8}$ .
Let ${A}$ , ${B}$ , ${M}$ , ${X}$ be ${n \times n}$ real matrices. Prove that if ${AM = MB}$ and ${A}$ , ${B}$ have the same characteristic polynomial then ${\det(A-MX) = \det(B-XM)}$ .

1.2. Night B

Let ${f : \mathbb R \rightarrow \mathbb R}$ be thrice differentiable. Prove that if ${f}$ has at least five distinct roots then ${f + 6f' + 12f'' + 8f'''}$ has at least two distinct roots.
Starting with the list of positive integers ${1, 2, 3, \dots}$ , we repeatedly remove the first three elements as well as their sum, giving a sequence of sums ${1+2+3=6}$ , ${4+5+7=16}$ , ${8+9+10=27}$ , ${11+12+13=36}$ , ${14+15+17=46}$ , and so on. Decide whether some sum in the sequence ends with ${2015}$ in base ${10}$ .
Define ${S}$ to be the set of real matrices ${\left(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right)}$ such that ${a}$ , ${b}$ , ${c}$ , ${d}$ form an arithmetic progression in that order. Find all ${M \in S}$ such that for some integer ${k > 1}$ , ${M^k \in S}$ .
Let ${ T = \left\{(a,b,c) \in \mathbb Z_+^3 \mid a,b,c \text{ are sides of a triangle} \right\} }$ . Prove that
$\displaystyle \sum_{(a,b,c) \in T} \frac{2^a}{3^b5^c}$

is rational and determine its value.
Let ${P_n}$ be the number of permutations ${\pi : \{1, \dots, n\} \rightarrow \{1, \dots, n\}}$ such that ${|\pi(i)-\pi(j)| \le 2}$ where ${|i-j| \le 1}$ . For any ${n \ge 2}$ show that
$\displaystyle P_{n+5} - P_{n+4} - P_{n+3} + P_n$

does not depend on ${n}$ and determine its value.
Let ${a(k)}$ be the number of odd divisors of ${k}$ in the interval ${[1, \sqrt{2k})}$ . Compute
$\displaystyle \sum_{k \ge 1} \frac{(-1)^{k-1} a(k)}{k}.$

2. Solution to Problem A1

Standard A1 fare. WLOG ${A}$ is to the left of ${B}$ on the positive branch. First we claim the tangent to ${P}$ must be parallel to line ${AB}$ ; otherwise let it intersect the parabola again at ${P'}$ , and any point between ${P}$ and ${P'}$ will increase the area of ${\triangle ABP}$ . In that case, we must have

$\displaystyle -\frac{1}{p^2} = \frac{\frac1a-\frac1b}{a-b} \implies p = \sqrt{ab}$

Now the area bounded by ${AP}$ is

$\displaystyle \frac{\frac1a+\frac1p}{2} \cdot (p-a) - \int_a^p \frac 1x \; dx = \frac{1}{2}\left( \frac pa - \frac ap \right) - \log \left( \frac pa \right).$

The area of ${BP}$ is computed similarly and gives

$\displaystyle \frac{1}{2}\left( \frac bp - \frac pb \right) - \log \left( \frac bp \right)$

and so these are equal.

3. Solution to Problem A2

By induction we have ${a_n = \frac12\left( (2+\sqrt3)^n+(2-\sqrt3)^n \right)}$ . Thus ${a_{m} \mid a_{(2k+1)m}}$ for any ${k}$ , ${m}$ , because their quotient is both rational and an algebraic integer. Thus ${a_5 = 362 = 2 \cdot \boxed{181}}$ .

During the test, I only found this solution by computing ${a_1}$ , \dots, ${a_{11}}$ explicitly and factoring the first ${10}$ numbers, upon which I realized ${a_3 \mid a_9}$ .

4. Solution to Problem A3

First, we use the fact that for any odd integer ${m}$ , we have

$\displaystyle \prod_{1 \le b \le m} (1 + \zeta^b) = 2$

where ${\zeta}$ is an ${m}$ th root of unity. (Just plug ${-1}$ into ${X^m-1}$ .) Thus

$\displaystyle \begin{aligned} \log_2 \prod_{a=1}^{2015} \prod_{b=1}^{2015} \left( 1 + e^{\frac{2\pi i a b}{2015}} \right) &= \log_2 \prod_{a=1}^{2015} 2^{\gcd(a,2015)} \\ &= \sum_{a=1}^{2015} \gcd(a,2015) \\ &= \sum_{d \mid 2015} \frac{2015}{d} \phi(d) \\ &= (5+\phi(5))(13+\phi(13))(31+\phi(31)) \\ &= 9 \cdot 25 \cdot 61 \\ &= \boxed{13725}. \end{aligned}$

5. Solution to Problem A4

We first prove that ${f(x) \ge \frac47}$ for every ${x \in [0,1)}$ . It suffices to consider ${x \ge \frac{1}{2}}$ since otherwise ${f(x) \ge \frac12+\frac14}$ . We note that for any ${k}$ , if ${k \notin S_x}$ and ${k+1 \notin S_x}$ then we require that ${\left\lfloor kx \right\rfloor = \left\lfloor (k+1)x \right\rfloor = 2m+1}$ for some ${m}$ ; since ${1 \le 2x < 2}$ this implies ${\left\lfloor (k+2)x \right\rfloor = 2m+2}$ .

Thus among any three consecutive numbers, at least one is in ${S_x}$ . Plainly ${1 \in S_x}$ and hence ${f(x) \ge 2^{-1} + 2^{-4} + 2^{-7} + \dots = \frac47}$ .

Finally note that

$\displaystyle f\left( \frac23-\varepsilon \right) \rightarrow \frac47 \quad\text{as}\quad x \rightarrow \frac23$

so the answer is ${L = \boxed{\frac47}}$ .

6. Solution to Problem A5

Let ${q = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}}$ . By Principle of Inclusion-Exclusion (or Moebius inversion?) we have

$\displaystyle N_q = \sum_{S \subset \{1, \dots, n\}} (-1)^{|S|} \left\lfloor \frac{q}{4\prod_{s \in S} p_s} \right\rfloor .$

The ${(-1)^{|S|}}$ vanishes when taking modulo ${2}$ . Now, ${\left\lfloor \frac{\bullet}{4} \right\rfloor \pmod 2}$ depends only on the input modulo ${8}$ , equalling ${0}$ for ${1,3 \pmod 8}$ and ${1}$ for ${5,7\pmod8}$ . As ${p^2 \equiv 1 \pmod 8}$ the exponents in the floor also can be taken mod ${2}$ . Therefore, we can simplify this to

$\displaystyle N_q \equiv \sum_{S \subset \{1, \dots, n\}} \left\lfloor \frac{q\prod_{s \in S} p_s}{8} \right\rfloor \pmod 2.$

Let ${A(S) = \left\lfloor \frac{q\prod_{s \in S} p_s}{8} \right\rfloor \pmod 2}$ . The solution now proceeds in three cases.

If any prime is ${1}$ or ${3}$ mod ${8}$ , say ${p_1}$ , then ${A(T) = A(T \cup \{1\})}$ for ${T \subset \{2, \dots, n\}}$ and thus ${N_q}$ is even.

If all primes are ${5}$ or ${7}$ mod ${8}$ and ${n \ge 2}$ , then ${A(T) = A(T \cup \{1,2\})}$ and ${A(T \cup \{1\}) = A(T \cup \{2\})}$ for ${T \subset \{3, \dots, n\}}$ and thus ${N_q}$ is even.

But if ${n = 1}$ and ${p_1 \equiv 5,7 \pmod 8}$ then ${A(\varnothing) + A(\{1\})}$ is always odd. This completes the proof.

7. Solution to Problem B1

Let ${X(f) = f + 2f'}$ . The problem asks to show ${f}$ having five distinct real roots implies ${X(X(X(f)))}$ has at least two. But by Rolle’s Theorem on

$\displaystyle g(x) = e^{\frac{1}{2} x} f(x) \implies 2g'(x) = e^{\frac{1}{2} x}(f(x) + 2f'(x))$

we see that ${f}$ having ${k}$ roots gives ${X(f)}$ having ${k-1}$ roots, so done. (I’m told the trick of considering this function ${g}$ is not new, though I came up with it during the exam so I can’t verify this.)

Lots of people said something about trying to use the Intermediate Value Theorem to show that ${X(f)}$ has a root between any two roots of ${f}$ . This would require ${f}$ to be continuously differentiable, so it breaks down at the last application to ${X(X(X(f)))}$ . I deliberately appealed to Rolle’s Theorem because I didn’t trust myself to deal with these real-analytic issues during the exam.

8. Solution to Problem B3

The answer is

$\displaystyle \begin{pmatrix} t&t\\t&t \end{pmatrix} \quad\text{and}\quad \begin{pmatrix} -3t&-t\\t&3t \end{pmatrix}$

for ${t \in \mathbb R}$ . These work by taking ${k=3}$ .

Now to see these are the only ones, consider an arithmetic matrix

$\displaystyle M = \begin{pmatrix} a & a+e \\ a+2e & a+3e \end{pmatrix}.$

which is not zero everywhere. Its characteristic polynomial is ${t^2 - (2a+3e)t - 2e^2}$ , with discriminant ${(2a+3e)^2 + 8e^2}$ , so it has two distinct real roots; moreover, since ${-2e^2 \le 0}$ either one of the roots is zero or they are of opposite signs.

Now we can diagonalize ${M}$ by writing

$\displaystyle M = \begin{pmatrix} s & -q \\ -r & p \end{pmatrix} \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \begin{pmatrix} p & q \\ r & s \end{pmatrix} = \begin{pmatrix} ps\lambda_1 - qr\lambda_2 & qs(\lambda_1-\lambda_2) \\ pr(\lambda_2-\lambda_1) & ps\lambda_2 - qr\lambda_1 \end{pmatrix}$

where ${ps-qr=1}$ . By using the fact the diagonal entries have sum equalling the off-diagonal entries, we obtain that

$\displaystyle (ps-qr)(\lambda_1+\lambda_2) = (qs-pr)(\lambda_1-\lambda_2) \implies qs-pr = \frac{\lambda_1+\lambda_2}{\lambda_1-\lambda_2}.$

Now if ${M^k \in S}$ too then the same calculation gives

$\displaystyle qs-pr = \frac{\lambda_1^k+\lambda_2^k}{\lambda_1^k-\lambda_2^k}.$

Let ${x = \lambda_1/\lambda_2 < 0}$ (since ${-2e^2 < 0}$ ). We appropriately get

$\displaystyle \frac{x+1}{x-1} = \frac{x^k+1}{x^k-1} \implies \frac{2}{x-1} = \frac{2}{x^k-1} \implies x = x^k \implies x = -1 \text{ or } x = 0$

and ${k}$ odd. If ${x=0}$ we get ${e=0}$ and if ${x=-1}$ we get ${2a+3e=0}$ , which gives the curve of solutions that we claimed. (Unfortunately, during the test I neglected to address ${x=-1}$ , which probably means I will get null marks.)

9. Solution to Problem B4

By the Ravi substitution,

$\displaystyle \begin{aligned} \sum_{(a,b,c) \in T} \frac{2^a}{3^b5^c} &= \sum_{x,y,z \ge 1 \text{ odd}} \frac{2^\frac{y+z}{2}}{3^{\frac{z+x}{2}} 5^{\frac{x+y}{2}}} + \sum_{x,y,z \ge 2 \text{ even}} \frac{2^\frac{y+z}{2}}{3^{\frac{z+x}{2}} 5^{\frac{x+y}{2}}} \\ &= \sum_{u,v,w \ge 1} \frac{2^{v+w}}{3^{w+u}5^{u+v}} \left( 1 + \frac{2^{-1}}{3^{-1}5^{-1}} \right) \\ &= \frac{17}{2} \sum_{u,v,w \ge 1} \left(\frac{1}{15}\right)^u \left(\frac25\right)^v \left(\frac23\right)^w \\ &= \frac{17}{2} \frac{\frac{1}{15}}{1-\frac{1}{15}} \frac{\frac25}{1-\frac25}\frac{\frac23}{1-\frac23} \\ &= \boxed{\frac{17}{21}}. \end{aligned}$

No idea why this was B4; it was by far the easiest problem on the test for me. I knew how to do it in less than a second on seeing it and the rest was just arithmetic. (We use the Ravi substitution all the time on olympiad inequalities, so it’s practically a reflex for me.)

10. Solution to Problem B5

My solution was long and disgusting, so I won’t write out the full details. The idea is to let ${A_n}$ be the number of permutations in ${P_{n+1}}$ with the additional property that ${\pi(1) = 1}$ . By casework on the index ${k}$ with ${\pi(k) = 1}$ (which must be surrounded by ${2}$ or ${3}$ if ${k \neq 1, n}$ ) one obtains

$\displaystyle P_n = 2(A_0 + A_1 + \dots + A_{n-3} + A_{n-1}) \qquad n \ge 2.$

Also by more casework one obtains the recursion

$\displaystyle A_n = A_{n-1} + A_{n-3} + 1 \qquad n \ge 3.$

From this one obtains

$\displaystyle P_n - P_{n-1} = 2(A_{n-1}-A_{n-2}+A_{n-3}) = 2(A_{n-3}+A_{n-4}+1).$

So we know ${P_{n+5}-P_{n+4}}$ and can compute ${P_{n+3}-P_n = (P_{n+3}-P_{n+2}) + (P_{n+2}-P_{n+1}) + (P_{n+1}-P_n)}$ so a long algebraic computation gives that these differ by ${\boxed 4}$ .

Also, I swear I’ve seen the exact condition ${|\pi(i)-\pi(j)|\le 2}$ many years ago, back when I was doing high school olympiads. But it was so long ago I don’t remember the source.