NMO Selection Tests for the Balkan and International Mathematical Olympiads

(a) Suppose that two such integers, $a<b$, exist. Let $m$ be the squarefree part of $a$; $a=m{s}^2$, $s\in \mathbb{Z}$. Then $mb$ is a square, so since $m$ is squarefree, $b=m{t}^2$ for some integer $t\ge s+1$. Hence $${\left(1+\frac{1}{s}\right)}^2\le \frac{t^2}{s^2}=\frac{b}{a}<\frac{(k+1{)}^2}{k^2}={\left(1+\frac{1}{k}\right)}^2,$$ so $s>k$. Consequently, $b=m{t}^2\ge m(s+1{)}^2>(k+1{)}^2$ – a contradiction.

(b) We show that the statement holds whenever $k\ge 3^{n-1}$; if $n$ is odd, the weaker condition $k\ge 2^{n-1}$ suffices. We require a LEMMA whose proof offers no difficulty. LEMMA. If $C>0$ and $n\ge 2$, then $(k+1{)}^n>(k^{n/(n-1)}+C{)}^{n-1}$ for all $k\ge C^{n-1}$. Now let $n$ be odd, let $a$ be the smallest integer greater than $k^{n/(n-1)}$, and let $b=a+1$. The $n$ integers $a^{n-i-1}{b}^i$, $i=0,1,2,\dots ,n-1$, are distinct, and their product is the $n$-th power of $(ab{)}^{(n-1)/2}$. The smallest of them, $a^{n-1}$, exceeds $k^n$, and the largest, $b^{n-1}$, is at most $(k^{n/(n-1)}+2{)}^{n-1}$. By the LEMMA, this is at most $(k+1{)}^n$ when $k\ge 2^{n-1}$. Next, we turn to the case of even $n$. Let again $a$ be the smallest integer greater than $k^{n/(n-1)}$, and let $b=a+1$ and $c=a+2$. Let further $x_i=a^{n-i}{b}^i$ and $y_i=b^{i-1}{c}^{n-i}$, $i=1,2,\dots ,n-1$. Note that $$k^n<x_1<x_2<x_3<\cdots <x_{n-1}<y_{n-1}<y_{n-2}<\cdots <y_2<y_1\le (k^{n/(n-1)}+3{)}^{n-1},$$ so these $2n-2$ integers are distinct, and by the LEMMA they are in the proper range when $k\ge 3^{n-1}$. We end the proof by showing that we can choose $n$ of these integers so that the product is a perfect $n$-th power. If $n$ is divisible by 4, say $n=4m$, choose $x_1,x_3,x_5,\dots ,x_{4m-1},y_1,y_3,y_5,\dots ,y_{4m-1}$; their product is the $n$-th power of $a^m{b}^{2m-1}{c}^m$. If $n=8m+2$, $m>0$, take $x_2,x_3,x_4,\dots ,x_{4m+2},y_2,y_3,y_4,\dots ,y_{4m+2}$; the product of these is the $n$-th power of $a^{3m}{b}^{2m+1}{c}^{3m}$. Finally, if $n=8m+6$, select $$x_1,x_2,x_3,\dots ,x_{4m+3},y_1,y_2,y_3,\dots ,y_{4m+3},$$ in which case the product is the $n$-th power of $a^{3m+2}{b}^{2m+1}{c}^{3m+2}$.