### Archive

Archive for the ‘Problem Solving’ Category

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

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

## Project Euler – Problem 264

Today I managed to solve problem 264 from Project Euler. This is my highest rating problem until now: 85%. You can click the link for the full text of the problem. The main idea is to find all triangles ABC with vertices having integer coordinates such that

• the circumcenter O of each of the triangles is the origin
• the orthocenter H (the intersection of the heights) is the point of coordinates (0,5)
• the perimeter is lower than a certain bound

I will not give detailed advice or codes. You can already find a program online for this problem (I won’t tell you where) and it can serve to verify the final code, before going for the final result. Anyway, following the hints below may help you get to a solution.

The initial idea has to do with a geometric relation linking the points A, B, C, O and H. Anyone who did some problems with vectors and triangles should have come across the needed relation at some time. If not, just search for important lines in triangles, especially the line passing through O and H (and another important point).

Once you find this vectorial relation, it is possible to translate it in coordinates. The fact that points A, B, C are on a circle centered in O shows that their coordinates satisfy an equation of the form $x^2+y^2=n$, where $n$ is a positive integer, not necessarily a square… It is possible to enumerate all solutions to the following equation for fixed $n$, simply by looping over $x$ and $y$. This helps you find all lattice points on the circle of radius $\sqrt{n}$.

Once these lattice points are found one needs to check the orthocenter condition. The relations are pretty simple and in the end we have two conditions to check for the sum of the x and y coordinates. The testing procedure is a triple loop. We initially have a list of points on a circle, from the previous step. We loop over them such that we dont count triangles twice: i from 1 to m, j from i+1 to m, k from j+1 to m, etc. Once a suitable solution is found, we compute the perimeter using the classical distance formula between two points given in coordinates. Once the perimeter is computed we add it to the total.

Since the triple loop has cubic complexity, one could turn it in a double loop. Loop over pairs and construct the third point using the orthocenter condition. Then just check if the point is also on the circle. I didn’t manage to make this double loop without overcounting things, so I use it as a test: use double loops to check every family of points on a given circle. If you find something then use a triple loop to count it properly. It turns out that cases where the triple loop is needed are quite rare.

So now you have the ingredients to check if on a circle of given radius there are triangles with the desired properties. Now we just iterate over the square of the radius. The problem is to find the proper upper bound for this radius in order to get all the triangles with perimeter below the bound. It turns out that a simple observation can get you close to a near optimal bound. Since in the end the radii get really large and the size of the triangles gets really large, the segment OH becomes small, being of fixed length 5. When OH is very small, the triangle is almost equilateral. Just use the upper bound for the radius for an equilateral triangle of perimeter equal to the upper bound of 100000 given in the problem.

Using these ideas you can build a bruteforce algorithm. Plotting the values of the radii which give valid triangles will help you find that you only need to loop over a small part of the radii values. Factoring these values will help you reduce even more the search space. I managed to  solve the problem in about 5 hours in Pari GP. This means things could be improved. However, having an algorithm which can give the result in “reasonable” time is fine by me.

## Balkan Mathematical Olympiad 2017 – Problems

Problem 1. Find all ordered pairs of positive integers ${ (x, y)}$ such that:

$\displaystyle x^3+y^3=x^2+42xy+y^2.$

Problem 2. Consider an acute-angled triangle ${ABC}$ with ${AB and let ${\omega}$ be its circumscribed circle. Let ${t_B}$ and ${t_C}$ be the tangents to the circle ${\omega}$ at points ${B}$ and ${C}$, respectively, and let ${L}$ be their intersection. The straight line passing through the point ${B}$ and parallel to ${AC}$ intersects ${t_C}$ in point ${D}$. The straight line passing through the point ${C}$ and parallel to ${AB}$ intersects ${t_B}$ in point ${E}$. The circumcircle of the triangle ${BDC}$ intersects ${AC}$ in ${T}$, where ${T}$ is located between ${A}$ and ${C}$. The circumcircle of the triangle ${BEC}$ intersects the line ${AB}$ (or its extension) in ${S}$, where ${B}$ is located between ${S}$ and ${A}$.

Prove that ${ST}$, ${AL}$, and ${BC}$ are concurrent.

Problem 3. Let ${\mathbb{N}}$ denote the set of positive integers. Find all functions ${f:\mathbb{N}\longrightarrow\mathbb{N}}$ such that

$\displaystyle n+f(m)\mid f(n)+nf(m)$

for all ${m,n\in \mathbb{N}}$

Problem 4. On a circular table sit ${\displaystyle {n> 2}}$ students. First, each student has just one candy. At each step, each student chooses one of the following actions:

• (A) Gives a candy to the student sitting on his left or to the student sitting on his right.
• (B) Separates all its candies in two, possibly empty, sets and gives one set to the student sitting on his left and the other to the student sitting on his right.

At each step, students perform the actions they have chosen at the same time. A distribution of candy is called legitimate if it can occur after a finite number of steps. Find the number of legitimate distributions.

(Two distributions are different if there is a student who has a different number of candy in each of these distributions.)

Source: AoPS

## Missing digit – short puzzle

The number $2^{29}$ has $9$ digits, all different; which digit is missing?