Numbers and Sequences

Construct the set

$$𝑇=\{𝑛-𝑘+1:𝑛\in 𝑆\}.$$

Note that $𝑇$ is a subset of ${\mathbb{Z}}^{+}$, since $𝑛\geq 𝑘$ for all $𝑛\in 𝑆$. Since $𝑆$ is nonempty, so is $𝑇$. By the well-ordering principle, there exists a least integer $𝑡$ in $𝑇$. There exists $𝑠\in 𝑆$ such that $𝑡=𝑠-𝑘+1$. We want to show that $𝑠$ is the least element of $𝑆$. Let $𝑚$ be any integer in $𝑆$. Then $𝑚-𝑘+1$ is in $𝑇$. Since $𝑡$ is the least element of $𝑇$,

$$𝑚-𝑘+1\leq 𝑡=𝑠-𝑘+1,$$

so $𝑚\leq 𝑠$. Thus $𝑠$ is the least element of $𝑆$.

Taking the negative signs over

$$\lfloor 𝑥\rfloor \leq 𝑥<\lfloor 𝑥\rfloor +1$$

yields

$$-\lfloor 𝑥\rfloor -1<-𝑥\leq -\lfloor 𝑥\rfloor$$

Add into

$$𝑛\leq 𝑥<𝑛+1,$$

we have

$$𝑛-\lfloor 𝑥\rfloor -1<0<𝑛-\lfloor 𝑥\rfloor +1.$$

Therefore,

$$-1<𝑛-\lfloor 𝑥\rfloor <1.$$

Since $𝑛-\lfloor 𝑥\rfloor \in \mathbb{Z}$, we must have $𝑛-\lfloor 𝑥\rfloor =0$, i.e., $𝑛=\lfloor 𝑥\rfloor$.

Add $𝑛$ into

$$\lfloor 𝑥\rfloor \leq 𝑥<\lfloor 𝑥\rfloor +1$$

, we have

$$\lfloor 𝑥\rfloor +𝑛\leq 𝑥+𝑛<(\lfloor 𝑥\rfloor +𝑛)+1.$$

By Proposition 1.2, $\lfloor 𝑥\rfloor +𝑛=\lfloor 𝑥+𝑛\rfloor$.

We have

$$\lfloor 𝑥\rfloor \leq 𝑥<𝑦<\lfloor 𝑦\rfloor +1.$$

Therefore,

$$\lfloor 𝑥\rfloor <\lfloor 𝑦\rfloor +1.$$

Since $\lfloor 𝑥\rfloor$ and $\lfloor 𝑦\rfloor +1$ are integers, we must have $\lfloor 𝑥\rfloor \leq \lfloor 𝑦\rfloor$.

Write

$$𝑥=\lfloor 𝑥\rfloor +\{𝑥\}\quad 𝑦=\lfloor 𝑦\rfloor +\{𝑦\}.$$

We have

$$𝑥+𝑦=(\lfloor 𝑥\rfloor +\lfloor 𝑦\rfloor )+(\{𝑥\}+\{𝑦\}).$$

Note that $0\leq \{𝑥\}+\{𝑦\}<2$.

If $\{𝑥\}+\{𝑦\}<1$, then $\{𝑥\}+\{𝑦\}$ is precisely the fraction part of $𝑥+𝑦$. Thus, $\lfloor 𝑥+𝑦\rfloor =\lfloor 𝑥\rfloor +\lfloor 𝑦\rfloor$.

On the other hand, if $1\leq \{𝑥\}+\{𝑦\}<2$, then the fraction part of $𝑥+𝑦$ is $\{𝑥\}+\{𝑦\}-1$. Consequently, $\lfloor 𝑥+𝑦\rfloor =\lfloor 𝑥\rfloor +\lfloor 𝑦\rfloor +1$.

Therefore, $\lfloor 𝑥+𝑦\rfloor$ is either $\lfloor 𝑥\rfloor +\lfloor 𝑦\rfloor$ or $\lfloor 𝑥\rfloor +\lfloor 𝑦\rfloor +1$, which implies that (1.1) holds.

We have seen that if $\{𝑥\}+\{𝑦\}<1$, then $\{𝑥\}+\{𝑦\}$ is precisely the fraction part of $𝑥+𝑦$, i.e., $\{𝑥+𝑦\}=\{𝑥\}+\{𝑦\}$. Take fraction on both sides and apply Proposition 1.5,

$$\{𝑥+𝑦\}=\{\{𝑥+𝑦\}\}=\{\{𝑥\}+\{𝑦\}\}.$$

If $1\leq \{𝑥\}+\{𝑦\}<2$, then we have seen that the fraction part of $𝑥+𝑦$ is $\{𝑥\}+\{𝑦\}-1$, i.e., $\{𝑥+𝑦\}=\{𝑥\}+\{𝑦\}-1$. Move the $1$ to the LHS,

$$1+\{𝑥+𝑦\}=\{𝑥\}+\{𝑦\}.$$

Note that LHS can be regard as a decomposition of the greatest integer part $1$ and the fraction part $\{𝑥+𝑦\}$ of the real number $1+\{𝑥+𝑦\}$. Take the fraction on both sides,

$$\{𝑥+𝑦\}=\{1+\{𝑥+𝑦\}\}=\{\{𝑥\}+\{𝑦\}\}.$$

Substitude $𝑥←𝑥-𝑦$ in (1.1),

$$\lfloor 𝑥-𝑦\rfloor +\lfloor 𝑦\rfloor \leq \lfloor 𝑥\rfloor \leq \lfloor 𝑥-𝑦\rfloor +\lfloor 𝑦\rfloor +1.$$

Rearranging the terms, we get (1.2).

Write

$$𝑥-𝑦=(\lfloor 𝑥\rfloor -\lfloor 𝑦\rfloor )+(\{𝑥\}-\{𝑦\}).$$

Note that $-1<\{𝑥\}-\{𝑦\}<1$.

If $\{𝑥\}-\{𝑦\}\geq 0$, then $\{𝑥\}-\{𝑦\}$ is the fraction part of $𝑥-𝑦$, i.e., $\{𝑥-𝑦\}=\{𝑥\}-\{𝑦\}$. And then take the fraction on both sides,

$$\{𝑥-𝑦\}=\{\{𝑥-𝑦\}\}=\{\{𝑥\}-\{𝑦\}\}.$$

The other case is that $-1<\{𝑥\}-\{𝑦\}<0$, equivalently, $0<\{𝑥\}-\{𝑦\}+1<1$. Then $\{𝑥\}-\{𝑦\}+1$ is the fraction part of $𝑥-𝑦$, i.e., $\{𝑥-𝑦\}=\{𝑥\}-\{𝑦\}+1$. Move $1$ to the LHS,

$$-1+\{𝑥-𝑦\}=\{𝑥\}-\{𝑦\}.$$

Take the fraction on both sides,

$$\{𝑥-𝑦\}=\{-1+\{𝑥-𝑦\}\}=\{\{𝑥\}-\{𝑦\}\}.$$

Write $𝑥=\lfloor 𝑥\rfloor +\{𝑥\}$. Apply the negative sign over to both sides,

$$-𝑥=-\lfloor 𝑥\rfloor -\{𝑥\}.$$

If $𝑥\in \mathbb{Z}$, then $\lfloor -𝑥\rfloor =-\lfloor 𝑥\rfloor$ and $\{-𝑥\}=0$.

If $𝑥\notin \mathbb{Z}$, we have

$$-𝑥=(-\lfloor 𝑥\rfloor -1)+(1-\{𝑥\}).$$

Note that $0<1-\{𝑥\}<1$, which means it is the fraction part of $-𝑥$. Thus, $\lfloor -𝑥\rfloor =-\lfloor 𝑥\rfloor -1$ and $\{-𝑥\}=1-\{𝑥\}$

We prove by contradiction. Suppose box $𝑖$ contains ${𝑛}_{𝑖}$ objects, for $𝑖=1,\ldots ,𝑘$. Assume that every box contains at most one object, i.e., ${𝑛}_{𝑖}\leq 1$ for all $𝑖=1,\ldots ,𝑘$. Then in total there are $𝑛={𝑛}_{1}+\cdots +{𝑛}_{𝑘}\leq 𝑘$ objects, a contradiction. Therefore there exists $𝑖\in \{1,\ldots ,𝑘\}$ such that ${𝑛}_{𝑖}\geq 2$.

Divide $[0,1]$ evenly into $𝑛+1$ buckets, the intervals

$$\left[0,\frac{1}{𝑛+1}\right),\left[\frac{1}{𝑛+1},\frac{2}{𝑛+1}\right),\ldots ,\left[\frac{𝑛}{𝑛+1},1\right]$$

with the last one closed. They partition $[0,1]$.

Now consider the $𝑛+2$ numbers

$$𝐴=(0,\{𝑥\},\{2𝑥\},\ldots ,\{𝑛𝑥\},1).$$

Here $𝐴$ is a list rather than a set, since there may be duplicates. All $𝑛+2$ of them lie in $[0,1]$. Put them into the $𝑛+1$ buckets. By the pigeonhole principle Theorem 1.1, at least two fall into the same bucket. There are three cases.

Case $1$. $[0,1/(𝑛+1))$ contains at least two of $𝐴$. $0$ is certainly one of them; $1$ cannot be. So $\{𝑎𝑥\}\in [0,1/(𝑛+1))$ for some $𝑎\in \{1,\ldots ,𝑛\}$. We have

$$𝑎𝑥-\lfloor 𝑎𝑥\rfloor =\{𝑎𝑥\}<\frac{1}{𝑛+1}.$$

Let $𝑏=\lfloor 𝑎𝑥\rfloor$ and (1.4) holds.

Case $2$. $[𝑛/(𝑛+1),1]$ contains at least two of $𝐴$. $1$ is certainly one of them; $0$ cannot be. So $\{𝑎𝑥\}\in [𝑛/(𝑛+1),1]$ for some $𝑎\in \{1,\ldots ,𝑛\}$. We have

$$1-\{𝑎𝑥\}<\frac{1}{𝑛+1}.$$

Write $\{𝑎𝑥\}=𝑎𝑥-\lfloor 𝑎𝑥\rfloor$ and rearrange:

$$|𝑎𝑥-(1+\lfloor 𝑎𝑥\rfloor )|<\frac{1}{𝑛+1}$$

Let $𝑏=1+\lfloor 𝑎𝑥\rfloor$ and (1.4) holds.

Case $3$. This is the interesting part. Suppose neither $[0,1/(𝑛+1))$ nor $[𝑛/(𝑛+1),1]$ contains at least two numbers of $𝐴$. Then some interval

$$𝐼=\left[\frac{𝑘}{𝑛+1},\frac{𝑘+1}{𝑛+1}\right)$$

with $𝑘\in \{1,\ldots ,𝑛-1\}$ contains at least two numbers of $𝐴$. It cannot contain $0$ or $1$. So there exist ${𝑎}_{1},{𝑎}_{2}\in \{1,\ldots ,𝑛\}$ with ${𝑎}_{1}\neq {𝑎}_{2}$ such that $\{{𝑎}_{1}𝑥\}$ and $\{{𝑎}_{2}𝑥\}$ both lie in $𝐼$. Their distance is then less than $1/(𝑛+1)$:

$$|\{{𝑎}_{1}𝑥\}-\{{𝑎}_{2}𝑥\}|<\frac{1}{𝑛+1}.$$

Without loss of generality, $\{{𝑎}_{1}𝑥\}\geq \{{𝑎}_{2}𝑥\}$. Thus

$$0\leq \{{𝑎}_{1}𝑥\}-\{{𝑎}_{2}𝑥\}<\frac{1}{𝑛+1}.$$

The fractional part of a number already in $[0,1)$ is itself, so

$$\{\{{𝑎}_{1}𝑥\}-\{{𝑎}_{2}𝑥\}\}<\frac{1}{𝑛+1}.$$

By (1.3) we obtain

$$\{({𝑎}_{1}-{𝑎}_{2})𝑥\}<\frac{1}{𝑛+1}$$

since $\{\{{𝑎}_{1}𝑥\}-\{{𝑎}_{2}𝑥\}\}=\{{𝑎}_{1}𝑥-{𝑎}_{2}𝑥\}$.

If ${𝑎}_{1}>{𝑎}_{2}$, let $𝑎={𝑎}_{1}-{𝑎}_{2}$. Clearly $1\leq 𝑎<𝑛$. Then

$$\{𝑎𝑥\}<\frac{1}{𝑛+1}.$$

The same argument as in Case $1$ finishes it.

If ${𝑎}_{1}<{𝑎}_{2}$, let $𝑎={𝑎}_{2}-{𝑎}_{1}$. We have

$$\{-𝑎𝑥\}<\frac{1}{𝑛+1}.$$

If $𝑎𝑥\in \mathbb{Z}$, we are already done. If $𝑎𝑥\notin \mathbb{Z}$, then by Proposition 1.7 we have $\{-𝑎𝑥\}=1-\{𝑎𝑥\}$. Therefore

$$0\leq 1-\{𝑎𝑥\}<\frac{1}{𝑛+1}.$$

Hence

$$|𝑎𝑥-(1+\lfloor 𝑎𝑥\rfloor )|=(1+\lfloor 𝑎𝑥\rfloor )-𝑎𝑥<\frac{1}{𝑛+1}.$$

Take $𝑏=1+\lfloor 𝑎𝑥\rfloor$ and we are done.

(1.5) is equivalent to

Before we go into the proof, a few observations.

$𝑞=1$ clearly satisfies. Let ${\varepsilon }^{\prime }=|𝑥-\lfloor 𝑥\rfloor |$ and ${\varepsilon }^{\prime\prime }=|𝑥-(\lfloor 𝑥\rfloor +1)|$, the two distances from $𝑥$ to the integers adjacent to it.

Now suppose $𝑞$ and $𝑝$ satisfy (1.6) with $𝑞\geq 2$, and let $\varepsilon =|𝑞𝑥-𝑝|$. Then $\varepsilon >0$, since $𝑥$ is irrational. Note also that $𝑞𝑥$ can never be the midpoint of two consecutive integers, and that $\varepsilon <1/2$. For any other integer $𝑎\neq 𝑝$, we must have

$$|𝑞𝑥-𝑎|>\varepsilon =|𝑞𝑥-𝑝|.$$

That is, $𝑝$ is the closest integer to $𝑞𝑥$ when $𝑞\geq 2$.

We prove by contradiction. Assume there are only finitely many such positive integers, $\{1,{𝑞}_{1},\ldots ,{𝑞}_{𝑛}\}$. Let ${𝑝}_{𝑖}$ be the associated integer for which (1.6) holds, i.e.,

$${\varepsilon }_{𝑖}=|{𝑞}_{𝑖}𝑥-{𝑝}_{𝑖}|<\frac{1}{{𝑞}_{𝑖}}.$$

We aim to produce a contradiction by finding another qualified integer $𝑞$. Let $𝑁\in {\mathbb{Z}}^{+}$ be such that

$$𝑁>\max \left(\frac{1}{{\varepsilon }^{\prime }},\frac{1}{{\varepsilon }^{\prime\prime }},\frac{1}{{\varepsilon }_{1}},\ldots ,\frac{1}{{\varepsilon }_{𝑛}}\right).$$

By Theorem 1.2, there exist $𝑞\in \{1,\ldots ,𝑁\}$ and $𝑝\in \mathbb{Z}$ such that

$$\varepsilon =|𝑞𝑥-𝑝|<\frac{1}{𝑁+1}<\frac{1}{𝑁}\leq \frac{1}{𝑞}.$$

Note that

$$\varepsilon <\frac{1}{𝑁}<{\varepsilon }_{𝑖}\quad \forall 𝑖\in \{1,\ldots ,𝑛\}.$$

Also

$$|𝑥-𝑝|\geq \min ({\varepsilon }^{\prime },{\varepsilon }^{\prime\prime })>\varepsilon .$$

If $𝑞=1$, then $\varepsilon =|𝑥-𝑝|$, which is impossible. Thus $𝑞\neq 1$, so $𝑞\geq 2$. If $𝑞={𝑞}_{𝑖}$ for some $𝑖$, then $𝑝$ is the closest integer to ${𝑞}_{𝑖}𝑥$, hence $𝑝={𝑝}_{𝑖}$ and $\varepsilon ={\varepsilon }_{𝑖}$, contradicting $\varepsilon <{\varepsilon }_{𝑖}$. Therefore $𝑞\notin \{1,{𝑞}_{1},\ldots ,{𝑞}_{𝑛}\}$, and yet $𝑞$ and $𝑝$ satisfy (1.6). This is a contradiction, which concludes the proof.