Putnam 2025

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

(a) $a_{i,j} = 0$ when $i+j\leq n$;

(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

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