### Archive

Archive for the ‘Uncategorized’ Category

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

## Putnam 2017 – Problem A1

Problem A1. We have ${n^2 \in S \Rightarrow N \in S}$ and ${n \in S \Rightarrow (n+5)^2 \in S}$. Therefore ${n \in S \Rightarrow n+5 \in S}$.

Next, let’s note what elements cannot be in ${S}$. Note that taking square roots and squaring ${n+5}$ cannot change a non-zero remainder modulo ${5}$ into a zero remainder. Therefore, starting from ${2}$ one could never get a multiple of ${5}$ following the allowed operations. Thus we can safely say that multiples of ${5}$ are not in the minimal set ${S}$.

Furthermore, ${1}$ could only be obtained as a square root of itself with the allowed operations. Starting from ${2}$, one could never get below by performing square roots or ${n \mapsto (n+5)^2}$. Therefore, the minimal set ${S}$ does not contain ${1}$ and multiples of ${5}$.

Now, we show that it contains all the rest. The general idea is as follows: it is enough to find which is the smallest element in a class of remainders modulo ${5}$ to deduce that all larger elements are there (recall the operation ${n \in S \Rightarrow n+5\in S}$). Now in order to obtain small elements of ${S}$, one would need to take successive square roots. So if we prove that for some ${a}$ we have ${a^{2^n}\in S}$ for some ${n}$ then we get that ${a \in S}$.

Now let’s start from the beginning. We have ${2 \in S}$ so ${49 = (2+5)^2 \in S}$. Since ${49+5k}$ is in ${S}$ for every ${k}$, we get that all squares of the form ${5k+4}$ greater than ${49}$ are in ${S}$. Moreover, ${(49+5)^2 = 2916}$ so all numbers of the form ${5k+1}$ greater than ${2916}$ are in ${S}$. Since ${81^2 =6561}$ it follows that ${6561 \in S \Rightarrow 81 \in S \Rightarrow 9 \in S \Rightarrow 3 \in S}$. Moreover, ${6^{16}}$ ends in ${6}$ and is greater than ${2916}$ so ${6 \in S}$. Next, we have ${4^8 = 16^4}$ which ends in ${6}$ and is greater than ${2916}$ so it is also in ${S}$. Therefore ${4 \in S}$.

Finally, we have that ${n \in S \Rightarrow n+5 \in S}$, ${\{2,3,4,6\} \subset S}$ and ${1 \notin S}$, ${5k \notin S}$. This means that the minimal set ${S}$ is ${\Bbb{Z}_+^* \setminus\{1\} \setminus \{5k: k \in \Bbb{Z}_+\}}$.

Categories: Uncategorized

## Putnam 2017 – Problems

Source: Art of Problem Solving forum

Problem A1. Let ${S}$ be the smallest set of positive integers such that

• a) ${2}$ is in ${S,}$
• b) ${n}$ is in ${S}$ whenever ${n^2}$ is in ${S,}$ and
• c) ${(n+5)^2}$ is in ${S}$ whenever ${n}$ is in ${S.}$

Which positive integers are not in ${S?}$

(The set ${S}$ is “smallest” in the sense that ${S}$ is contained in any other such set.)

Problem A2. Let ${Q_0(x)=1}$, ${Q_1(x)=x,}$ and

$\displaystyle Q_n(x)=\frac{(Q_{n-1}(x))^2-1}{Q_{n-2}(x)}$

for all ${n\ge 2.}$ Show that, whenever ${n}$ is a positive integer, ${Q_n(x)}$ is equal to a polynomial with integer coefficients.

Problem A3. Let ${a}$ and ${b}$ be real numbers with ${a and let ${f}$ and ${g}$ be continuous functions from ${[a,b]}$ to ${(0,\infty)}$ such that ${\int_a^b f(x)\,dx=\int_a^b g(x)\,dx}$ but ${f\ne g.}$ For every positive integer ${n,}$ define

$\displaystyle I_n=\int_a^b\frac{(f(x))^{n+1}}{(g(x))^n}\,dx.$

Show that ${I_1,I_2,I_3,\dots}$ is an increasing sequence with ${\displaystyle\lim_{n\rightarrow\infty}I_n=\infty.}$

Problem A4. A class with ${2N}$ students took a quiz, on which the possible scores were ${0,1,\dots,10.}$ Each of these scores occurred at least once, and the average score was exactly ${7.4.}$ Show that the class can be divided into two groups of ${N}$ students in such a way that the average score for each group was exactly ${7.4.}$

Problem A5. Each of the integers from ${1}$ to ${n}$ is written on a separate card, and then the cards are combined into a deck and shuffled. Three players, ${A,B,}$ and ${C,}$ take turns in the order ${A,B,C,A,\dots}$ choosing one card at random from the deck. (Each card in the deck is equally likely to be chosen.) After a card is chosen, that card and all higher-numbered cards are removed from the deck, and the remaining cards are reshuffled before the next turn. Play continues until one of the three players wins the game by drawing the card numbered ${1.}$

Show that for each of the three players, there are arbitrarily large values of ${n}$ for which that player has the highest probability among the three players of winning the game.

Problem A6. The ${30}$ edges of a regular icosahedron are distinguished by labeling them ${1,2,\dots,30.}$ How many different ways are there to paint each edge red, white, or blue such that each of the 20 triangular faces of the icosahedron has two edges of the same color and a third edge of a different color?

Problem B1. Let ${L_1}$ and ${L_2}$ be distinct lines in the plane. Prove that ${L_1}$ and ${L_2}$ intersect if and only if, for every real number ${\lambda\ne 0}$ and every point ${P}$ not on ${L_1}$ or ${L_2,}$ there exist points ${A_1}$ on ${L_1}$ and ${A_2}$ on ${L_2}$ such that ${\overrightarrow{PA_2}=\lambda\overrightarrow{PA_1}.}$

Problem B2. Suppose that a positive integer ${N}$ can be expressed as the sum of ${k}$ consecutive positive integers

$\displaystyle N=a+(a+1)+(a+2)+\cdots+(a+k-1)$

for ${k=2017}$ but for no other values of ${k>1.}$ Considering all positive integers ${N}$ with this property, what is the smallest positive integer ${a}$ that occurs in any of these expressions?

Problem B3. Suppose that

$\displaystyle f(x) = \sum_{i=0}^\infty c_ix^i$

is a power series for which each coefficient ${c_i}$ is ${0}$ or ${1}$. Show that if ${f(2/3) = 3/2}$, then ${f(1/2)}$ must be irrational.

Problem B4. Evaluate the sum

$\displaystyle \sum_{k=0}^{\infty}\left(3\cdot\frac{\ln(4k+2)}{4k+2}-\frac{\ln(4k+3)}{4k+3}-\frac{\ln(4k+4)}{4k+4}-\frac{\ln(4k+5)}{4k+5}\right)$

$\displaystyle =3\cdot\frac{\ln 2}2-\frac{\ln 3}3-\frac{\ln 4}4-\frac{\ln 5}5+3\cdot\frac{\ln 6}6-\frac{\ln 7}7-\frac{\ln 8}8-\frac{\ln 9}9+3\cdot\frac{\ln 10}{10}-\cdots.$

(As usual, ${\ln x}$ denotes the natural logarithm of ${x.}$)

Problem B5. A line in the plane of a triangle ${T}$ is called an equalizer if it divides ${T}$ into two regions having equal area and equal perimeter. Find positive integers ${a>b>c,}$ with ${a}$ as small as possible, such that there exists a triangle with side lengths ${a,b,c}$ that has exactly two distinct equalizers.

Problem B6. Find the number of ordered ${64}$-tuples ${\{x_0,x_1,\dots,x_{63}\}}$ such that ${x_0,x_1,\dots,x_{63}}$ are distinct elements of ${\{1,2,\dots,2017\}}$ and

$\displaystyle x_0+x_1+2x_2+3x_3+\cdots+63x_{63}$

is divisible by ${2017.}$

Categories: Uncategorized

## A hint for Project Euler Pb 613

The text for Problem 613 can be found here. The hint is the following picture 🙂

## IMC 2017 – Day 2 – Solutions

See the previous post for the statements of the problems.

Problem 6. We have that

$\displaystyle \int_0^1 f(nx) dx = \frac{1}{n} \int_0^n f(x)dx$

Suppose ${f(x) \geq L}$ for ${x > M}$. Then for ${n \gg M}$ we have

$\displaystyle \frac{1}{n} \int_0^n f(x) = \frac{1}{n} \int_0^M f(x) dx + \frac{1}{n}\int_M^n f(x) dx \geq \frac{1}{n} \int_0^M f(x)dx + \frac{n-M}{n}L.$

This shows that ${\displaystyle \liminf\limits_{n \rightarrow \infty} \frac{1}{n} \int_0^n f(x) dx \geq L}$. In the same way, having ${f(x) \leq L}$ for ${x>M}$ leads to ${\displaystyle \limsup_{n \rightarrow \infty} \frac{1}{n} \int_0^n f(x)dx \leq L}$.

Now all we need to do is to apply the above procedure to inequalities of the form ${f(x) \leq L+\delta}$ for ${x>M}$ and ${f(x) \geq L-\delta}$ for ${x>M}$, which come from the definition of the limit when ${x \rightarrow \infty}$. The case ${L}$ infinite is similar.

Problem 7. If all roots of ${q_n}$ are real then the sum of their square is non-negative. Suppose ${p}$ is a polynomial of degree ${d>0}$. If we denote ${w_1,...,w_{n+d}}$ are the roots of ${q_n}$ then

$\displaystyle 0 \leq \sum w_i^2 = \left(\sum w_i\right)^2-2\sum_{i

If ${q_n(x) = ax^{n+d}+bx^{n+d-1}+cx^{n+d-2}+...}$ then the previous inequality translates to

$\displaystyle 0 \leq \sum w_i^2 = \left( \frac{b}{a}\right)^2 - 2 \frac{c}{a},$

which is equivalent to ${b^2 - 2ac \geq 0}$. Now if we compute the coefficients ${a,b,c}$ for ${q_n}$ we find something which for ${n \rightarrow \infty}$ contradicts the previous inequality.

Problem 8. We start by observing that the eigenvalues of ${A_1}$ are ${1}$ and ${-1}$. Next, using the properties of block matrix determinants, we have the following equalities

$\displaystyle \det(A_{n+1}-\lambda I) = \det\begin{pmatrix} A_n-\lambda I & I \\ I & A_n-\lambda I \end{pmatrix} = \det((A_n-\lambda I)^2-I)$

$\displaystyle = \det(A_n-(\lambda+1)I)\det(A_n-(\lambda-1)I)$

The block determinant formula holds if ${(A_n-\lambda I)}$ is invertible. This happens for all but finitely many values of ${\lambda}$ (the eigenvalues of ${A_n)}$). Moreover, since the above equalities are polynomial equalities, this implies equality for every ${\lambda}$. Therefore, for each eigenvalue ${\lambda}$ of ${A_n}$ (multiplicity accounted) we have ${\lambda+1}$ and ${\lambda-1}$ as eigenvalues for ${A_{n+1}}$.

Therefore the eigenvalues of ${A_n}$ are

• ${A_2: \ \{-2,0,0,2\}}$
• ${A_3: \ \{-3,-1,-1,-1,1,1,1,3 \}}$
• ${A_4: \ \{-4,-2,-2,-2,-2,0,0,0,0,0,0,2,2,2,2,4\}}$

Note that a phenomenon similar to the Pascal triangle appears, which makes that adjacent eigenvalues of ${A_n}$ (which have a difference equal to ${2}$) with multiplicities ${{n\choose k}}$ and ${{n\choose k+1}}$ generate an eigenvalue of ${A_{n+1}}$ with multiplicity ${{n\choose k}+{n\choose k+1}={n+1 \choose k+1}}$

Problem 9. Elementary techniques in ODE show that ${\displaystyle f_{n+1}(x) = \exp(\int_0^x f_n(t)dt)}$. We note that ${f_1 = 1}$ and ${f_2(x) = e^x}$. Therefore ${f_1\leq f_2}$ on ${[0,1]}$. This implies, using a recurrence argument, that ${f_n(x) \leq f_{n+1}(x)}$. This shows that ${\lim_{n \rightarrow \infty} f_n(x)}$ exists for ${x\in [0,1]}$, but, for now, might be infinite.

In order to find an upper bound we may look what is the equation satisfied by an eventual limit ${F}$ of ${f_n}$ as ${n \rightarrow \infty}$. We arrive at the ODE ${F' = F^2,\ F(0)=1}$. It is immediate to see that ${F(x) = \frac{1}{1-x}}$. Now we would like to prove that ${f_n \leq F}$ on ${[0,1)}$, and for this we define ${g_n = f_n-F}$. Using ${f_n \leq f_{n+1}}$ and the hypothesis we get ${f_{n+1}' \leq f_{n+1}^2}$. Using this we have

$\displaystyle g_n' = f_n'-F' \leq f_n^2 - F^2=g_n(f_n+F)$

and ${g_n(0)=0}$. This implies that

$\displaystyle \left( g_n \exp(-\int_0^x (f_n+F)) \right)'\leq 0$

This implies easily that ${g_n \leq 0}$ on ${[0,1)}$, which means that ${f_n \leq F}$ on ${[0,1)}$. Thus the pointwise limit of ${f_n}$ exists. Let’s denote it by ${G}$. Since ${f_n \leq f_{n+1}}$ using the monotone convergence theorem we have the convergence of integrals ${\int_0^x f_n(t)dt = \int_0^x G(t)dt}$. Thus the limit satisfies

$\displaystyle G(x) = \exp\left(\int_0^x G(t)dt\right).$

Therefore ${G}$ satisfies ${G'=G^2}$ and ${G(0)=1}$ which means that the limit is indeed ${G(x) = 1/(1-x)}$ for ${x \in [0,1)}$.

Categories: Uncategorized

## IMC 2017 – Day 2 – Problems

Problem 6. Let ${f: [0,\infty) \rightarrow \Bbb{R}}$ be a continuous function such that ${\lim_{x \rightarrow \infty}f(x) = L}$ exists (finite or infinite).

Prove that

$\displaystyle \lim_{n \rightarrow \infty} \int_0^1 f(nx) dx = L.$

Problem 7. Let ${p(x)}$ be a nonconstant polynomial with real coefficients. For every positive integer ${n}$ let

$\displaystyle q_n(x) = (x+1)^n p(x)+x^n p(x+1).$

Prove that there are only finitely many numbers ${n}$ such that all roots of ${q_n(x)}$ are real.

Problem 8. Define the sequence ${A_1,A_2,...}$ of matrices by the following recurrence

$\displaystyle A_1 = \begin{pmatrix} 0& 1 \\ 1& 0 \end{pmatrix}, \ A_{n+1} = \begin{pmatrix} A_n & I_{2^n} \\ I_{2^n} & A_n \end{pmatrix} \ \ (n=1,2,...)$

where ${I_m}$ is the ${m\times m}$ identity matrix.

Prove that ${A_n}$ has ${n+1}$ distinct integer eigenvalues ${\lambda_0<\lambda_1<...<\lambda_n}$ with multiplicities ${{n \choose 0},\ {n\choose 1},...,{n \choose n}}$, respectively.

Problem 9. Define the sequence ${f_1,f_2,... : [0,1) \rightarrow \Bbb{R}}$ of continuously differentiable functions by the following recurrence

$\displaystyle f_1 = 1; f'_{n+1} = f_nf_{n+1} \text{ on } (0,1) \text{ and } f_{n+1}(0)=1.$

Show that ${\lim_{n\rightarrow \infty}f_n(x)}$ exists for every ${x \in [0,1)}$ and determine the limit function.

Problem 10. Let ${K}$ be an equilateral triangle in the plane. Prove that for every ${p>0}$ there exists an ${\varepsilon >0}$ with the following property: If ${n}$ is a positive integer and ${T_1,...,T_n}$ are non-overlapping triangles inside ${K}$ such that each of them is homothetic to ${K}$ with a negative ratio and

$\displaystyle \sum_{\ell =1}^n \text{area}(T_\ell) > \text{area} (K)-\varepsilon,$

then

$\displaystyle \sum_{\ell =1}^n \text{perimeter} (T_\ell) > p.$

## IMC 2017 – Day 1

Problem 1. Determine all complex numbers ${\lambda}$ for which there exists a positive integer ${n}$ and a real ${n\times n}$ matrix ${A}$ such that ${A^2 = A^T}$ and ${\lambda}$ is an eigenvalue of ${A}$.

Problem 2. Let ${f: \Bbb{R} \rightarrow (0,\infty)}$ be a differentiable function and suppose that there exists a constant ${L>0}$ such that

$\displaystyle |f'(x)-f'(y)|\leq L|x-y|$

for all ${x,y}$. Prove that

$\displaystyle (f'(x))^2 < 2Lf(x)$

holds for all ${x}$.

Problem 3. For any positive integer ${m}$ denote by ${P(m)}$ the product of positive divisors of ${m}$. For every positive integer ${n}$ define the sequence

$\displaystyle a_1(n)=n, \ \ \ a_{k+1}(n) = P(a_k(n)) \ \ (k=1,2,...,2016).$

Determine whether for every set ${S \subseteq \{1,2,...,2017\}}$ there exists a positive integer ${n}$ such that the following condition is satisfied:

For every ${k}$ with ${1\leq k \leq 2017}$ the number ${a_k(n)}$ is a perfect square if and only if ${k \in S}$.

Problem 4. There are ${n}$ people in a city and each of them has exactly ${1000}$ friends (friendship is mutual). Prove that it is possible to select a group ${S}$ of people such that at least ${n/2017}$ persons in ${S}$ have exactly two friends in ${S}$.

Problem 5. Let ${k}$ and ${n}$ be positive integers with ${n \geq k^2-3k+4}$ and let

$\displaystyle f(z) = z^{n-1}+c_{n-2}z^{n-2}+...+c_0$

be a polynomial with complex coefficients such that

$\displaystyle c_0c_{n-2} = c_1c_{n-3} = ... = c_{n-2}c_0 = 0.$

Prove that ${f(z)}$ and ${z^n-1}$ have at most ${n-k}$ common roots.

Categories: Uncategorized