Posts Tagged ‘putnam’

Putnam 2017 A3 – Solution

December 4, 2017 Leave a comment

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

December 4, 2017 Leave a comment

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

December 11, 2016 Leave a comment

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…

Read more…

Putnam 2014 Problems

December 8, 2014 Leave a comment

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

Categories: Olympiad Tags: ,

Putnam 2010 A6

February 5, 2011 Leave a comment

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

February 5, 2011 2 comments

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

February 5, 2011 Leave a comment

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:
%d bloggers like this: