### Archive

Posts Tagged ‘putnam’

## Putnam 2017 A3 – Solution

Problem A3. Denote ${\phi = f-g}$. Then ${\phi}$ is continuous and ${\int_a^b \phi = 0}$. We can see that

$\displaystyle I_{n+1}-I_n = \int_a^b (f/g)^n \phi = \int_{\phi\geq 0} (f/g)^n \phi+ \int_{\phi<0} (f/g)^n \phi$

Now note that on ${\{ \phi>=0\}}$ we have ${f/g \geq 1}$ so ${(f/g)^n \phi \geq \phi}$. Furthermore, on ${\{\phi<0\}}$ we have ${(f/g)^n <1}$ so multiplying with ${\phi<0}$ we get ${(f/g)^n \phi \geq \phi}$. Therefore

$\displaystyle I_{n+1}-I_n \geq \int_{\phi \geq 0} \phi + \int_{\phi<0} \phi = \int \phi = 0.$

To prove that ${I_n}$ goes to ${+\infty}$ we can still work with ${I_{n+1}-I_n}$. Note that the negative part cannot get too big:

$\displaystyle \left|\int_{ \phi <0 } (f/g)^n \phi \right| \leq \int_{\phi<0} |\phi| \leq \int_a^b |f-g|.$

As for the positive part, taking ${0<\varepsilon< \max_{[a,b]} \phi}$ we have

$\displaystyle \int_{\phi\geq 0} (f/g)^n \phi \geq \int_{\phi>\varepsilon}(f/g)^n \varepsilon.$

Next, note that on ${\{ \phi \geq \varepsilon\}}$

$\displaystyle \frac{f}{g} = \frac{g+\phi}{g} \geq \frac{g+ \varepsilon}{g}.$

We would need that the last term be larger than ${1+\delta}$. This is equivalent to ${g\delta <\varepsilon}$. Since ${g}$ is continuous on ${[a,b]}$, it is bounded above, so some delta small enough exists in order for this to work.

Grouping all of the above we get that

$\displaystyle I_{n+1}-I_n \geq \int_{\phi \geq 0} (f/g)^n \phi \geq \int_{\phi>\varepsilon} \varepsilon (1+\delta)^n.$

Since ${|\phi>\varepsilon|>0}$ we get that ${I_{n+1}-I_n}$ goes to ${+\infty}$.

## Putnam 2017 A2 – Solution

Problem A2. We have the following recurrence relation

$\displaystyle Q_n = \frac{Q_{n-1}^2-1}{Q_{n-2}},$

for ${n \geq 2}$, given ${Q_0=1}$ and ${Q_1=x}$. In order to prove that ${Q_n}$ is always a polynomial with integer coefficients we should prove that ${Q_{n-2}}$ divides ${Q_{n-1}^2-1}$ somehow. Recurrence does not seem to work very well. Also, root based arguments might work, but you need to take good care in the computation.

A simpler idea, which is classic in this context, is to try and linearize the recurrence relation. In order to do this, let’s write two consecutive recurrence relations

$\displaystyle Q_nQ_{n-2} +1 = Q_{n-1}^2$

$\displaystyle Q_n^2 = Q_{n+1}Q_{n-1}+1$

We add them and we obtain the following relation

$\displaystyle \frac{Q_n}{Q_{n-1}} = \frac{Q_{n+1}+Q_{n-1}}{Q_n+Q_{n-2}},$

which leads straightforward to a telescoping argument. Finally, we are left with a simple linear recurrence with integer coefficient polynomials, and the result follows immediately.

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