Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $S= \{x_0,\dots,x_n\}$ be a finite subset of $[0,1]$ , $x_0=0$ and $x_1=1$ such that every distance between pair of elements of $S$ occurs at least twice, except for the distance $1$, then we are to show that $S$ is a subset of $\mathbb{Q}$.

share|cite|improve this question
Source: problem $3$. – user9413 Apr 13 '12 at 8:12
up vote 6 down vote accepted

Let $V$ be the $\mathbb{Q}$-vector space generated by $S$ and let $\leq$ be any total order on $V$ compatible with addition (forall $x,y,z \in V$, if $x \leq y$ then $x+z \leq y+z$, and more generally, any reasoning you are used to involving $+$ and $\leq$ is valid).
Then, for this particular total order, there is a unique pair $(x_i,x_j) \in S^2$ such that $x_i - x_j$ is the greatest distance between pair of elements of $S$ :

Since $S$ is finite and $\leq$ is total, the set $\{x-y, (x,y)\in S^2\}$ is finite so it has a maximal element $x_i - x_j$ for some pair $(x_i,x_j) \in S^2$.
Then we show it is unique : suppose there is $(x_k,x_l) \in V^2$ such that $(x_i - x_j) = (x_k - x_l)$.
Then $(x_i - x_j) + (x_i - x_j) = (x_k - x_l) + (x_i - x_j) = (x_k - x_j) + (x_i - x_l)$. Since $(x_i - x_j)$ is maximal, $(x_k - x_j) \leq (x_i - x_j)$ and $(x_i - x_l) \leq (x_i - x_j)$. If any of those two inequalities were strict, we would get the contradiction $(x_i - x_j) + (x_i - x_j) < (x_i - x_j) + (x_i - x_j)$, so they have to be equalities, which implies that $(x_k,x_l) = (x_i,x_j)$.

Now, the hypothesis on $S$ says that the only pairs $(x_i,x_j)$ such that $x_i-x_j$ is unique are the pairs $(0,1)$ and $(1,0)$. So it implies that for any total order on $V$ compatible with addition, this greatest distance is always $1$ or $-1$.

So we only need to show that if $V \neq \mathbb{Q}$, there must exist total orders $\leq$ on $V$ such that the greatest distance for $\leq$ is not $1$ or $-1$ :

Since $S$ generates $V$, and $(x_1 = 1)$ is free, we can add elements of $S$ to $(x_1)$ to form a basis $(e_1, \ldots, e_m) = (x_{i_1}, \ldots, x_{i_{m-1}},x_1)$ of $V$.

  • Pick the lexicographical order induced by this basis. It is caracterised by the property that $0 < \sum a_i e_i$ if and only if the first nonzero coefficient is positive.
    In particular, $(x_{i_1} - x_0) = x_{i_1} > \pm x_1 = \pm (x_1 - x_0) = \pm 1$, so neither $1$ nor $-1$ can be the greatest distance for $\leq$.

  • Define a linear application $f : V \to \mathbb{R}$ with $f(1) = 1$ and $f(x_{i_k}) = \pi^k$. Since $\pi$ is transcendental, this map $f$ is injective. Pick the order defined by $x \leq y \Leftrightarrow f(x) \leq_\mathbb{R} f(y)$, where $\leq_\mathbb{R}$ is the usual order on $\mathbb{R}$. But then, since $f(x_{i_1}) >_\mathbb{R} f(x_1)$, we have again $(x_{i_1} - x_0) = x_{i_1} > \pm x_1 = \pm (x_1 - x_0) = \pm 1$.

share|cite|improve this answer
first of all In the problem it is given that the points are in [0,1] so the greatest no $(x_i-x_j)$ is the unique no 1, there is nothing to prove in it ,secondly I do not understand why in lexicographic order a number which is not a rational number then why that will not be in [0,1]? – La Belle Noiseuse Apr 15 '12 at 19:13
Over all I have not understood properly. – La Belle Noiseuse Apr 15 '12 at 20:18

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.