Square of an integer

Let a, b be positive integers such that ab +1 divides a^2+b^2. Show that


is the square of an integer.


This is a very well known problem. It first appeared in IMO 1988 held in Canberra, Australia. It even has its own Wikipedia page.

History Background

One of the organisers had sent this exercise to all professors of Number Theory to check if the exercise is original and try to solve it within 4 hours. No one was able to do so. However, one Bulgarian student managed to solve the problem in less than 4 hours ( his solution was fallen from the sky )  and for that he was awarded a special reward beyond the medal.



Choose integers a,b,k such that a^2+b^2=k(ab+1) Now, for fixed k, out of all pairs (a,b) choose the one with the lowest value of \min(a,b). Label b'=\min(a,b), a'=\max(a,b). Thus, a'^2-kb'a'+b'^2-k=0 is a quadratic in a'. Should there be another root, c', the root would satisfy: b'c'\leq a'c'=b'^2-k<b'^2\implies c'<b' Thus, c' isn’t a positive integer (if it were, it would contradict the minimality condition). But c'=kb'-a', so c' is an integer; hence, c'\leq 0. In addition, (a'+1)(c'+1)=a'c'+a'+c'+1=b'^2-k+b'k+1=b'^2+(b'-1)k+1\geq 1 so that c'>-1. We conclude that c'=0 so that b'^2=k.

This construction works whenever there exists a solution (a,b) for a fixed k, hence k is always a perfect square.

Read more

On permutation

Let x_1, x_2, \dots, x_k be vectors of m – dimensional Euclidean space such that x_1+x_2+\cdots+x_k=0. Prove that there exists a permutation \pi of the integers \{1, 2, \dots,k\} such that

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|\leq\left ( \sum_{i=1}^{k} \left \| x_i \right \|^2 \right )^{1/2}\]

for each n=1,2, \dots, k.


We define \pi inductively. Set \pi(1)=1.Assume \pi is defined for i=1, 2, \dots, n and also

(1)   \begin{equation*} \left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \end{equation*}

Note that (1) is true for n=1. We choose \pi(n+1) in a way that (1) is fulfilled for n+1 instead of n. Set y=\sum \limits_{i=1}^{n} x_{\pi(i)} and A=\{1,2, \dots, k\} \setminus \{\pi(i) : i=1,2, \dots, n\}. Assume that (y, x_r)>0 for all r \in A.  Then \left ( y , \sum \limits_{r \in A} x_r \right )>0 and in view of y + \sum \limits_{r \in A} x_r =0 ones gets -(y, y)>0 which is impossible. Hence , there is r\in A such that

(2)   \begin{equation*} (y, x_r)\leq 0\end{equation*}

Put \pi(n+1) = r . Then using (2) and (1) we have

    \begin{align*} \left \| \sum_{i=1}^{n+1} x_{\pi(i)} \right \|^2 &= \left \| y + x_r \right \|^2 \\ &=\left \| y \right \|^2 + 2\left ( y, x_r \right ) + \left \| x_r \right \|^2 \\ &\leq \left \| y \right \|^2 + \left \| x_r \right \|^2 \\ &\leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 + \left \| x_r \right \|^2\\ &= \sum_{i=1}^{n+1} \left \| x_{\pi(i)} \right \|^2 \end{align*}

which verifies (1) for n+1. Thus we define \pi for every n=1, 2, \dots, k. Finally from (1) we get

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{k} \left \| x_i \right \|^2\]

Read more

Does there exist an expression?

For which positive integers n does there exist expression

    \[\mathbb{R}^2 = \bigcup_{m=1}^{\infty} A_m\]

where each A_m is a disk of radius 1 such that each point x \in \mathbb{R}^2 belongs to either the boundary of some A_m or to precisely n interiors of the sets A_1 , A_2 , \dots ?

(Euler Competition , 2017)

Solution [official]

For none n. Assume , on the contrary , that such expression exists for some value of n. Let us first note that the set of disks is countable hence the Lebesgue measure of the union of all the circles is 0.

Further, consider any disk A_i and let us show that the number of the other disks it intersects is finite. Indeed, each disk that intersects A_k would have to be a subset of the disk or radius 3 co-centric with A_k. All such disks together would cover an area of at most 9 \pi so that each point is covered by at most n disks. Hence the total area of disks that intersect A_k is at most 9 \pi n and therefore there are not more than 9n of them.

Now, let us introduce the function f:\mathbb{R}^2 \rightarrow \mathbb{N} whose value f(P) is the number of disks A_i that P belongs to. Note that

  • f(P)=n for almost all P \in \mathbb{R}^2
  • f(P) is constant on every connected component of \mathbb{R}^2 \setminus \bigcup \limits_{k=1}^{\infty} \partial A_k.

What remains to be shown is that this is impossible. Since the disk A_i intersects only with finitely many other disks , let us consider the circular arc between two such intersection points such that the arc XY in the figure above. But then obviously the value f(P) for points on one side of the arc and f(P) for points on the other side of the arc differ by 1. For the collections of disks that cover the two regions is different – A_i is only on one side of the circular arc.

Read more

A divergent series

Let a_n be a positive and strictly decreasing sequence such that \lim a_n =0. Prove that the series

    \[\mathcal{S} = \sum_{n=1}^{\infty} \frac{a_n-a_{n+1}}{a_n}\]



We shall begin with a lemma.

Lemma: Let x_1, \dots, x_n \in (0, 1). It holds that

    \[\sum_{i=1}^n (1-x_i) \geqslant 1 - \prod_{i=1}^n x_i\]

Proof: We are using induction on n. For n=1 it is trivial. Suppose that it holds for n=k. Then

    \begin{align*} \sum_{i=1}^{k+1} (1-x_i) &= \left( \sum_{i=1}^{k} (1-x_i)\right) + (1-x_{k+1}) \\ &\geqslant \left(1 - \prod_{i=1}^k x_i\right) + (1-x_{k+1}) \\ &= 1 - \prod_{i=1}^{k+1} x_i + \\ & \quad \quad +\left(1 - \prod_{i=1}^k x_i\right)\left(1-x_{k+1}\right) \\ &\geqslant 1 - \prod_{i=1}^{k+1} x_i \end{align*}

Thus it holds for n=k+1 and the lemma is proved. Since a_n>0 and \lim a_n =0 I can find 1 = i_1 < i_2 < \cdots such that \frac{a_{i_{r+1}}}{a_{i_r}} < \frac{1}{2} for all r. But then

    \begin{align*} \sum_{n=1}^{i_k-1} \frac{a_n - a_{n+1}}{a_n} &= \sum_{r=1}^{k-1} \sum_{n=i_r}^{i_{r+1}-1}\left(1 - \frac{a_{n+1}}{a_n} \right) \\ &\geqslant \sum_{r=1}^{k-1} \left(1 - \frac{a_{i_{r+1}}}{a_{i_r}} \right) \\ &> \sum_{r=1}^{k-1} \frac{1}{2} \\ &> \frac{k-1}{2} \end{align*}

where in the first inequality the lemma was used.

The exercise can also be found at mathematica.gr . It can also be found in Problems in Mathematical Analysis v1 W.J.Kaczor M.T.Nowak as exercise 3.2.43 page 80 .


Read more

Seemous 2017/4

(a) Let n \in \mathbb{N} \cup \{ 0 \}. Evaluate the integral:

    \[\mathcal{J} = \int_0^1 \left( 1 - t \right)^n e^t \, {\rm d}t\]

(b) Let k \in \mathbb{N} \cup \{ 0 \} and let \{x_n\}_{n \geq k} be a sequence defined as

    \[x_n = \sum_{i=k}^n \binom{i}{k} \left(e - 1 - \frac{1}{1!} - \frac{1}{2!} - \cdots -\frac{1}{i!} \right)\]

Find the limit of x_n.


(a) We have successively:

    \begin{align*} \int_{0}^{1} \left ( 1-t \right )^n e^t \, {\rm d}t &\overset{u=1-t}{=\! =\! =\! =\!} \int_{0}^{1} u^n e^{1-u} \, {\rm d}u\\ &= e \int_{0}^{1}u^n e^{-u} \, {\rm d}u\\ &= e \gamma(n+1, 1)\\ &\!\overset{(*)}{=} e n!\left ( 1- e^{-1} \sum_{k=0}^{n} \frac{1}{k!} \right )\\ &= n! \left ( e - \sum_{k=0}^{n} \frac{1}{k!} \right ) \end{align*}

where \gamma denotes the lower incomplete Gamma function.

(b) We are invoking Tonelli’s theorem. Hence the limit we seek is equal to

    \begin{align*} \sum_{i=k}^{\infty} \binom{i}{k} \sum_{r=i}^{\infty} \frac{1}{(r+1)!} &= \sum_{r=k}^{\infty} \frac{1}{(r+1)!}\sum_{i=k}^{r} \binom{i}{k} \\ &= \sum_{r=k}^{\infty} \frac{1}{(r+1)!} \binom{r+1}{k+1}\\ &= \frac{1}{\left ( k+1 \right )!} \sum_{r=k}^{\infty} \frac{1}{\left ( r-k \right )!}\\ &= \frac{e}{\left ( k+1 \right )!} \end{align*}

Read more