A Generalization of Beatty's Theorem

Solution 1:

Edited 10/24. Now this is largely expanded, probably longer than what it needs to be. TL;DR: Construct a function $f$, record where it ticks. The range of $f$ is exactly $\mathbb N$ and covers $\{a_n\}, \{b_n\}$ and $\{c_n\}$ without repetition.

That is true.

By substituting $t$ by $1/t$ if necessary, assume $t>1$. By adding dummy $\lfloor \cdot \rfloor$, we rewrite the sequences as $$ \begin{aligned} a_n &= \Big\lfloor\frac{n}{t^2}\Big\rfloor + \Big\lfloor\frac{n}{t}\Big\rfloor + \lfloor n\rfloor,\\ b_n &= \Big\lfloor\frac{n}{t}\Big\rfloor + \lfloor n \rfloor + \lfloor nt\rfloor,\\ c_n &= \lfloor n\rfloor + \lfloor nt\rfloor + \lfloor nt^2\rfloor. \end{aligned} $$

This suggests us the following process. We consider a function $$f(\delta) := \lfloor\delta\rfloor + \lfloor\delta t\rfloor + \lfloor\delta t^2\rfloor,$$ and start with $f(1/t^2) = a_1 = 1$. For convenience denote $\delta_1 = 1/t^2$.

Given $\delta_{i-1}$, we will obtain $\delta_i$ by the following process. We increase $\delta$ continuously from $\delta_{i-1}$, until we are in the situation that one of $\delta$, $\delta t$ or $\delta t^2$ hits an integer. Then we will call the new $\delta$ value $\delta_i$. Therefore we get a sequence $$\left\{\delta_1 = \frac1{t^2}, \delta_2, \cdots\right\}.$$

What do the function $f$ and the sequence $\{\delta_i\}$ tell us? Well, lets look at it.

1. $f$ only take values at integers, by the definition, and it is non-decreasing, with $f(\delta_1) = 1$. Therefore by restricting the domain, the range $$f\left(\left[\delta_1, \infty\right)\right) \subseteq \mathbb N.$$
2. In the interval $\delta \in (\delta_{i-1}, \delta_i)$, by the construction of the sequence $\{\delta_i\}$, $\delta, \delta t, \delta t^2$ have the same integral part as $\delta_{i-1}, \delta_{i-1}t, \delta_{i-1}t^2$, respectively. Hence $f(\delta) = f(\delta_{i-1})$. In other words, $\{\delta_i\}$ are the places when $f$ "jump in value". Written in math, $$f(\{\delta_i\}) = f\left(\left[\delta_1, \infty\right)\right) \subseteq \mathbb N.$$
3. For every $\delta_i$ in the sequence, $f(\delta_i)$ is in $\{a_n\}, \{b_n\}$ or $\{c_n\}$, depending on which of $\delta_i, \delta_it$ or $\delta_it^2$ is an integer. For instance, if $\delta_it = n$ is an integer, then $f(\delta_i) = \lfloor n/t\rfloor + \lfloor n\rfloor + \lfloor nt \rfloor = b_n$. So $$f(\{\delta_i\}) \subseteq \{a_n\} \cup \{b_n\} \cup \{c_n\}.$$
4. Converse to 3., whenever $\delta, \delta t$ or $\delta t^2$ is an integer, $\delta \in \{\delta_i\}$. In other words, the sequence $\{\delta_i\}$ can be obtained by merging and sorting the three sequences $\{n\}_{n=1}^\infty$, $\{n/t\}_{n=1}^\infty$ and $\{n/t^2\}_{n=1}^\infty$, or $$f(\{\delta_i\} \supseteq \{a_n\}) \cup \{b_n\} \cup \{c_n\}.$$
5. For an integer $i$, $f(\delta_i) = f(\delta_{i-1})+1$. Since $t$ and $t^2$ are irrational, only one of $\delta_{i-1}, \delta_{i-1}t, \delta_{i-1}t^2$ can be an integer. Same when $i-1$ is changed to $i$. Therefore, comparing $f(\delta_{i-1})$ and $f(\delta_i)$, two of the three terms are same (have the same integral part) and the third term jumps to the next integer. Therefore $f(\delta_i) = f(\delta_{i-1})+1$. Together with the fact $f(\delta_1) = 1$, we have $$f(\{\delta_i\}) = \mathbb N.$$ Putting 3., 4., and 5. together, we know that $$\{a_n\}\cup\{b_n\}\cup \{c_n\} = f(\{\delta_i\}) = \mathbb N.$$
6. If $a_n = b_{n'}$, from 4., there exist $i, i' \in \mathbb N$ such that $a_n = f(\delta_i)$ and $b_{n'} = f(\delta_{i'})$. From 5., it is enforced that $i = i'$. From the construction, this means that both $\delta_i$ and $\delta_i t$ are integers, hence $t \in \mathbb Q$, but this is impossible. Hence, $\{a_n\} \cap \{b_n\} = \varnothing$. Similarly, we have $$\{a_n\} \cap \{b_n\} = \{b_n\} \cap \{c_n\} = \{a_n\} \cap \{c_n\} = \varnothing.$$

This ends the proof of your conjecture.

Remarks, specializations and generalizations:

Playing with the "construct a floor function $f$ and record points where it jumped" trick as above by changing the function $f$, there are other things you can say:

• (From @Jyrki Lahtonen) Classic Beatty's theorem says, if $\alpha$ and $\beta$ are irrationals satisfying $$\frac1\alpha + \frac1\beta = 1$$, then $\lfloor n\alpha\rfloor$ and $\lfloor n\beta\rfloor$ forms a partition of $\mathbb N$. A little computation indicates $\alpha = 1 + \tau$ and $\beta = 1+\tau^{-1}$ for some irrational $\tau$. Rewrite $\lfloor n\alpha \rfloor = \lfloor n\rfloor+\lfloor n\tau\rfloor$ and $\lfloor n\beta \rfloor = \lfloor n\rfloor+\lfloor n\tau^{-1}\rfloor$, and consider the function $$f(\delta) = \lfloor\delta\rfloor + \lfloor\delta\tau\rfloor,$$ one can prove the classic Beatty theorem (probably this is not the proof of Beatty theorem most people know, at least I did not know at the beginning).
• Consider the function $$f(\delta) = \left\lfloor \delta\frac{t_1}{t_1}\right\rfloor + \left\lfloor \delta\frac{t_2}{t_1}\right\rfloor + \cdots + \left\lfloor \delta\frac{t_k}{t_1}\right\rfloor,$$ your last statement can be proved:

$\{a_i(n)\}$, $i = 1, \cdots, k$ forms a partition of $\mathbb N$, where $$a_i(n) = \sum_{j=1}^k \left\lfloor n\frac{t_j}{t_i}\right\rfloor.$$

• Pass to infinity. By considering the function $$f(\delta) = \sum_{i=1}^\infty \left\lfloor \delta \tau^{-i}\right\rfloor,$$ we can prove the following:

Let $\tau > 1$ be transcendental (like $\pi$; this is sufficient but not likely to be necessary). Then $$\mathbb N = \bigcup_{j=0}^\infty A_j, \quad A_{j} \cap A_{j'} = \varnothing \text{ if $j \neq j'$},$$ where $A_j = \{a_j^n\}_{n=1}^\infty$, and $$a_j^n = \sum_{i=0}^\infty \lfloor n\tau^{j-i}\rfloor.$$

This gives another proof that you can accommodate (countably) infinite travelers in infinitely many hotels, each hotel have infinitely many rooms, so that all rooms are occupied (i.e. the $\mathbb N = \mathbb N\times \mathbb N$ problem). This proof is neater than what I knew (the square grid trick), in my opinion.

You can further generalize by changing the sequence $\{\tau^i\}$ into other infinite sequence, but the descriptions get uglier and I will omit it.

Solution 2:

Often it's crucial how a question is formulated to understand it well. My following considerations involve a functional view. It's a proof for the generalisation.

$k\in\mathbb{N}~$ fixed.

$t_i\in\mathbb{R}^+~$ and $~\displaystyle t_i,\frac{t_j}{t_i}|_{j\neq i}~$ are irrational for all $~i,j\in\{1,2,...,k\}~\quad\quad (1)$

Let $~\displaystyle f(x):=\sum\limits_{j=1}^k\lfloor t_j\,x\rfloor~$ with $~x\in\mathbb{R}_0^+~$ . $~~~$ Note: $~\displaystyle a_i(n) \equiv f\left(\frac{n}{t_i}\right)$

It follows $~f(x_1)\leq f(x_2)~$ for all $~x_1\leq x_2~ . \hspace{4.7cm} (2)$

Define $~0~$ as a infinitesimal small positive value as a simplification for "choosing always a sufficient small value" as it is used in the sense of mathematical border processes for the left side $~x\to a-0~$ and for the right side $~x\to a+0~$ . $\hspace{4cm} (3)$

It means $~n=\lfloor n-0\rfloor + 1 ~$ for all natural $~n~$ .

Note: If someone has a problem with such a use of $~0~$ then it's better to define $~\delta>0~$ as a infinite small value so that $~n=\lfloor n-\delta\rfloor + 1 ~$ and substitute $~0~$ by $~\delta~$. But then the argumentation always has to be supplemented by $~\delta\to 0 ~$.

$\text{(A)}$

Because of $~(1)~$ we have $~\displaystyle\frac{n_1}{t_{i_1}}\neq\frac{n_2}{t_{i_2}}~$ for $~i_1\neq i_2~$ and $n_1, n_2\in\mathbb{N}~$, $~$ and

together with $~(2)~$ and $~(3)~$ we get $~\displaystyle f\left(\frac{n}{t_i}\right) = f\left(\frac{n-0}{t_i}\right) + 1~$; $~$ it follows:

$$\{f(x)\,|\,x\in\mathbb{R}_0^+\}=\mathbb{N}_0$$

In words: $~f(x)~$ grows always by $~1~$, $\,$there is never a jump of $~2~$ or more.

And $~\displaystyle f\left(\frac{n}{t_i}\right)-n = f\left(\frac{n-0}{t_i}\right)-\lfloor n-0\rfloor~$ tells us that $~f(x)~$ can only grow,

if at least one of it's components $~\left\lfloor t_j\,x\right\rfloor~$ grows:

$$\left\{f\left(\frac{n}{t_i}\right)|\,i\in\{1,2,...,k\}\right\}=\{f(x)\,|\,x\in\mathbb{R}_0^+\}$$

$\text{(B)}$

Because of $~(1)~$ we have $~\displaystyle\left|\frac{n_1}{t_{i_1}}-\frac{n_2}{t_{i_2}}\right|>0~$ for $~i_1\neq i_2~$ and $n_1, n_2\in\mathbb{N}~$ .

E.g. we choose $~\displaystyle\frac{n_1}{t_{i_1}}<\frac{n_2}{t_{i_2}}~$ and with $~(3)~$ we get $~\displaystyle\frac{n_1}{t_{i_1}}<\frac{n_2-0}{t_{i_2}}~$ .

Assume that $~\displaystyle f\left(\frac{n_1}{t_{i_1}}\right) = f\left(\frac{n_2}{t_{i_2}}\right)~$ .

Then we get $~\displaystyle f\left(\frac{n_1}{t_{i_1}}\right) = f\left(\frac{n_2-0}{t_{i_2}}\right) + 1~$ which means $~\displaystyle f\left(\frac{n_1}{t_{i_1}}\right) > f\left(\frac{n_2-0}{t_{i_2}}\right)~$ .

But this is a $\,$contradiction$\,$ to $~(2)~$ , $~$ so that we have

$$\left\{f\left(\frac{n_1}{t_{i_1}}\right)\right\}\cap\left\{f\left(\frac{n_2}{t_{i_2}}\right)\right\} = \emptyset$$

for all $~i_1\neq i_2~$ and $n_1, n_2\in\mathbb{N}~$ .

With $\text{(A)}$ and $\text{(B)}$ follows, that the claim is correct.