Putnam 2018

Find all ordered pairs $(a,b)$ of positive integers for which $$\frac{1}{a} + \frac{1}{b} = \frac{3}{2018}.$$

Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some order, and let $M$ be the $(2^n-1) \times (2^n-1)$ matrix whose $(i,j)$ entry is $$m_{ij} = \begin{cases} 0 & \text{if }S_i \cap S_j = \emptyset; \\ 1 & \text{otherwise.} \end{cases}$$ Calculate the determinant of $M$.

Determine the greatest possible value of $\sum_{i=1}^{10} \cos(3x_i)$ for real numbers $x_1,x_2,\dots,x_{10}$ satisfying $\sum_{i=1}^{10} \cos(x_i) = 0$.

Let $m$ and $n$ be positive integers with $\gcd(m,n) = 1$, and let $$a_k = \left\lfloor \frac{mk}{n} \right\rfloor - \left\lfloor \frac{m(k-1)}{n} \right\rfloor$$ for $k=1,2,\dots,n$. Suppose that $g$ and $h$ are elements in a group $G$ and that $$gh^{a_1} gh^{a_2} \cdots gh^{a_n} = e,$$ where $e$ is the identity element. Show that $gh= hg$. (As usual, $\lfloor x \rfloor$ denotes the greatest integer less than or equal to $x$.)

Let $f: \mathbb{R} \to \mathbb{R}$ be an infinitely differentiable function satisfying $f(0) = 0$, $f(1)= 1$, and $f(x) \geq 0$ for all $x \in \mathbb{R}$. Show that there exist a positive integer $n$ and a real number $x$ such that $f^{(n)}(x) < 0$.

Suppose that $A,B,C,$ and $D$ are distinct points, no three of which lie on a line, in the Euclidean plane. Show that if the squares of the lengths of the line segments $AB$, $AC$, $AD$, $BC$, $BD$, and $CD$ are rational numbers, then the quotient $$\frac{\mathrm{area}(\triangle ABC)}{\mathrm{area}(\triangle ABD)}$$ is a rational number.

Let $\mathcal{P}$ be the set of vectors defined by $$\mathcal{P} = \left\{ \left. \begin{pmatrix} a \\ b \end{pmatrix} \right| 0 \leq a \leq 2, 0 \leq b \leq 100, \text{ and } a,b \in \mathbb{Z} \right\}.$$ Find all $\mathbf{v} \in \mathcal{P}$ such that the set $\mathcal{P} \setminus \{ \mathbf{v} \}$ obtained by omitting vector $\mathbf{v}$ from $\mathcal{P}$ can be partitioned into two sets of equal size and equal sum.

Let $n$ be a positive integer, and let $f_n(z) = n + (n-1) z + (n-2)z^2 + \cdots + z^{n-1}$. Prove that $f_n$ has no roots in the closed unit disk $\{z \in \mathbb{C}\colon |z| \leq 1 \}$.

Find all positive integers $n < 10^{100}$ for which simultaneously $n$ divides $2^n$, $n-1$ divides $2^n-1$, and $n-2$ divides $2^n - 2$.

Given a real number $a$, we define a sequence by $x_0 = 1$, $x_1 = x_2 = a$, and $x_{n+1} = 2x_n x_{n-1} - x_{n-2}$ for $n \geq 2$. Prove that if $x_n = 0$ for some $n$, then the sequence is periodic.

Let $f = (f_1, f_2)$ be a function from $\mathbb{R}^2$ to $\mathbb{R}^2$ with continuous partial derivatives $\frac{\partial f_i}{\partial x_j}$ that are positive everywhere. Suppose that $$\frac{\partial f_1}{\partial x_1} \frac{\partial f_2}{\partial x_2} - \frac{1}{4} \left( \frac{\partial f_1}{\partial x_2} + \frac{\partial f_2}{\partial x_1} \right)^2 > 0$$ everywhere. Prove that $f$ is one-to-one.

Let $S$ be the set of sequences of length $2018$ whose terms are in the set $\{1,2,3,4,5,6,10\}$ and sum to $3860$. Prove that the cardinality of $S$ is at most $$2^{3860} \cdot \left( \frac{2018}{2048} \right)^{2018}.$$