Let $a<b<c$ be three positive integers. Prove that among any $2c$ consecutive positive integers there exist three different numbers $x,y,z$ such that $abc$ divides $xyz$.
Problem
Source: Baltic Way 1995
Tags: number theory proposed, number theory
GlassBead
08.10.2011 23:07
Note that among any $2c$ consecutive integers, there are at least $2$ multiples of $c$, and more than $2$ multiples of $a, b$. Then just choose $x$ such that it's a multiple of $a$, $y$ such that it's a multiple of $b$, and $z$ such that it's a multiple of $c$.
Tintarn
07.09.2019 17:56
GlassBead wrote: Note that among any $2c$ consecutive integers, there are at least $2$ multiples of $c$, and more than $2$ multiples of $a, b$. That's not correct. Of course there are exactly $2$ multiples of $c$ and at least $2$ multiples of each $a$ and $b$. But it is not necessarily true that there are more than $2$ multiples of $a$ or $b$. For instance, consider $c=4, b=3$ and the numbers $1,2,\dots,8$ which only contain $2$ multiples of $b$.
The problem is still not very hard, but a little more subtle.
Let's take two multiples of each $a,b$ and $c$ and call them $a_1,a_2,b_1,b_2,c_1,c_2$ where we assume that $\vert a_2-a_1\vert=a, \vert b_2-b_1\vert=b, \vert c_2-c_1\vert=c$.
Note that some of these numbers can be identical (otherwise the problem would be trivial) but we show that "sufficiently many of them are not".
Indeed, since $a<b<c$, no two of the sets $A=\{a_1,a_2\},B=\{b_1,b_2\}$ and $C=\{c_1,c_2\}$ are identical.
Let's just try to choose $x=a_1$. Suppose that $a_1$ occurs neither in $B$ nor in $C$. Then since $B \ne C$, we can certainly find $y \in B, z \in C$ such that $x,y,z$ are distinct and we win. So we may assume that $a_1$ occurs in $B$ or in $C$.
Similarly, $a_2$ must occur in $B$ or in $C$. But they cannot occur in the same set.
So we may assume that $a_1=b_1$ and $a_2=c_2$. But then we can take $x=a_1=b_1, y=b_2, z=a_2=c_2$.