MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It was proved here that if $a\in \mathbb{N}_{\geq3}$ then

$$\bigcap_{i = 1}^{a} \bigcup_{j = 0}^{i-1} \left[\frac{1+aj}{i},\frac{a(j+1)-1}{i}\right] = \varnothing \tag{1}$$

It may be conjectured that forcing $i\ne b$, where $1\leq b< a$, renders $(1)$ untrue, that is, the result is not an empty interval.

We look at the diagram here from the link above for $a=5$ to get a better picture:
Red is the interval, Yellow are the gaps between the intervals that cause the intersection to be a null set, white gaps do not effect the intersection. The conjecture here says that if we were to remove any one of the top $4$ strips, then there will form a region of intersection.

I tried analyzing the gaps but everything seems to meet up at a dead end.

What tools may one employ to handle such problems?

share|cite|improve this question
It looks a bit Cantor-setish.. – Felix Goldberg May 26 '13 at 10:46
Another way to state the original is that for every number $x\in [0,1]$ there is some $1 \le i \le a$ so that $i x$ is within $1/a$ of an integer $j$. Your conjecture is that for any $1 \le b \lt a$, there is some $x \in [0,1]$ so that the only one of $x, 2x, ..., ax$ which is within $1/a$ of an integer is $bx$. – Douglas Zare May 26 '13 at 12:10
Which is just $x=\frac ca+\frac 1a^2$ when $b$ and $a$ are relatively prime with $c$ given by $bc\equiv -1\mod a$. So, when $a$ is prime, it is certainly true. – fedja May 26 '13 at 16:12
Sorry, $\frac ca+\frac 1{a^2}$, of course... – fedja May 26 '13 at 16:13
It's interesting that fedja's answer for $(a,b)=1$ and mine correspond to different endpoints of the interval of solutions for $b=2, a=5$. – Douglas Zare May 27 '13 at 3:03
up vote 6 down vote accepted

As I commented, the original result can be restated as that for every $x \in [0,1]$ (or $x\in \mathbb R$) there is some $1\le i\le a$ so that $ix$ is within $1/a$ of an integer (and the proof is the pigeonhole principle -- two of the fractional parts of $0,x,2x,...,ax$ must be within $1/a$ of each other, so their difference is within $1/a$ of an integer). Your conjecture is that for any $1\le b \lt a$ there is some $x$ so that the only one of $x,2x,...,ax$ within $1/a$ of an integer is $bx$. For example, for $a=5$ and $b=2$, then if we take $x \in [\frac{44}{100},\frac{45}{100}] \cup [\frac{55}{100},\frac{56}{100}]$ then the only one of the first $5$ multiples within $1/5$ of an integer is the second.

If $2b \gt a$ then $x=1/b$ works. Since $b\lt a$, $i/b$ is within $1/a$ of an integer only when $i$ is a multiple of $b$.

For $2b \le a$ we can modify this to $x=1/b + 1/(2ab) = \frac{2a+1}{2ab}$. This is designed so that $bx = \frac{2ab + b}{2ab} = 1 + \frac{1}{2a}$ is within $1/a$ of $1$, but $2bx = 2 + \frac{1}{a}$ just barely misses being within $1/a$ of $2$. Larger multiples of $bx$ are also too large, $bix - i = \frac{i}{2a} \ge \frac{1}{a},$ while $(bi-1)x$ is too small to be within $1/a$ of $i$ when $bi-1 \le a$. $i - \frac{(bi-1)(2a+1)}{2ab} = \frac{2a - (bi-1)}{2ab} \ge \frac{a}{2ab} = \frac{1}{2b} \ge \frac{1}{a}.$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.