Putnam 2014

Prove that every nonzero coefficient of the Taylor series of $$(1 - x + x^2)e^x$$ about $x=0$ is a rational number whose numerator (in lowest terms) is either $1$ or a prime number.

Let $A$ be the $n \times n$ matrix whose entry in the $i$-th row and $j$-th column is $$\frac{1}{\min(i,j)}$$ for $1 \leq i,j \leq n$. Compute $\det(A)$.

Let $a_0 = 5/2$ and $a_k = a_{k-1}^2 - 2$ for $k \geq 1$. Compute $$\prod_{k=0}^\infty \left(1 - \frac{1}{a_k} \right)$$ in closed form.

Suppose $X$ is a random variable that takes on only nonnegative integer values, with $E[X] = 1$, $E[X^2] = 2$, and $E[X^3] = 5$. (Here $E[Y]$ denotes the expectation of the random variable $Y$.) Determine the smallest possible value of the probability of the event $X = 0$.

Let $$P_n(x) = 1 + 2 x + 3 x^2 + \cdots + n x^{n-1}.$$ Prove that the polynomials $P_j(x)$ and $P_k(x)$ are relatively prime for all positive integers $j$ and $k$ with $j \neq k$.

Let $n$ be a positive integer. What is the largest $k$ for which there exist $n \times n$ matrices $M_1, \dots, M_k$ and $N_1, \dots, N_k$ with real entries such that for all $i$ and $j$, the matrix product $M_i N_j$ has a zero entry somewhere on its diagonal if and only if $i \neq j$?

A base $10$ over-expansion of a positive integer $N$ is an expression of the form $$N = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_0 10^0$$ with $d_k \neq 0$ and $d_i \in \{0,1,2,\dots,10\}$ for all $i$. For instance, the integer $N = 10$ has two base 10 over-expansions: $10 = 10 \cdot 10^0$ and the usual base 10 expansion $10 = 1 \cdot 10^1 + 0 \cdot 10^0$. Which positive integers have a unique base 10 over-expansion?

Suppose that $f$ is a function on the interval $[1,3]$ such that $-1 \leq f(x) \leq 1$ for all $x$ and $\int_1^3 f(x) dx = 0$. How large can $\int_1^3 \frac{f(x)}{x} dx$ be?

Let $A$ be an $m \times n$ matrix with rational entries. Suppose that there are at least $m+n$ distinct prime numbers among the absolute values of the entries of $A$. Show that the rank of $A$ is at least 2.

Show that for each positive integer $n$, all the roots of the polynomial $$\sum_{k=0}^n 2^{k(n-k)} x^k$$ are real numbers.

In the 75th annual Putnam Games, participants compete at mathematical games. Patniss and Keeta play a game in which they take turns choosing an element from the group of invertible $n \times n$ matrices with entries in the field $\mathbb{Z}/p \mathbb{Z}$ of integers modulo $p$, where $n$ is a fixed positive integer and $p$ is a fixed prime number. The rules of the game are:

(1) A player cannot choose an element that has been chosen by either player on any previous turn.

(2) A player can only choose an element that commutes with all previously chosen elements.

(3) A player who cannot choose an element on his/her turn loses the game.

Patniss takes the first turn. Which player has a winning strategy? (Your answer may depend on $n$ and $p$.)

Let $f: [0,1] \to \mathbb{R}$ be a function for which there exists a constant $K>0$ such that $\left| f(x) - f(y) \right| \leq K \left| x - y \right|$ for all $x,y \in [0,1]$. Suppose also that for each rational number $r \in [0,1]$, there exist integers $a$ and $b$ such that $f(r) = a + br$. Prove that there exist finitely many intervals $I_1, \dots, I_n$ such that $f$ is a linear function on each $I_i$ and $[0,1] = \bigcup_{i=1}^n I_i$.