A Generalization of Beatty's Theorem

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.