Olympiad problems

2020 Putnam, B6

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$.)

2020 Putnam, B5

Tags: Putnam , Putnam 2020

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.$$

2020 Putnam, B1

Tags: Putnam , abstract algebra , Putnam 2020

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$.

2020 Putnam, A1

Tags: Putnam , Putnam 2020

How many positive integers $N$ satisfy all of the following three conditions?\\ (i) $N$ is divisible by $2020$.\\ (ii) $N$ has at most $2020$ decimal digits.\\ (iii) The decimal digits of $N$ are a string of consecutive ones followed by a string of consecutive zeros.

2020 Putnam, A2

Tags: Putnam , Putnam 2020 , college contests , Binomial identites

Let $k$ be a nonnegative integer. Evaluate \[ \sum_{j=0}^k 2^{k-j} \binom{k+j}{j}. \]

2020 Putnam, A5

Tags: Putnam , Putnam 2020

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$.

2020 Putnam, A6

Tags: Putnam , Putnam 2020

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$.

2020 Putnam, B2

Tags: Putnam , Putnam 2020

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?

2020 Putnam, A4

Tags: Putnam , Putnam 2020

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}.\]

2020 Putnam, A3

Tags: Putnam , Putnam 2020 , college contests , real analysis

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.

2020 Putnam, B4

Tags: Putnam , Putnam 2020

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)$.

2020 Putnam, B3

Tags: Putnam , probability , expected value , function , Putnam 2020

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$.