[Solutions] William Lowell Putnam Mathematical Competition 2020

1. How many positive integers $N$ satisfy all of the following three conditions?
• $N$ is divisible by $2020$.
• $N$ has at most $2020$ decimal digits.
• The decimal digits of $N$ are a string of consecutive ones followed by a string of consecutive zeros.
2. Let $k$ be a nonnegative integer. Evaluate \[ \sum_{j=0}^k 2^{k-j} \binom{k+j}{j}. \]
3. Let $a_0=\pi /2$, and let $a_n=\sin (a_{n-1})$ for $n\ge 1$. Determine whether \[ \sum_{n=1}^{\infty}a_n^2 \] converges.
4. Consider a horizontal strip of $N+2$ squares in which the first and the last square are black and the remaining $N$ squares are all white. Choose a white square uniformly at random, choose one of its two neighbors with equal probability, and color tis neighboring square black if it is not already black. Repeat this process until all the remaining white squares have only black neighbors. Let $w(N)$ be the expected number of white squares remaining. Find \[ \lim_{N\to\infty}\frac{w(N)}{N}.\]
5. Let $a_n$ be the number of sets $S$ of positive integers for which \[ \sum_{k\in S}F_k=n,\]where the Fibonacci sequence $(F_k)_{k\ge 1}$ satisfies $F_{k+2}=F_{k+1}+F_k$ and begins $F_1=1$, $F_2=1$, $F_3=2$, $F_4=3$. Find the largest number $n$ such that $a_n=2020$.
6. For a positive integer $N$, let $f_N$ be the function defined by \[ f_N (x)=\sum_{n=0}^N \frac{N+1/2-n}{(N+1)(2n+1)} \sin\left((2n+1)x \right). \] Determine the smallest constant $M$ such that $f_N (x)\le M$ for all $N$ and all real $x$.
7. For a positive integer $n$, define $d(n)$ to be the sum of the digits of $n$ when written in binary (for example, $d(13)=1+1+0+1=3$). Let \[S=\sum_{k=1}^{2020}(-1)^{d(k)}k^3.\] Determine $S$ modulo $2020$.
8. Let $k$ and $n$ be integers with $1\leq k<n$. Alice and Bob play a game with $k$ pegs in a line of $n$ holes. At the beginning of the game, the pegs occupy the $k$ leftmost holes. A legal move consists of moving a single peg to any vacant hole that is further to the right. The players alternate moves, with Alice playing first. The game ends when the pegs are in the $k$ rightmost holes, so whoever is next to play cannot move and therefore loses. For what values of $n$ and $k$ does Alice have a winning strategy?
9. Let $x_0=1$, and let $\delta$ be some constant satisfying $0<\delta<1$. Iteratively, for $n=0,1,2,\dots$, a point $x_{n+1}$ is chosen uniformly form the interval $[0,x_n]$. Let $Z$ be the smallest value of $n$ for which $x_n<\delta$. Find the expected value of $Z$, as a function of $\delta$.
10. Let $n$ be a positive integer, and let $V_n$ be the set of integer $(2n+1)$-tuples $\mathbf{v}=(s_0,s_1,\cdots,s_{2n-1},s_{2n})$ for which $s_0=s_{2n}=0$ and $|s_j-s_{j-1}|=1$ for $j=1,2,\cdots,2n$. Define \[q(\mathbf{v})=1+\sum_{j=1}^{2n-1}3^{s_j},\] and let $M(n)$ be the average of $\frac{1}{q(\mathbf{v})}$ over all $\mathbf{v}\in V_n$. Evaluate $M(2020)$.
11. For $j \in \{ 1,2,3,4\}$, let $z_j$ be a complex number with $| z_j | = 1$ and $z_j \neq 1$. Prove that $$3 - z_1 - z_2 - z_3 - z_4 + z_1z_2z_3z_4 \neq 0.$$
12. Let $n$ be a positive integer. Prove that $$\sum_{k=1}^n (-1)^{\lfloor k (\sqrt{2} - 1) \rfloor} \geq 0.$$(As usual, $\lfloor x \rfloor$ denotes the greatest integer less than or equal to $x$.)

DOWNLOAD SOLUTIONS