### Archive

Posts Tagged ‘putnam’

## Some of the easy Putnam 2016 Problems

Here are a few of the problems of the Putnam 2016 contest. I choose to only list problems which I managed to solve. Most of them are pretty straightforward, so maybe the solutions posted here may be very similar to the official ones. You can find a complete list of the problems on other sites, for example here.

A1. Find the smallest integer ${j}$ such that for every polynomial ${p}$ with integer coefficients and every integer ${k}$, the number

$\displaystyle p^{(j)}(k),$

that is the ${j}$-th derivative of ${p}$ evaluated at ${k}$, is divisible by ${2016}$.

Hints. Successive derivatives give rise to terms containing products of consecutive numbers. The product of ${j}$ consecutive numbers is divisible by ${j!}$. Find the smallest number such that ${2016 | j!}$. Prove that ${j-1}$ does not work by choosing ${p = x^{j-1}}$. Prove that ${j}$ works by working only on monomials…

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

## Putnam 2010 A6

Let $f : [0,\infty) \to \Bbb{R}$ be a strictly decreasing continuous function such that $\displaystyle \lim_{x \to \infty}f(x)=0$. Prove that $\displaystyle \int_0^\infty \frac{f(x)-f(x+1)}{f(x)}dx$ diverges.

Putnam 2010 A6

Categories: Analysis Tags:

## Putnam 2010 A5

Let $G$ be a group, with operation $\star$. Suppose that:

1. $G$ is a subset of $\Bbb{R}^3$;
2. For each $a,b \in G$ either $a \times b=a\star b$ or $a\times b=0$ (or both), where $\times$ is the usual cross product.

Prove that $a\times b=0$ for all $a,b \in G$.

Putnam A5

## Putnam 2010 A4

Prove that for each positive integer $n$ the number $10^{10^{10^n}}+10^{10^n}+10^n-1$ is not prime.

Putnam 2010 A4

Categories: Number theory Tags:

## Putnam 2010 A3

Suppose that the function $h \to \Bbb{R}^2 \to \Bbb{R}$ has continuous partial derivatives and satisfies the equation $\displaystyle h(x,y)=a \frac{\partial h}{\partial x}(x,y)+b\frac{\partial h}{\partial y}(x,y)$ for some constants $a,b$. Prove that if there is a constant $M$ such that $|h(x,y) | \leq M$ for all $(x,y) \in \Bbb{R}^2$, then $h$ is identically zero.

Putnam 2010 A3

Categories: Analysis Tags:

## Putnam 2010 A2

Find all differentiable functions $f: \Bbb{R} \to \Bbb{R}$ such that $\displaystyle f^\prime(x)=\frac{f(x+n)-f(x)}{n}$ for all $x \in \Bbb{R},\ \forall n \in \Bbb{Z}_+^*$.

Putnam 2010 A2