Home > Olympiad > Putnam 2014 Problems

## Putnam 2014 Problems

A1. 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.

A2. Let ${A}$ be the ${n\times n}$ matrix whose entry in the ${i}$-th row and ${j}$-th column is

$\displaystyle \frac1{\min(i,j)}$

for ${1\le i,j\le n.}$ Compute ${\det(A).}$

A3. Let ${a_0=5/2}$ and ${a_k=a_{k-1}^2-2}$ for ${k\ge 1.}$ Compute

$\displaystyle \prod_{k=0}^{\infty}\left(1-\frac1{a_k}\right)$

in closed form.

A4. 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.}$

A5. Let ${P_n(x)=1+2x+3x^2+\cdots+nx^{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\ne k.}$

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_iN_j}$ has a zero entry somewhere on its diagonal if and only if ${i\ne j?}$

B1. A base ${1}$ over-expansion of a positive integer ${N}$ is an expression of the form ${N=d_k10^k+d_{k-1}10^{k-1}+\cdots+d_0 10^0}$ with ${d_k\ne 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?

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

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.}$

B4. Show that for each positive integer ${n,}$ all the roots of the polynomial

$\displaystyle \sum_{k=0}^n 2^{k(n-k)}x^k$

are real numbers.

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:

(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?

B6. Let ${f:[0,1]\rightarrow\mathbb{R}}$ be a function for which there exists a constant ${K>0}$ such that ${|f(x)-f(y)|\le K|x-y|}$ 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}^nI_i.}$