\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{hhline}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{anyfontsize}
\usepackage[super]{nth}
\usepackage{ulem}
\usepackage{multicol}
\usepackage{phaistos}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}
\usepackage{makecell}
\newcolumntype{x}[1]{>{\centering\arraybackslash}p{#1}}
\usepackage{tikz}

\input{preamble.tex}



\begin{document}

\homework{18: The 2014 Putnam Exam}{Due by Thursday at 2pm, finals week.}


Solve up to \textbf{three} of the following \textbf{twelve} problems.  This is the 2014 Putnam exam, and is extra-credit!  The problems are broken into two sets $A$ and $B$, corresponding to the morning and afternoon sessions of the Putnam.  Problems with lower numbers are usually easier or require less background to solve.  This set can be submitted by email if you can't turn it in to my office.  Have fun!

\begin{enumerate}
\item[A1.] 
Prove that every nonzero coefficient of the Taylor series of
\begin{align*}
(1 - x + x^2)e^x
\end{align*}
about $x=0$ is a rational number whose numerator (in lowest terms) is either $1$ or a prime number.

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

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

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

\item[A5.]
Let
\begin{align*}
P_n(x) = 1 + 2 x  + 3 x^2 + \cdots + n x^{n-1}.
\end{align*}
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$.

\item[A6.]
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$?

\item[B1.]
A \emph{base $10$ over-expansion} of a positive integer $N$ is an expression of the form
\begin{align*}
N = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_0 10^0
\end{align*}
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?

\item[B2.]
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?

\,

\item[B3.]
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.

\item[B4.]
Show that for each positive integer $n$, all the roots of the polynomial
\begin{align*}
\sum_{k=0}^n 2^{k(n-k)} x^k
\end{align*}
are real numbers.

\item[B5.]
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:
\begin{enumerate}
\item A player cannot choose an element that has been chosen by either player on any previous turn.
\item A player can only choose an element that commutes with all previously chosen elements.
\item A player who cannot choose an element on his/her turn loses the game.
\end{enumerate}
Patniss takes the first turn. Which player has a winning strategy? (Your answer may depend on $n$ and $p$.)

\item[B6.]
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$. 
\end{enumerate}





\end{document}








