[Solutions] William Lowell Putnam Mathematical Competition 2013

1. 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.
2. 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,\dots, 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. For example, $2\cdot 3\cdot 6$ is a perfect square, while $2\cdot 3,2\cdot 4, 2\cdot 5, 2\cdot 3\cdot 4,$ $2\cdot 3\cdot 5, 2\cdot 4\cdot 5,$ and $2\cdot 3\cdot 4\cdot 5$ are not, and so $f(2)=6.$ Show that the function $f$ from $S$ to the integers is one-to-one.
3. 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_1y+\cdots+a_ny^n=0.\]
4. A finite collection of digits $0$ and $1$ is written around a circle. An arc of length $L\ge 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 $|Z(w)-Z(w')|\le 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=\frac1k\sum_{j=1}^kZ(w_j)\text{ and }N=\frac1k\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.$
5. For $m\ge 3,$ a list of $\binom m3$ real numbers $a_{ijk}$ $(1\le i<j<k\le m)$ is said to be area definite for $\mathbb{R}^n$ if the inequality \[\sum_{1\le i<j<k\le m}a_{ijk}\cdot\text{Area}(\triangle A_iA_jA_k)\ge0\] 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 m3$ numbers is area definite for $\mathbb{R}^2,$ then it is area definite for $\mathbb{R}^3.$
6. Define a function $w:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ as follows. For $|a|,|b|\le 2,$ let $w(a,b)$ be as in the table shown; otherwise, let $w(a,b)=0.$ \[\begin{array}{|lr|rrrrr|}\hline &&&&b&&\\ &w(a,b)&-2&-1&0&1&2\\ \hline &-2&-1&-2&2&-2&-1\\ &-1&-2&4&-4&4&-2\\ a&0&2&-4&12&-4&2\\ &1&-2&4&-4&4&-2\\ &2&-1&-2&2&-2&-1\\ \hline\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,0,-1,-1,-2,-2,-4,-4.$
7. 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)^nc(n).$ Find the value of \[\sum_{n=1}^{2013}c(n)c(n+2).\]
8. Let $C=\bigcup_{N=1}^{\infty}C_N,$ where $C_N$ denotes the set of 'cosine polynomials' of the form \[f(x)=1+\sum_{n=1}^Na_n\cos(2\pi nx)\] for which: (i) $f(x)\ge 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.
9. Let $P$ be a nonempty collection of subsets of $\{1,\dots,n\}$ such that: (i) if $S,S'\in P,$ then $S\cup S'\in P$ and $S\cap S'\in P,$ and (ii) if $S\in P$ and $S\ne\emptyset,$ then there is a subset $T\subset S$ such that $T\in P$ and $T$ contains exactly one fewer element than $S.$ Suppose that $f: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 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 P?$
10. For any continuous real-valued function $f$ defined on the interval $[0,1],$ let $$\mu(f)=\int_0^1f(x)dx,$$ $$\text{Var}(f)=\int_0^1(f(x)-\mu(f))^2dx,$$ $$M(f)=\max_{0\le x\le 1}|f(x)|.$$ Show that if $f$ and $g$ are continuous real-valued functions defined on the interval $[0,1],$ then \[\text{Var}(fg)\le 2\text{Var}(f)M(g)^2+2\text{Var}(g)M(f)^2.\]
11. 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\ge 0$ such that $f^{(j)}(x)\le k.$ [Here $f^{(j)}$ denotes the $j$th iterate of $f,$ so that $f^{(0)}(x)=x$ and $f^{(j+1)}(x)=f\left(f^{(j)}(x)\right).$]
12. Let $n\ge 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?

[DOWNLOAD SOLUTIONS ##download##]