Putnam Archive

Let $m_0$ and $n_0$ be distinct positive integers. For every positive integer $k$, define $m_k$ and $n_k$ to be the relatively prime positive integers such that $$\frac{m_k}{n_k} = \frac{2m_{k-1} + 1}{2n_{k-1}+1}.$$ Prove that $2m_k+1$ and $2n_k+1$ are relatively prime for all but finitely many positive integers $k$.

Find the largest real number $a$ and the smallest real number $b$ such that $$ax(\pi-x) \leq \sin x \leq bx(\pi-x)$$ for all $x$ in the interval $[0, \pi]$.

Alice and Bob play a game with a string of $n$ digits, each of which is restricted to be $0$, $1$, or $2$. Initially all the digits are $0$. A legal move is to add or subtract $1$ from one digit to create a new string that has not appeared before. A player with no legal move loses, and the other player wins. Alice goes first, and the players alternate moves. For each $n \geq 1$, determine which player has a strategy that guarantees winning.

Find the minimal value of $k$ such that there exist $k$-by-$k$ real matrices $A_1, \dots, A_{2025}$ with the property that $A_i A_j = A_j A_i$ if and only if $|i-j| \in \{0,1,2024\}$.

Let $n$ be an integer with $n \geq 2$. For a sequence $s = (s_1,\dots,s_{n-1})$ where each $s_i = \pm 1$, let $f(s)$ be the number of permutations $(a_1,\dots,a_n)$ of $\{1,2,\dots,n\}$ such that $s_i(a_{i+1}-a_i) > 0$ for all $i$. For each $n$, determine the sequences $s$ for which $f(s)$ is maximal.

Let $b_0 = 0$ and, for $n \geq 0$, define $b_{n+1} = 2b_n^2 + b_n + 1$. For each $k \geq 1$, show that $b_{2^{k+1}} - 2b_{2^k}$ is divisible by $2^{2k+2}$ but not by $2^{2k+3}$.

Suppose that each point in the plane is colored either red or green, subject to the following condition: For every three noncollinear points $A,B,C$ of the same color, the center of the circle passing through $A,B$ and $C$ is also this color. Prove that all points of the plane are the same color.

Let $f\colon [0,1] \to [0, \infty)$ be strictly increasing and continuous. Let $R$ be the region bounded by $x=0$, $x=1$, $y=0$, and $y=f(x)$. Let $x_1$ be the $x$-coordinate of the centroid of $R$. Let $x_2$ be the $x$-coordinate of the centroid of the solid generated by rotating $R$ around the $x$-axis. Prove that $x_1 < x_2$.

Suppose $S$ is a nonempty set of positive integers with the property that if $n$ is in $S$, then every positive divisor of $2025^n -15^n$ is in $S$. Must $S$ contain all positive integers?

For $n \geq 2$, let $A = [a_{i,j}]_{i,j=1}^n$ be an $n$-by-$n$ matrix of nonnegative integers such that

1. (a)
   $a_{i,j} = 0$ when $i+j\leq n$;
2. (b)
   $a_{i+1,j} \in \{a_{i,j}, a_{i,j}+1\}$ when $1 \leq i \leq n-1$ and $1 \leq j \leq n$; and
3. (c)
   $a_{i,j+1} \in \{a_{i,j}, a_{i,j}+1\}$ when $1 \leq i \leq n$ and $1 \leq j \leq n-1$.

Let $S$ be the sum of the entries of $A$, and let $N$ be the number of nonzero entries of $A$. Prove that $$S \leq \frac{(n+2)N}{3}.$$

Let $p$ be a prime number greater than $3$. For each $k \in \{1,\dots,p-1\}$, let $I(k) \in \{1,2,\dots,p-1\}$ be such that $k \cdot I(k) \equiv 1 \pmod{p}$. Prove that the number of integers $k \in \{1,\dots,p-2\}$ such that $I(k+1) < I(k)$ is greater than $p/4-1$.

Let $\mathbb{N} = \{1,2,3,\dots\}$. Find the largest real constant $r$ such that there exists a function $g\colon \mathbb{N} \to \mathbb{N}$ such that $$g(n+1)-g(n) \geq (g(g(n)))^r$$ for all $n \in \mathbb{N}$.

Determine all positive integers $n$ for which there exist positive integers $a$, $b$, and $c$ satisfying $$2a^n + 3b^n = 4c^n.$$

For which real polynomials $p$ is there a real polynomial $q$ such that $$p(p(x)) - x = (p(x) - x)^2 q(x)$$ for all real $x$?

Let $S$ be the set of bijections $$T \colon \{1,2,3\} \times \{1,2,\dots,2024\} \to \{1,2,\dots,6072\}$$ such that $T(1,j) < T(2,j) < T(3,j)$ for all $j \in \{1,2,\dots,2024\}$ and $T(i,j) < T(i,j+1)$ for all $i \in \{1,2,3\}$ and $j \in \{1,2,\dots,2023\}$. Do there exist $a$ and $c$ in $\{1,2,3\}$ and $b$ and $d$ in $\{1,2,\dots,2024\}$ such that the fraction of elements $T$ in $S$ for which $T(a,b) < T(c,d)$ is at least $1/3$ and at most $2/3$?

Find all primes $p > 5$ for which there exists an integer $a$ and an integer $r$ satisfying $1 \leq r \leq p-1$ with the following property: the sequence $1,a,a^2,\dots,a^{p-5}$ can be rearranged to form a sequence $b_0,b_1,b_2,\dots,b_{p-5}$ such that $b_n-b_{n-1}-r$ is divisible by $p$ for $1 \leq n \leq p-5$.

Consider a circle $\Omega$ with radius 9 and center at the origin $(0,0)$, and a disc $\Delta$ with radius 1 and center at $(r,0)$, where $0 \leq r \leq 8$. Two points $P$ and $Q$ are chosen independently and uniformly at random on $\Omega$. Which value(s) of $r$ minimize the probability that the chord $\overline{PQ}$ intersects $\Delta$?

Let $c_0,c_1,c_2,\dots$ be the sequence defined so that $$\frac{1-3x-\sqrt{1-14x+9x^2}}{4} = \sum_{k=0}^\infty c_k x^k$$ for sufficiently small $x$. For a positive integer $n$, let $A$ be the $n$-by-$n$ matrix with $i,j$-entry $c_{i+j-1}$ for $i$ and $j$ in $\{1,\dots,n\}$. Find the determinant of $A$.

Let $n$ and $k$ be positive integers. The square in the $i$th row and $j$th column of an $n$-by-$n$ grid contains the number $i+j-k$. For which $n$ and $k$ is it possible to select $n$ squares from the grid, no two in the same row or column, such that the numbers contained in the selected squares are exactly $1,2,\dots,n$?

Two convex quadrilaterals are called partners if they have three vertices in common and they can be labeled $ABCD$ and $ABCE$ so that $E$ is the reflection of $D$ across the perpendicular bisector of the diagonal $\overline{AC}$. Is there an infinite sequence of convex quadrilaterals such that each quadrilateral is a partner of its successor and no two elements of the sequence are congruent? [A diagram has been omitted.]

Let $r_n$ be the $n$th smallest positive solution to $\tan x = x$, where the argument of tangent is in radians. Prove that $$0 < r_{n+1} - r_n - \pi < \frac{1}{(n^2+n)\pi}$$ for $n \geq 1$.

Let $n$ be a positive integer. Set $a_{n,0} = 1$. For $k \geq 0$, choose an integer $m_{n,k}$ uniformly at random from the set $\{1,\dots,n\}$, and let $$a_{n,k+1} = \begin{cases} a_{n,k} + 1, & \mbox{if $m_{n,k} > a_{n,k};$} \\ a_{n,k}, & \mbox{if $m_{n,k} = a_{n,k}$;} \\ a_{n,k}-1, & \mbox{if $m_{n,k} < a_{n,k}$.} \end{cases}$$ Let $E(n)$ be the expected value of $a_{n,n}$. Determine $\lim_{n\to \infty} E(n)/n$.

Let $k$ and $m$ be positive integers. For a positive integer $n$, let $f(n)$ be the number of integer sequences $x_1,\dots,x_k,y_1,\dots,y_m,z$ satisfying $1 \leq x_1 \leq \cdots \leq x_k \leq z \leq n$ and $1 \leq y_1 \leq \cdots \leq y_m \leq z \leq n$. Show that $f(n)$ can be expressed as a polynomial in $n$ with nonnegative coefficients.

For a real number $a$, let $F_a(x) = \sum_{n \geq 1} n^a e^{2n} x^{n^2}$ for $0 \leq x < 1$. Find a real number $c$ such that

For a positive integer $n$, let $f_n(x) = \cos(x) \cos(2x) \cos(3x) \cdots \cos(nx)$. Find the smallest $n$ such that $|f_n''(0)| > 2023$.

Let $n$ be an even positive integer. Let $p$ be a monic, real polynomial of degree $2n$; that is to say, $p(x) = x^{2n} + a_{2n-1} x^{2n-1} + \cdots + a_1 x + a_0$ for some real coefficients $a_0, \dots, a_{2n-1}$. Suppose that $p(1/k) = k^2$ for all integers $k$ such that $1 \leq |k| \leq n$. Find all other real numbers $x$ for which $p(1/x) = x^2$.

Determine the smallest positive real number $r$ such that there exist differentiable functions $f\colon \mathbb{R} \to \mathbb{R}$ and $g\colon \mathbb{R} \to \mathbb{R}$ satisfying

1. (a)
   $f(0) > 0$,
2. (b)
   $g(0) = 0$,
3. (c)
   $|f'(x)| \leq |g(x)|$ for all $x$,
4. (d)
   $|g'(x)| \leq |f(x)|$ for all $x$, and
5. (e)
   $f(r) = 0$.

Let $v_1, \dots, v_{12}$ be unit vectors in $\mathbb{R}^3$ from the origin to the vertices of a regular icosahedron. Show that for every vector $v \in \mathbb{R}^3$ and every $\varepsilon > 0$, there exist integers $a_1,\dots,a_{12}$ such that $\| a_1 v_1 + \cdots + a_{12} v_{12} - v \| < \varepsilon$.

For a nonnegative integer $k$, let $f(k)$ be the number of ones in the base 3 representation of $k$. Find all complex numbers $z$ such that $$\sum_{k=0}^{3^{1010}-1} (-2)^{f(k)} (z+k)^{2023} = 0.$$

Alice and Bob play a game in which they take turns choosing integers from $1$ to $n$. Before any integers are chosen, Bob selects a goal of “odd” or “even”. On the first turn, Alice chooses one of the $n$ integers. On the second turn, Bob chooses one of the remaining integers. They continue alternately choosing one of the integers that has not yet been chosen, until the $n$th turn, which is forced and ends the game. Bob wins if the parity of $\{k\colon \mbox{the number $k$ was chosen on the $k$th turn}\}$ matches his goal. For which values of $n$ does Bob have a winning strategy?

Consider an $m$-by-$n$ grid of unit squares, indexed by $(i,j)$ with $1 \leq i \leq m$ and $1 \leq j \leq n$. There are $(m-1)(n-1)$ coins, which are initially placed in the squares $(i,j)$ with $1 \leq i \leq m-1$ and $1 \leq j \leq n-1$. If a coin occupies the square $(i,j)$ with $i \leq m-1$ and $j \leq n-1$ and the squares $(i+1,j), (i,j+1)$, and $(i+1,j+1)$ are unoccupied, then a legal move is to slide the coin from $(i,j)$ to $(i+1,j+1)$. How many distinct configurations of coins can be reached starting from the initial configuration by a (possibly empty) sequence of legal moves?

For each positive integer $n$, let $k(n)$ be the number of ones in the binary representation of $2023 \cdot n$. What is the minimum value of $k(n)$?

A sequence $y_1,y_2,\dots,y_k$ of real numbers is called zigzag if $k=1$, or if $y_2-y_1, y_3-y_2, \dots, y_k-y_{k-1}$ are nonzero and alternate in sign. Let $X_1,X_2,\dots,X_n$ be chosen independently from the uniform distribution on $[0,1]$. Let $a(X_1,X_2,\dots,X_n)$ be the largest value of $k$ for which there exists an increasing sequence of integers $i_1,i_2,\dots,i_k$ such that $X_{i_1},X_{i_2},\dots,X_{i_k}$ is zigzag. Find the expected value of $a(X_1,X_2,\dots,X_n)$ for $n \geq 2$.

For a nonnegative integer $n$ and a strictly increasing sequence of real numbers $t_0,t_1,\dots,t_n$, let $f(t)$ be the corresponding real-valued function defined for $t \geq t_0$ by the following properties:

1. (a)
   $f(t)$ is continuous for $t \geq t_0$, and is twice differentiable for all $t>t_0$ other than $t_1,\dots,t_n$;
2. (b)
   $f(t_0) = 1/2$;
3. (c)
   $\lim_{t \to t_k^+} f'(t) = 0$ for $0 \leq k \leq n$;
4. (d)
   For $0 \leq k \leq n-1$, we have $f''(t) = k+1$ when $t_k < t< t_{k+1}$, and $f''(t) = n+1$ when $t>t_n$.

Considering all choices of $n$ and $t_0,t_1,\dots,t_n$ such that $t_k \geq t_{k-1}+1$ for $1 \leq k \leq n$, what is the least possible value of $T$ for which $f(t_0+T) = 2023$?

Determine which positive integers $n$ have the following property: For all integers $m$ that are relatively prime to $n$, there exists a permutation $\pi\colon \{1,2,\dots,n\} \to \{1,2,\dots,n\}$ such that $\pi(\pi(k)) \equiv mk \pmod{n}$ for all $k \in \{1,2,\dots,n\}$.

Let $n$ be a positive integer. For $i$ and $j$ in $\{1,2,\dots,n\}$, let $s(i,j)$ be the number of pairs $(a,b)$ of nonnegative integers satisfying $ai +bj=n$. Let $S$ be the $n$-by-$n$ matrix whose $(i,j)$ entry is $s(i,j)$. For example, when $n=5$, we have $S = \begin{bmatrix} 6 & 3 & 2 & 2 & 2 \\ 3 & 0 & 1 & 0 & 1 \\ 2 & 1 & 0 & 0 & 1 \\ 2 & 0 & 0 & 0 & 1 \\ 2 & 1 & 1 & 1 & 2 \end{bmatrix}$. Compute the determinant of $S$.

Determine all ordered pairs of real numbers $(a,b)$ such that the line $y = ax+b$ intersects the curve $y = \ln(1+x^2)$ in exactly one point.

Let $n$ be an integer with $n \geq 2$. Over all real polynomials $p(x)$ of degree $n$, what is the largest possible number of negative coefficients of $p(x)^2$?

Let $p$ be a prime number greater than 5. Let $f(p)$ denote the number of infinite sequences $a_1, a_2, a_3, \dots$ such that $a_n \in \{1, 2, \dots, p-1\}$ and $a_n a_{n+2} \equiv 1 + a_{n+1} \pmod{p}$ for all $n \geq 1$. Prove that $f(p)$ is congruent to 0 or 2 $\pmod{5}$.

Suppose that $X_1, X_2, \dots$ are real numbers between 0 and 1 that are chosen independently and uniformly at random. Let $S = \sum_{i=1}^k X_i/2^i$, where $k$ is the least positive integer such that $X_k < X_{k+1}$, or $k = \infty$ if there is no such integer. Find the expected value of $S$.

Alice and Bob play a game on a board consisting of one row of 2022 consecutive squares. They take turns placing tiles that cover two adjacent squares, with Alice going first. By rule, a tile must not cover a square that is already covered by another tile. The game ends when no tile can be placed according to this rule. Alice's goal is to maximize the number of uncovered squares when the game ends; Bob's goal is to minimize it. What is the greatest number of uncovered squares that Alice can ensure at the end of the game, no matter how Bob plays?

Let $n$ be a positive integer. Determine, in terms of $n$, the largest integer $m$ with the following property: There exist real numbers $x_1,\dots,x_{2n}$ with $-1 < x_1 < x_2 < \cdots < x_{2n} < 1$ such that the sum of the lengths of the $n$ intervals $$[x_1^{2k-1}, x_2^{2k-1}], [x_3^{2k-1},x_4^{2k-1}], \dots, [x_{2n-1}^{2k-1}, x_{2n}^{2k-1}]$$ is equal to 1 for all integers $k$ with $1 \leq k \leq m$.

Suppose that $P(x) = a_1 x + a_2 x^2 + \cdots + a_n x^n$ is a polynomial with integer coefficients, with $a_1$ odd. Suppose that $e^{P(x)} = b_0 + b_1 x + b_2 x^2 + \cdots$ for all $x$. Prove that $b_k$ is nonzero for all $k \geq 0$.

Let $\times$ represent the cross product in $\mathbb{R}^3$. For what positive integers $n$ does there exist a set $S \subset \mathbb{R}^3$ with exactly $n$ elements such that $$S = \{v \times w: v, w \in S\}?$$

Assign to each positive real number a color, either red or blue. Let $D$ be the set of all distances $d > 0$ such that there are two points of the same color at distance $d$ apart. Recolor the positive reals so that the numbers in $D$ are red and the numbers not in $D$ are blue. If we iterate this recoloring process, will we always end up with all the numbers red after a finite number of steps?

Find all integers $n$ with $n \geq 4$ for which there exists a sequence of distinct real numbers $x_1,\dots,x_n$ such that each of the sets

forms a 3-term arithmetic progression when arranged in increasing order.

For $0 \leq p \leq 1/2$, let $X_1, X_2, \dots$ be independent random variables such that $$X_i = \begin{cases} 1 & \mbox{with probability $p$,} \\ -1 & \mbox{with probability $p$,} \\ 0 & \mbox{with probability $1-2p$,} \end{cases}$$ for all $i \geq 1$. Given a positive integer $n$ and integers $b, a_1, \dots, a_n$, let $P(b, a_1, \dots, a_n)$ denote the probability that $a_1 X_1 + \cdots + a_n X_n = b$. For which values of $p$ is it the case that $$P(0, a_1, \dots, a_n) \geq P(b, a_1, \dots, a_n)$$ for all positive integers $n$ and all integers $b, a_1, \dots, a_n$?

Find all continuous functions $f: \mathbb{R}^+ \to \mathbb{R}^+$ such that $$f(xf(y)) + f(yf(x)) = 1 + f(x+y)$$ for all $x,y > 0$.

A grasshopper starts at the origin in the coordinate plane and makes a sequence of hops. Each hop has length $5$, and after each hop the grasshopper is at a point whose coordinates are both integers; thus, there are $12$ possible locations for the grasshopper after the first hop. What is the smallest number of hops needed for the grasshopper to reach the point $(2021, 2021)$?

For every positive real number $x$, let $$g(x) = \lim_{r \to 0} ((x+1)^{r+1} - x^{r+1})^{\frac{1}{r}}.$$ Find $\lim_{x \to \infty} \frac{g(x)}{x}$.

Determine all positive integers $N$ for which the sphere $$x^2 + y^2 + z^2 = N$$ has an inscribed regular tetrahedron whose vertices have integer coordinates.

Let $$I(R) = \iint_{x^2+y^2 \leq R^2} \left( \frac{1+2x^2}{1+x^4+6x^2y^2+y^4} - \frac{1+y^2}{2+x^4+y^4} \right)\,dx\,dy.$$ Find $$\lim_{R \to \infty} I(R),$$ or show that this limit does not exist.

Let $A$ be the set of all integers $n$ such that $1 \leq n \leq 2021$ and $\gcd(n, 2021) = 1$. For every nonnegative integer $j$, let $$S(j) = \sum_{n \in A} n^j.$$ Determine all values of $j$ such that $S(j)$ is a multiple of 2021.

Let $P(x)$ be a polynomial whose coefficients are all either $0$ or $1$. Suppose that $P(x)$ can be written as a product of two nonconstant polynomials with integer coefficients. Does it follow that $P(2)$ is a composite integer?

Suppose that the plane is tiled with an infinite checkerboard of unit squares. If another unit square is dropped on the plane at random with position and orientation independent of the checkerboard tiling, what is the probability that it does not cover any of the corners of the squares of the checkerboard?

Determine the maximum value of the sum $$S = \sum_{n=1}^\infty \frac{n}{2^n} (a_1 a_2 \cdots a_n)^{1/n}$$ over all sequences $a_1, a_2, a_3, \cdots$ of nonnegative real numbers satisfying $$\sum_{k=1}^\infty a_k = 1.$$

Let $h(x,y)$ be a real-valued function that is twice continuously differentiable throughout $\mathbb{R}^2$, and define $$\rho(x,y) = yh_x - xh_y.$$ Prove or disprove: For any positive constants $d$ and $r$ with $d>r$, there is a circle $\mathcal{S}$ of radius $r$ whose center is a distance $d$ away from the origin such that the integral of $\rho$ over the interior of $\mathcal{S}$ is zero.

Let $F_0, F_1, \dots$ be the sequence of Fibonacci numbers, with $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. For $m > 2$, let $R_m$ be the remainder when the product $\prod_{k=1}^{F_m-1} k^k$ is divided by $F_m$. Prove that $R_m$ is also a Fibonacci number.

Say that an $n$-by-$n$ matrix $A = (a_{ij})_{1 \leq i,j \leq n}$ with integer entries is very odd if, for every nonempty subset $S$ of $\{1,2,\dots,n\}$, the $|S|$-by-$|S|$ submatrix $(a_{ij})_{i,j \in S}$ has odd determinant. Prove that if $A$ is very odd, then $A^k$ is very odd for every $k \geq 1$.

Given an ordered list of $3N$ real numbers, we can trim it to form a list of $N$ numbers as follows: We divide the list into $N$ groups of $3$ consecutive numbers, and within each group, discard the highest and lowest numbers, keeping only the median.

Consider generating a random number $X$ by the following procedure: Start with a list of $3^{2021}$ numbers, drawn independently and uniformly at random between 0 and 1. Then trim this list as defined above, leaving a list of $3^{2020}$ numbers. Then trim again repeatedly until just one number remains; let $X$ be this number. Let $\mu$ be the expected value of $|X - \frac{1}{2}|$. Show that $$\mu \geq \frac{1}{4} \left( \frac{2}{3} \right)^{2021}.$$

How many positive integers $N$ satisfy all of the following three conditions?

1. (i)
   $N$ is divisible by 2020.
2. (ii)
   $N$ has at most 2020 decimal digits.
3. (iii)
   The decimal digits of $N$ are a string of consecutive ones followed by a string of consecutive zeros.

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

Let $a_0 = \pi/2$, and let $a_n = \sin(a_{n-1})$ for $n \geq 1$. Determine whether $$\sum_{n=1}^\infty a_n^2$$ converges.