## A hint for Project Euler Pb 613

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

## Metapost – or how to code an image

What software do you use when you need to draw a nice image? I often need to draw things related to research and I never managed to efficiently use a software which uses the mouse or touchpad to draw and modify things. Moreover, if you need to add some mathematical text to the figure things get even more complicated. For me it is more natural to use code to generate graphics, if this is possible. Using something like Matlab to draw is possible. The advantage is that once you have a working code which produces what you want, you can easily modify it. If you have an image where you need to repeat things, using loops can facilitate the job (programmers will understand…).

This is were Metapost comes into play. I found this a long time ago while searching for a tool to build nice graphics for my master thesis. Being used to LaTeX for typesetting math, it was a natural way to draw using code. I do not claim it is the best or the simplest way, but for me it works. Most importantly, it allows me to build high quality, vectorized graphics, which are memory efficient. The advantage of vector graphics is that you can zoom as much as you want and you’ll never see the pixels.

There are a bunch of places where you can learn Metapost. I’ll put here some references I use a lot. The easiest way to start drawing in Metapost is to take a look at some existing codes and modify them. You can find lots of examples in this tutorial. If you have a linux system, you can compile metapost .mp files to obtain high quality pdfs using the command mptopdf. If not, then you can use the online Metapost editor found here. In any case, here are some of my codes for some drawings in Metapost.

Here is the code for my website logo: If you want to see the lossless vectorized pdf click to see the following file: logo-0    You can see that it has a border which changes from one color to another. This was done using a loop and a parameter to vary the color as we go along the boundary.

prologues:=3;
verbatimtex
%&latex
\documentclass{minimal}
\begin{document}
etex
beginfig(0);
% copy from here to use the online previewer
u:=25; % 25 = 25bp = 25 PostScript points = 25/72 in
wi:=10; % width in units u
he:=7; % height in units u
hoehe:=he*u; % height
breite:=wi*u;
%for i=0 upto he:
%draw (0, i*u)--(breite, i*u) withcolor .7white;
%endfor
%for j=0 upto wi:
%draw (j*u, 0)--(j*u, hoehe) withcolor .7white;
%endfor;
path p,q;
p:=(6u,0.5u)--(6u,0)--(0,0)--(0,6u)--(6u,6u)--(6u,5.5u);
pickup pensquare scaled 20;
draw p;
h=length(p);
numeric c,d,detail;
color a,b,co;
a:=(1,0.45,0);
b:=.2white;
co:=.2white;
detail:=500;
for i=1 upto (detail/2):
q := subpath (h*(i-1)/detail,h*i/detail) of p;
draw q withcolor (2*i/detail)[a,b];
endfor;
for i=detail downto (1+detail/2):
q := subpath (h*(i-1)/detail,h*i/detail) of p;
draw q withcolor (2*(detail-i)/detail)[a,b];
endfor;
label ("B",(1/15)*(2.6u,2.7u)) scaled 15 withcolor co ;
label ("2" infont defaultfont scaled 8,(4.9u,4.1u))
withcolor co;
% end copy here for online previewer
endfig;
end;


Here’s another example of a figure where I needed a grid of disks aligned on top of another figure. Using loops in Metapost allowed me to get what I wanted:

For the high quality pdf click here: cioranescu-murat-0  and see the code below

prologues:=3;
verbatimtex
%&latex
\documentclass{minimal}
\begin{document}
etex
beginfig(0);
u:=25; % 25 = 25bp = 25 PostScript points = 25/72 in
wi:=10; % width in units u
he:=7; % height in units u
hoehe:=he*u; % height
breite:=wi*u;

path p,pa;
p:=(0,4u)..(0,2u)..(2u,2u)..(3u,u)..(3u,0)..(6u,u)..(7u,3u)..(9u,5u)..cycle;
pa:=(3u,5u)..(5u,6u)..(8u,6u)..(8u,3.8u)..(7.5u,3.4u)..(7u,3u)..cycle;
draw p;
fill p withcolor .8white;
pair a,b;
h=length(p);
i=5;
numeric c,d;
c:=0.65*h;
d:=0.7*h;
a:= point c of p;
b:= point d of p;
pickup pencircle scaled 1.5;
%draw a;
%draw b;
path q,r,s;
q:= subpath (c,d) of p;
%draw q withcolor red;
%r:= b..((a+b)/2 shifted (.5(a-b) rotated -90))..a;
%draw r;
%fill buildcycle(r,q) withcolor .5red;
%fill pa withcolor .9999blue;
%label.rt(btex $\Omega$ etex,.5(u,3u))  scaled 2;

draw (-u,9u)-- (10u,9u)--(10u,-2u)--(-u,-2u)--cycle;
for i=0 upto 9:
for j=-1 upto 8:
draw fullcircle scaled 0.3u shifted (i*u, j*u);
fill fullcircle scaled 0.3u shifted (i*u, j*u) withcolor white;
endfor
endfor;
endfig;
end;


There are many ways today to draw what you want. Metapost is one of the tools available, if you like coding.

Categories: Programming

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

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