Putnam 2013

Recall that a regular icosahedron is a convex polyhedron having 12 vertices and 20 faces; the faces are congruent equilateral triangles. On each face of a regular icosahedron is written a nonnegative integer such that the sum of all 20 integers is 39. Show that there are two faces that share a vertex and have the same integer written on them.

Let $S$ be the set of all positive integers that are not perfect squares. For $n \in S$, consider choices of integers $a_1, a_2, \ldots, a_r$ such that $n < a_1 < a_2 < \cdots < a_r$ and $n \cdot a_1 \cdot a_2 \cdots a_r$ is a perfect square, and let $f(n)$ be the minimum of $a_r$ over all such choices. Show that the function $f$ from $S$ to the integers is one-to-one.

Suppose that the real numbers $a_0, a_1, \dots, a_n$ and $x$, with $0 < x < 1$, satisfy $$\frac{a_0}{1-x} + \frac{a_1}{1-x^2} + \cdots + \frac{a_n}{1 - x^{n+1}} = 0.$$ Prove that there exists a real number $y$ with $0 < y < 1$ such that $$a_0 + a_1 y + \cdots + a_n y^n = 0.$$

A finite collection of digits $0$ and $1$ is written around a circle. An arc of length $L \geq 0$ consists of $L$ consecutive digits around the circle. For each arc $w$, let $Z(w)$ and $N(w)$ denote the number of $0$'s in $w$ and the number of $1$'s in $w$, respectively. Assume that $\left| Z(w) - Z(w') \right| \leq 1$ for any two arcs $w, w'$ of the same length. Suppose that some arcs $w_1,\dots,w_k$ have the property that $$Z = \frac{1}{k} \sum_{j=1}^k Z(w_j) \text{ and } N = \frac{1}{k} \sum_{j=1}^k N(w_j)$$ are both integers. Prove that there exists an arc $w$ with $Z(w) = Z$ and $N(w) = N$.

For $m \geq 3$, a list of $\binom{m}{3}$ real numbers $a_{ijk}$ ($1 \leq i < < j < k \leq m$) is said to be area definite for $\mathbb{R}^n$ if the inequality $$\sum_{1 \leq i < j < k \leq m} a_{ijk} \cdot \mathrm{Area}(\Delta A_i A_j A_k) \geq 0$$ holds for every choice of $m$ points $A_1,\dots,A_m$ in $\mathbb{R}^n$. For example, the list of four numbers $a_{123} = a_{124} = a_{134} = 1$, $a_{234} = -1$ is area definite for $\mathbb{R}^2$. Prove that if a list of $\binom{m}{3}$ numbers is area definite for $\mathbb{R}^2$, then it is area definite for $\mathbb{R}^3$.

Define a function $w : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ as follows. For $|a|, |b| \leq 2$, let $w(a, b)$ be as in the table shown; otherwise, let $w(a, b) = 0$.

$$\begin{array}{c|ccccc} w(a,b) & b=-2 & b=-1 & b=0 & b=1 & b=2 \\ \hline a=-2 & -1 & -2 & 2 & -2 & -1 \\ a=-1 & -2 & 4 & -4 & 4 & -2 \\ a=0 & 2 & -4 & 12 & -4 & 2 \\ a=1 & -2 & 4 & -4 & 4 & -2 \\ a=2 & -1 & -2 & 2 & -2 & -1 \\ \end{array}$$

For every finite subset $S$ of $\mathbb{Z} \times \mathbb{Z}$, define $$A(S) = \sum_{(\mathbf{s}, \mathbf{s}') \in S \times S} w(\mathbf{s} - \mathbf{s}').$$ Prove that if $S$ is any finite nonempty subset of $\mathbb{Z} \times \mathbb{Z}$, then $A(S) > 0$. (For example, if $S = \{(0,1), (0,2), (2,0), (3,1)\}$, then the terms in $A(S)$ are 12, 12, 12, 12, 4, 4, 0, 0, 0, -1, -1, -2, -2, -4, -4.)

For positive integers $n$, let the numbers $c(n)$ be determined by the rules $c(1) = 1$, $c(2n) = c(n)$, and $c(2n+1) = (-1)^n c(n)$. Find the value of $$\sum_{n=1}^{2013} c(n) c(n+2).$$

Let $C = \bigcup_{N=1}^\infty C_N$, where $C_N$ denotes the set of those `cosine polynomials' of the form $$f(x) = 1 + \sum_{n=1}^N a_n \cos(2 \pi n x)$$ for which:

(i) $f(x) \geq 0$ for all real $x$, and

(ii) $a_n = 0$ whenever $n$ is a multiple of $3$.

Determine the maximum value of $f(0)$ as $f$ ranges through $C$, and prove that this maximum is attained.

Let $\mathcal{P}$ be a nonempty collection of subsets of $\{1,\dots, n\}$ such that:

(i) if $S, S' \in \mathcal{P}$, then $S \cup S' \in \mathcal{P}$ and $S \cap S' \in \mathcal{P}$, and

(ii) if $S \in \mathcal{P}$ and $S \neq \emptyset$, then there is a subset $T \subset S$ such that $T \in \mathcal{P}$ and $T$ contains exactly one fewer element than $S$.

Suppose that $f: \mathcal{P} \to \mathbb{R}$ is a function such that $f(\emptyset) = 0$ and $$f(S \cup S') = f(S) + f(S') - f(S \cap S') \text{ for all $S,S' \in \mathcal{P}$.}$$ Must there exist real numbers $f_1,\dots,f_n$ such that $$f(S) = \sum_{i \in S} f_i$$ for every $S \in \mathcal{P}$?

For any continuous real-valued function $f$ defined on the interval $[0,1]$, let $$\mu(f) = \int_0^1 f(x) dx,\ \text{Var}(f) = \int_0^1 (f(x) - \mu(f))^2 dx,\ \ M(f) = \max_{0 \leq x \leq 1} |f(x)|.$$ Show that if $f$ and $g$ are continuous real-valued functions defined on the interval $[0,1]$, then $$\text{Var}(fg) \leq 2\text{Var}(f)M(g)^2 + 2\text{Var}(g)M(f)^2.$$

Let $X = \{1, 2, \dots, n\}$, and let $k \in X$. Show that there are exactly $k \cdot n^{n-1}$ functions $f: X \to X$ such that for every $x \in X$ there is a $j \geq 0$ such that $f^{(j)}(x) \leq k$. [Here $f^{(j)}$ denotes the $j$th iterate of $f$, so that $f^{(0)}(x) = x$ and $f^{(j+1)}(x) = f(f^{(j)}(x))$.]

Let $n \geq 1$ be an odd integer. Alice and Bob play the following game, taking alternating turns, with Alice playing first. The playing area consists of $n$ spaces, arranged in a line. Initially all spaces are empty. At each turn, a player either

• places a stone in an empty space, or

• removes a stone from a nonempty space $s$, places a stone in the nearest empty space to the left of $s$ (if such a space exists), and places a stone in the nearest empty space to the right of $s$ (if such a space exists).

Furthermore, a move is permitted only if the resulting position has not occurred previously in the game. A player loses if he or she is unable to move. Assuming that both players play optimally throughout the game, what moves may Alice make on her first turn?