18
$\begingroup$

If $t>0,t^2, t+\frac{1}{t},t+t^2,\frac{1}{t}+\frac{1}{t^2}$ are all irrational number, $$a_n=n+\left \lfloor \frac{n}{t} \right \rfloor+\left \lfloor \frac{n}{t^2} \right \rfloor,\\ b_n=n+\left \lfloor \frac{n}{t} \right \rfloor +\left \lfloor nt \right \rfloor,\\ c_n=n+\left \lfloor nt \right \rfloor+\left \lfloor nt^2 \right \rfloor, $$ then every positive integer appear exactly once. In other words, the sequences $a_1,b_1,c_1,a_2,b_2,c_2,\cdots$ together contain all the positive integers without repetition. I have checked every integer from $1$ to $10^6$ for $t=2^\frac{1}{4}$: $$a_n=1, 4, 7, 9, 12, 15, 16, 19, 22, 25, 27, 30, 32, 34, 37, 40, 43, 45, 47, 50,\dots \\ b_n=2, 5, 8, 11, 14, 18, 20, 23, 26, 29, 33, 36, 38, 41, 44, 48, 51, 54, 56, 59,\dots \\ c_n=3, 6, 10, 13, 17, 21, 24, 28, 31, 35, 39, 42, 46, 49, 53, 57, 61, 64, 67, 71,\dots $$

PS: This is a special case of following statement:

If $t_1,t_2,\cdots,t_k>0$,and $\forall i \not =j,\frac{t_j}{t_i}$ is irrational, $$a_i(n)=\sum_{j=1}^k{\left \lfloor \frac{t_j}{t_i}n \right \rfloor},i=1,2,\cdots,k,$$

then every positive integer appear exactly once in $a_1(n),\cdots,a_k(n)$.

$\endgroup$
6
  • 4
    $\begingroup$ Curious! An easy special case is that the claim holds when $t=(1+\sqrt5)/2$. In spite of $1/t+1/t^2$ then being equal to $1$. Then the $a$-sequence covers the odd natural numbers, and the other two partition the even numbers Beatty-style. All because $1+1/t=t$, $1+t=t^2$, and $(t,t^2)$ is a Beatty pair. $\endgroup$ Oct 12, 2019 at 7:30
  • 1
    $\begingroup$ Maybe it holds for all t>0 when t^2 is irrational. $\endgroup$
    – lsr314
    Oct 12, 2019 at 7:40
  • $\begingroup$ See this variant of Beatty from a week earlier. In some texts the Beatty construction is iterated to find partitions into more sequences. The idea is explained in this old answer by Achille Hui. That idea doesn't seem to work here because none of the sequences here are of the Beatty form due to the presence of several floor functions. $\endgroup$ Oct 16, 2019 at 10:44
  • $\begingroup$ Next, sorry about hijacking your question to an extent with the bounty. If you think you want to see more details and/or other answers I will happily sponsor another round later. $\endgroup$ Oct 19, 2019 at 16:20
  • $\begingroup$ @Jyrki Lahtonen Thanks, I added a more general statement :) $\endgroup$
    – lsr314
    Oct 22, 2019 at 14:05

2 Answers 2

9
+100
$\begingroup$

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.

$\endgroup$
15
  • 3
    $\begingroup$ It really is this simple. Well done. If I got it right: A) You only need $t^2$ to be irrational. B) A simpler form of the same argument would prove that the sequences $d_n=n+\lfloor n/t\rfloor$ and $e_n=n+\lfloor tn\rfloor$ also partition the naturals. Of course, $d$- and $e$-sequences form a Beatty pair. C) Generalization to four or more sequences comes naturally as long as we assume that relevant powers of $t$ are all irrational. My upvote was already there. $\endgroup$ Oct 13, 2019 at 8:56
  • $\begingroup$ Obviously need $t$ to be irrational in my item B. $\endgroup$ Oct 13, 2019 at 9:06
  • $\begingroup$ Thanks for your comments! I think you are right. $\endgroup$
    – Hw Chu
    Oct 13, 2019 at 11:51
  • 1
    $\begingroup$ Very nice answer! +1. @Next the argument is definitely correct. Here are some details. Let $\delta_1,\delta_2,\dots$ be the values of $\delta$ for which one of $\delta,\delta t,\delta t^2$ is an integer. What "$f(\delta)$ increases by exactly 1 after each step" means is that $f(\delta_1)=1,f(\delta_2)=2,f(\delta_3)=3,\dots$. We also have: if $\delta_n$ is an integer, $f(\delta_n) \in \{c_1,c_2,\dots\}$; if $t\delta_n$ is an integer, $f(\delta_n) \in \{b_1,b_2,\dots\}$; if $t^2\delta_n$ is an integer, $f(\delta_n) \in \{a_1,a_2,\dots\}$. First of all, since $f(\delta_n) = n$ for each $n$, $\endgroup$ Oct 23, 2019 at 5:26
  • 1
    $\begingroup$ clearly $\{a_n\}\cup\{b_n\}\cup\{c_n\} = \mathbb{N}$. Second of all, each $a_n$ is achieved as $f(\delta_k)$ for some $\delta_k$; indeed, for $\delta_k = \frac{n}{t^2}$. Similarly with $b_n$ and $c_n$. So, if some $a_n$ were equal to some $b_m$, we would have to have $\frac{n}{t^2}$ and $\frac{m}{t}$ be an integer simultaneously, which is impossible, since $t$ is irrational. This is (one of the three cases) why "no two of $\delta, \delta t, \delta t^2$ will hit an integer at the same time". $\endgroup$ Oct 23, 2019 at 5:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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