A sequence of positive integers $(a_n)_{n \ge 1}$ is of Fibonacci type if it satisfies the recursive relation $a_{n + 2} = a_{n + 1} + a_n$ for all $n \ge 1$. Is it possible to partition the set of positive integers into an infinite number of Fibonacci type sequences? Proposed by Ivan Borsenco
Problem
Source: USA TSTST 2017, Problem 6, proposed by Ivan Borsenco
Tags: algebra, TSTST 2017, Tstst, number theory, TST, Fibonacci
v_Enhance
29.06.2017 06:04
One possible solution is via Wythoff array... this basically follows from Zeckendorf theorem on Fibonacci representations. There's a longer analytic solution which is i.m.o. more natural, but I have not written up the details.
62861
29.06.2017 06:06
Alternatively, one can use the fact that this old IMO problem Quote: Let $\mathbb{N} = \{1,2,3, \ldots\}$. Determine if there exists a strictly increasing function $f: \mathbb{N} \mapsto \mathbb{N}$ with the following properties: (i) $f(1) = 2$; (ii) $f(f(n)) = f(n) + n, (n \in \mathbb{N})$. has a valid function $f$; then, we just simply let $f(n)$ be the next integer after $n$. (This gives the same construction as the Wythoff array.)
Alison
29.06.2017 22:23
This problem appeared on the 2000 Estonian math olympiad. It also appeared on the ARML 2003 Power Round, along with hints in the earlier problems. I don't remember what the intended solution was, but it wasn't the Zeckendorf one (though that was the one I wrote up when taking the competition). I may have to dig up my old ARML papers.
62861
30.06.2017 03:51
Here's a more algebraic solution utilizing the Wythoff array.
Define $a_n = \lfloor n\phi \rfloor$ and $b_n = \lfloor n\phi^2 \rfloor$ for all positive integer $n$, where $\phi = \frac{1 + \sqrt{5}}{2}$ is the positive number satisfying $\phi^2 = \phi + 1$.
We claim that for every $n$, the sequence
\[a_n, b_n, a_{b_n}, b_{b_n}, a_{b_{b_n}}, b_{b_{b_n}}, \dots\]is of Fibonacci type. To check this, it suffices to show that $a_{b_n} = a_n + b_n$ and $b_{b_n} = a_{b_n} + b_n$ for all $n$; however, $b_n = \lfloor n\phi^2 \rfloor = \lfloor n(\phi + 1) \rfloor = a_n + n$ for all $n$, so the claim $b_{b_n} = a_{b_n} + b_n$ is true.
It suffices to verify that $a_{b_n} = a_n + b_n$ is true, which is equivalent to
\[a_n = a_{b_n} - b_n = \lfloor b_n\phi \rfloor - b_n = \lfloor b_n(\phi - 1) \rfloor = \left\lfloor \frac{b_n}{\phi} \right\rfloor,\]or
\[a_n = \left\lfloor \frac{a_n + n}{\phi} \right\rfloor.\]
Thus, now we must verify that if $m = \lfloor n\phi \rfloor$, then $m = \left\lfloor \frac{m + n}{\phi} \right\rfloor$.
Suppose that $m = \lfloor n\phi \rfloor$; then, $m < n\phi < m + 1$ (equality can't hold since $\phi$ is irrational). Now, we see that $m < \frac{m + n}{\phi}$ is equivalent to
\begin{eqnarray*}
m\phi & < & m + n\\
m\phi^2 & < & m\phi + n\phi\\
m & < & n\phi
\end{eqnarray*}which is true, and $m + 1 > \frac{m + n}{\phi}$ is equivalent to
\begin{eqnarray*}
(m + 1)\phi & > & m + n\\
m\phi^2 + \phi^2 & > & m\phi + n\phi\\
m + \phi^2 & > & n\phi,
\end{eqnarray*}which is true since $m + 1 > n\phi$ by assumption. Thus, the claim $a_{b_n} = a_n + b_n$ has been verified.
Now, draw an arrow from $a_n$ to $b_n$, as well as from $b_n$ to $a_{b_n}$, for each $n$. By the theory of Beatty sequences, every positive integer $n$ appears in exactly one of $\{a_k\}$ and $\{b_k\}$, so no two arrows point at the same number. In addition, each chain of arrows traces out a Fibonacci type sequence, and every positive integer is in exactly one chain. Finally, we note that since every arrow points from a smaller number to a bigger number, every chain has a number with no incoming arrows (which is the smallest number in the chain).
It suffices to verify that we actually have infinitely many Fibonacci type sequences in our partition; however, this is true since every Fibonacci type sequence has density $0$ (since they grow exponentially) while $\mathbb{N}$ has density $1$, so $\mathbb{N}$ can't be partitioned into finitely many Fibonacci type sequences.
msinghal
07.07.2017 08:26
Interesting variant: Can you partition all natural numbers except 2 into Fibonacci type sequences? (The analytic solution still works, but I wonder if there's a different solution that also still works) Here is the full analytic solution that Evan was referring to.
The full solution has a lot of technicalities to deal with, so it is somewhat hard to understand. The basic idea is that Fibonacci type sequences approach very close to a constant times $\phi^n$, so if sequences are sufficiently far apart "exponentially mod $\phi$", then there won't be any collisions near the end of the sequence. So it should intuitively be possible, for any starting $a_0$, to find an $a_1$ that works. You only need to check the small cases ($a_i$ for small $i$) for collisions. But basically, there are a lot of choices for $a_1$, and not all of them can lead to collisions for small $i$, so some choice of $a_1$ does work.
(Note: Indices of sequences start with 0 instead of 1.)
Let $\textstyle \phi=\frac{1+\sqrt 5}{2}, \overline\phi=\frac{1-\sqrt 5}{2}$ be the two roots of $x^2+x+1=0$. Note $\textstyle \overline\phi = \frac{-1}{\phi}$. Note also that $|\overline \phi| < 1$, so powers of $\overline \phi$ converge to 0.
We will construct the partition one sequence at a time, such that all sequences are increasing. Suppose we currently have a list of increasing Fibonacci type sequences $b^{(1)}, \ldots, b^{(\ell)}$ (with $b^{(j)} = (b_i^{(j)})_{i \ge 0}$), and suppose that $a_0$ is the smallest unused element. It suffices to show that there exists $a_1 > a_0$ such that the Fibonacci type sequence $(a_i)_{i \ge 0}$ starting with $a_0, a_1$ does not intersect any $b^{(j)}$.
Lemma 1: For a Fibonacci type sequence $(b_i)$, the terms are given by \[b_i = r\phi^i + s{\overline\phi}^i\]where $\textstyle r = \frac{b_1 - b_0 \overline \phi}{\sqrt 5}, s = \frac{-b_1 + \phi b_0}{\sqrt 5}$
Proof: Induction
So let $b_i^{(j)} = r_j \phi^i + s_j {\overline \phi}^i$.
For arbitrary $a_1$, let $\textstyle R = \frac{a_1 - a_0 \overline \phi}{\sqrt 5}, S = \frac{-a_1 + \phi a_0}{\sqrt 5}$.
Lemma 2: There exists $r_z$ such that there are no integer $i$ ($i$ can be negative) and index $j$ satisfying $\textstyle 1 < \frac{r_j}{r_z}\phi^i < \phi^{1/\ell}$
ProofFor a contradiction, assume not. Consider the directed graph on $\{1, \ldots, \ell\}$ with an edge from every $z$ to the $j$ satisfying the lemma statement. This graph must have a cycle, and multiplying all the inequalities in this cycle gives a contradiction.
Now, let $N$ be an arbitrary integer. Define $X=r_z\phi^y$ for some arbitrary but sufficiently large $y$, so that $N^3 \le X < \phi N^3$.
Lemma 3: For sufficiently large $N$, there exists a choice of $a_1$ such that $R \in (X + 1, \phi^{1/\ell}X - 1)$ and such that none of $a_1, \ldots, a_N$ belong to any $b^{(j)}$.
ProofCall a choice of $a_1$ "bad" if one of $a_1, \ldots, a_N$ does belong to some $b^{(j)}$.
Note that it is possible to pick an index $M$ such that $b^{(j)}_M > a_N$ for all valid choices of $a_1$. Moreover, since the sequences $b^{(j)}$ grow exponentially, we have $m = O(\log a_N) = O(\log(cN^3\phi^N)) = O(N)$ ($c$ is a constant).
Now, all bad sequences satisfy $a_n = b^{(j)}_m$ for some $1 \le n \le N, 1 \le j \le \ell, 1 \le m \le M$. Note that if $n,j,m$ are fixed, then this can have at most one solution in $a_1$, since $a_n$ is a linear function of $a_1$ and $b^{(j)}_m$ is constant in $a_1$. Thus the number of bad $a_1$ is at most the number of choices of $n,j,m$, which is $N\ell M = O(N^2)$. But the total number of choices of $a_1$ is $\Omega(N^3)$, so for sufficiently large $N$, there exists some choice of $a_1$ that is not bad.
Now fix $a_1$ so that Lemma 3 is satisfied.
Lemma 4: $|R-r_j\phi^x| > 1$ for all integers $x$ and indices $j$.
ProofSuppose not. Then, since $R \in (X + 1, \phi^{1/\ell}X - 1)$, we have $r_j\phi^x \in (X, \phi^{1/\ell}X)$. But since $X = r_z\phi^y$, this gives a contradiction to Lemma 2.
Now we claim that the Fibonacci type sequence $(a_i)_{i \ge 0}$ starting with $a_0, a_1$ does not intersect any $b^{(j)}$ when $N$ is sufficiently large. Suppose for a contradiction that $a_n = b_m^{(j)}$. By Lemma 3, $n > N$. Then, we have (in what follows, two occurrences of $\pm$ may have different sign choices):
\[R\phi^n + S{\overline \phi}^n = r_j\phi^m + s_j{\overline \phi}^m\]\[R\phi^n \pm \frac{S}{\phi^n} = r_j\phi^m \pm \frac{s_j}{\phi^m}\]\[R\phi^n - r_j\phi^m = \pm \frac{S}{\phi^n} \pm \frac{s_j}{\phi^m}\]\[R - r_j\phi^{m-n} = \pm \frac{S}{\phi^{2n}} \pm \frac{s_j}{\phi^{m+n}}\]\[\left|R - r_j\phi^{m-n}\right| = \left|\pm \frac{S}{\phi^{2n}} \pm \frac{s_j}{\phi^{m+n}}\right|\]\[\left|R - r_j\phi^{m-n}\right| \le \left|\frac{S}{\phi^{2n}}\right| + \left|\frac{s_j}{\phi^{m+n}}\right|\]
By Lemma 4:
\[1 < \left|\frac{S}{\phi^{2n}}\right| + \left|\frac{s_j}{\phi^{m+n}}\right|\]\[1 < \left|\frac{S}{\phi^{2N}}\right| + \left|\frac{s_j}{\phi^{n}}\right|\]
But $S = O(N^3)$, so for sufficiently large $N$, the RHS is less than 1, a contradiction.
Thus, if we have a list of sequences, we can always add a new sequence starting with the smallest unused element, so we are done.
McTeague
10.09.2017 19:36
Another idea for a construction (I think), similar to the ideas above but without using $\phi$: Given two Fibonacci-type sequences $(a_i)_i$ and $(b_i)_i$ with $a_i < b_1 < a_{i+1} < b_2 < a_{i+2}$ for some $i$, it follows inductively that the sequences "thread" between each other, i.e. $a_{j+i-1} < b_j < a_{j+i} < b_{j+1} < a_{j+i+1}$ for all $j$ (and some fixed $i$): \begin{align*} b_3 &= b_2 + b_1 > a_{i+1} + a_i = a_{i+2} \\ \Longrightarrow a_i &< b_1 < a_{i+1} < b_2 < a_{i+2} < b_3 \\ a_{i+3} &= a_{i+2} + a_{i+1} > b_2 + b_1 = b_3 \\ \Longrightarrow a_i &< b_1 < a_{i+1} < b_2 < a_{i+2} < b_3 < a_{i+3} \\ \vdots \end{align*} If we can successively add the first two elements of new Fibonacci-type sequences $A_n = (a_{n,i})_i$ that thread through all previously defined $A_k = (a_{k,i})_i$ then $\{A_i\}$ will partition $\mathbb{N}$. Start with $A_1$ given by $a_{1,1} = 1$ and $a_{1,2} = 2$ (the normal Fibonacci sequence). Having defined $A_1, \ldots, A_{k-1}$, define $A_k$ by setting $a_{k,1}$ to be the smallest positive integer not appearing in any of $A_1, \ldots, A_{k-1}$ and $a_{k,2}$ to be $2a_{k,1} - k$. We just have to show that $a_{k,2} = 2a_{k,1} - k$ is always available (i.e. not in $A_1, A_2, \ldots, A_{k-1}$) and that $\{a_{k,1}, a_{k,2}\}$ threads through each of $A_1, \ldots, A_{k-1}$. Use induction. $A_2 = \{4,6,10,\ldots\}$, which threads through $A_1$ (and is therefore disjoint from $A_1$). Assume $A_1, \ldots, A_{n-1}$ have been constructed in this way, with the properties that they are disjoint and thread through each other. Define $A_n = \{a_{n,1}, a_{n,2}, a_{n,3}, \ldots\}$ as outlined above. For $j \in [n-1]$, let $a_{j, i_j}$ be the largest element of $A_j$ appearing before $a_{n,1}$. $\bold{L1}$: $\{a_{1,i_1}, a_{2,i_2}, \ldots, a_{n-1, i_{n-1}}\} = \{a_{n,1} - (n-1), a_{n,1} - (n-2), \ldots, a_{n,1} - 1\}$.
If the claim were false, then there would exist two elements of some $A_{j_1}$ in $\{a_{n,1} - (n-1), a_{n,2} - (n-2), \ldots, a_{n,1} - 1\}$ (with $1 \le j_1 \le n-1$), so by the pigeonhole principle some sequence $A_{j_2}$ is such that $a_{j_2, i_{j_2}} < a_{n,1} - (n-1) \le a_{j_1, i_{j_1}-1} < a_{j_1, i_{j_1}} < a_{n,1} < a_{j_2, i_{j_2} + 1}$. So then $A_{j_1}$ and $A_{j_2}$ don't thread, contradicting the IH.
$\bold{L2}$: For each $j \in [n-1]$, $a_{j, i_j + 2} > a_{n,2}$.
From $\bold{L1}$, $a_{j,i_j} \ge a_{n,1} - n + 1$. By definition of $i_j$, $a_{j, i_j + 1} \ge a_{n,1} + 1$. Then:
\begin{align*}
a_{j,i_j + 2} &= a_{j, i_j + 1} + a_{j, i_j} \\
&\ge (a_{n,1} + 1) + a_{n,1} - n + 1\\
&= 2 a_{n,1} - n + 2 \\
&= a_{n,2} + 2 > a_{n,2} \\
\end{align*}
$\bold{L3(A)}$: For $j \in [n-1]$, if $i_j \ge 2$, then $a_{j, i_j + 1} < a_{n,2}$.
By definition of $i_j$, $a_{j, i_j} \le a_{n,1} - 1$. From $\bold{L1}$, $a_{j, i_j - 1} \le a_{n,1} - n$. Then:
\begin{align*}
a_{j,i_j + 1} &= a_{j, i_j} + a_{j, i_j - 1} \\
&\le (a_{n,1} - 1) + (a_{n,1} - n) \\
&= 2 a_{n,1} - n - 1 \\
&= a_{n,2} - 1 < a_{n,2} \\
\end{align*}
$\bold{L3(B)}$: For $j \in [n-1]$, if $i_j = 1$, then $a_{j, i_j+1} = a_{j, 2} < a_{n,2}$.
From the construction, it is clear that $a_{1,1} < a_{2,1} < a_{3,1} < \cdots$. If $a_{j, 1}$ is the largest element of $A_j$ appearing before $a_{n,1}$, then it follows that $a_{k, 1}$ is the largest for $j \le k < n$ and these are all larger than $a_{j,1}$ while being bounded above by $a_{n,1}$. Then $a_{j,1} \le a_{n,1} - (n-j)$ so:
\begin{align*}
a_{j,1} &\le a_{n,1} - (n-j) \\
&< a_{n,1} - \frac{n-j}{2} \\
\Longrightarrow 2 a_{j,1} &< 2 a_{n,1} - n + j \\
\Longrightarrow 2 a_{j,1} - j &< 2 a_{n,1} - n \\
\Longrightarrow a_{j,2} &< a_{n,2} \\
\end{align*}
From $\bold{L2}, \bold{L3(A)}, \bold{L3(B)}$ and the definitions of $i_j$ and $a_{n,1}$, for each $j \in [n-1]$ we have $a_{j, i_j} < a_{n,1} < a_{j, i_j +1} < a_{n,2} < a_{j, i_j + 2}$ so $A_n$ threads through each of $A_1, A_2, \ldots, A_{n-1}$ (and is therefore disjoint, so that $a_{n,2}$ was in fact available).
McTeague
10.09.2017 23:41
The above gives the following, which looks somewhat like the Wythoff array described earlier: \begin{align*} A_1 &= \{1, 2, 3, 5, 8, 13, 21, \ldots \} \\ A_2 &= \{4, 6, 10, 16, 26, 42, \ldots \} \\ A_3 &= \{7, 11, 18, 29, 47, 76, \ldots \} \\ A_4 &= \{9, 14, 23, 37, 60, 97, \ldots \} \\ A_5 &= \{12, 19, 31, 50, 81, 131 \ldots \} \\ A_6 &= \{15, 24, 39, 63, 102, 165, \ldots \} \\ A_7 &= \{17, 27, 44, 71, 115, 186, \ldots \} \\ \vdots \end{align*}
InCtrl
16.10.2017 06:47
I happened to stumble upon this exact problem in an old Komal! https://www.komal.hu/verseny/2000-09/mat.e.shtml (bottom of page)
me9hanics
21.03.2018 22:52
As guy above mentioned, this appeared in KöMaL. Here are the solutions for it, there are 3 different solutions: https://www.komal.hu/verseny/2000-09/A.e.shtml I really love the last solution.
Géza Kós
28.03.2018 09:05
misinnyo wrote: As guy above mentioned, this appeared in KöMaL. Here are the solutions for it, there are 3 different solutions: https://www.komal.hu/verseny/2000-09/A.e.shtml I really love the last solution. I like the second solution better. A sharper version was asked in a separate problem: Quote: $\textbf{B. 3429.}$ Let $q=\dfrac{1+\sqrt{5}}{2}$ and let $f:\mathbb{N}\to\mathbb{N}$ be a function satisfying $\big|f(n)-qn\big| < \dfrac{1}{q}$ for every $n\in\mathbb{N}$. Prove that $f(f(n))=f(n)+n$. KöMaL, 2001 January, https://www.komal.hu/verseny/2001-01/mat.e.shtml The value of $f(n)$ must be chosen from an interval longer than $1$, so, for infinitely many $n$, there are two candidates. Despite this freedom, the relation still holds true...
dgrozev
21.09.2019 09:39
An analytic approach, starting from scratch. Instead of $(a_n)_{n \ge 1}$, we denote a sequence as $a(n), n=0,1,\dots$. The idea is to add consecutively Fibonacci type sequences which do not intersect the previous ones. At any step we choose a natural number $n_0$ still uncovered by any sequence and find a sufficiently large $n_1>n_0$ such that the new Fibonacci type sequence (starting with $n_0,n_1,\dots$ ) doesn't intersect the previous sequences. The existence of $n_1$ is not a constructive type of proof. Very roughly speaking, we'll establish that when $n_1$ increases, the possible intersections would have been not so many, so, for some large enough $n_1$ , the corresponding sequence would be free of any other numbers already covered. Let $F(n), n\ge 0$ be the Fibonacci sequence $F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2), n\ge 2$. Any Fibonacci type sequence $a(n)$ can be represented as $$a(n)=a(1)F(n)+a(0)F(n-1),n\geq 1 $$Suppose, we've already chosen a finite family $A$ of Fibonacci type sequences, mutually disjoint (non-intersecting). Let $n_0\in \mathbb{N}$ be the smallest number not yet covered by any $a\in A$. We want to find a Fibonacci type sequence $h=\left( h(n),n\ge 0\right), h(0)=n_0$ which don't meet any $a\in A$. Suppose $h(m)=a(n), a\in A, m,n\in \mathbb{N}$. It can be written as $$a(1) F(n)+a(0)F(n-1)=h(1)F(m) + h(0) F(m-1)$$hence $$h(1)=a(1)\frac{F(n)}{F(m)}+a(0)\frac{F(n-1)}{F(m)}-n_0\frac{F(m-1)}{F(m)}.$$Consider the set $$H := \left \{a(1)\frac{F(n)}{F(m)}+a(0)\frac{F(n-1)}{F(m)}-n_0\frac{F(m-1)}{F(m)}: a\in A, n,m\in \mathbb{N} \right\}$$It's convenient to denote the elements of $H$ as $h(a,m,n), a\in A, m,n \in \mathbb{N}$. We want to establish $H$ doesn't contain all the natural numbers. The key observation is that $\frac{F(n)}{F(m)}\approx \phi^{n-m}$, where $\phi=\frac{1+\sqrt{5}}{2}$. We take sufficiently large $N$, such that $[N,\infty)$ doesn't contain any $h(a,m,n)$ with $m>n$. It's possible, since $A$ is finite and hence $\{a(0), a(1): a\in A\}$ is bounded. We have $$\frac{F(n)}{F(m)}=\frac{\phi^n-(-\phi)^{-n}}{\phi^m-(-\phi)^{-m}}=\frac{\phi^{n-m}-(-\phi)^{-n-m}}{1-(-\phi^{-2m})} $$It is easy to check $|\frac{x}{1-\varepsilon}-x|<1$ when $|x|<1/\varepsilon$. Hence $|x\cdot \frac{F(n)}{F(m)}-x\cdot \phi^{n-m}|<1$ when $n<2m$ and $0<x<\phi^m$. Now, we partition all the numbers $h(a,m,n)$ into three parts. Those with "small" $m$ are in the first part, the other ones for which $m$ is large and $n-m$ is not too large form the second part, and the rest of them with large $n-m$ are in the third part. Further, we choose large enough $M$ (but not "too large") such that $[N,M]$ is free of $h(a,m,n)$ that are in the third part. The number of elements of $H$ in the first partition, which hit the interval $[N,M]$, is finite and much less than $M-N$. There are infinite elements of the second partition lying inside $[N,M]$, but they are clustered around finite number of points, much less than the intervals' length. Here are the details. Let $m_0\in \mathbb{N}$ be large enough such that $\phi^{m_0}>\max\{n_0,a(0),a(1) : a\in A\}$ and $m_0>|A|$. We denote \begin{align*} H_1 &:=\{h(a,m,n): m\leq m_0,n\ge m \}\\ H_2 &:= \{h(a,m,n): m> m_0,n\ge m, n-m<m_0 \}\\ H_3 &:=H\setminus (H_1\cup H_2) \end{align*}Let $M:=\phi^{m_0}$. Obviously all $h\in H_3$ are larger than $M$. For each $m,m\leq m_0$, the number of those $h(a,m,n)$ in $H_1$ that are less than $M$ is at most $m_0\cdot |A|$, hence $$\left|H_1\cap [N,M]\right|\leq m_0^2|A|$$. For each $h(a,m,n)\in H_2$ we have $$\left|h(a,m,n)-\left( a(1)\phi^{n-m}+a(0)\phi^{n-1-m}-n_0\phi^{-1} \right) \right|<3$$Denote $$ H'_2 := \{ a(1)\phi^{n-m}+a(0)\phi^{n-1-m}-n_0\phi^{-1}:h(a,m,n)\in H_2\}$$Clearly $|H'_2|\leq m_0|A|$ and each point in $H_2$ is at distance at most $3$ to some point in $H'_2$. To recap. All points in $H$ that are inside $[N,M]$ lie in the union of intervals of length $6$ centered at the points in $H_1\cup H'_2$ which number is at most $m_0^2|A|+m_0|A|<2m_0^2|A|<2m_0^3$. The total length of those intervals is at most $12m_0^3$, hence the total length of the complement $H^*$ of those intervals to $[N,M]$ is at least $M-N-12m_0^3=\phi^{m_0}-12m_0^3-N$. That complement $H^*$ is composed of at most $12m_0^3+1$ intervals. Hence the average length of intervals in $H^*$ is at least $I_{\text{avg}}=\frac{\phi^{m_0}-12m_0^3-N}{12m_0^3+1}.$ Now, if we choose $m_0$ large enough, we can make $I_{\text{avg}}$ as large as we want, for example bigger than $1$. It means there is an interval with length more than $1$ which doesn't contain points in $H$, hence there is a natural number $n_1$ outside $H$. As shown above, the Fibonacci type sequence $h(n), h(0)=n_0,h(1)=n_1$ does not meet any other sequence $\left(a(n)\right)_{n\ge 0}, a\in A$.
mathleticguyyy
26.10.2020 19:21
utterly incomprehensible solution, redacted.
GeronimoStilton
06.01.2021 02:14
Yes. Let $f$ be a solution to IMO 1993/5. Partition $\mathbb{N}$ into chains $n\mapsto f(n)\mapsto f^2(n)\mapsto\cdots$ for which $f^{-1}(n)=\emptyset$. Remark that these chains must include all elements of $\mathbb{N}$. Then each chain is a Fibonacci type sequence by the conditions on $f$, so we are done.
Plops
07.09.2021 22:38
First, ignore the above definition of Fibonacci sequences (I'll give a new term later). Lemma: Given the Fibonacci sequence $F_0=1, F_1=2$, and $F_{n+2}=F_{n+1}+F_n$, $F_{n+2} -2=\sum_{i=0}^{n} F_n$ for $n \geq 0$. Proof: $1=F_2-2=F_0$. Assume the result is true for $0 \leq n \leq m$. Then $$F_{m+2}-2=F_{m+1}-2+F_m=\sum_{i=0}^{m-1} F_i+F_m=\sum_{i=0}^{m} F_m$$ Claim: Call a summation good if each summand is a Fibonacci number, no two of which are consecutive. Then every natural number can be uniquely represented as a good summation. Proof: Assume every natural number less than $F_n$ can be represented as a good summation and consider a number $m$ s.t. $F_n \leq m<F_{n+1}$. Then $m-F_n<F_{n-1}$ can be represented as a good summation $\sum_{i}^{}F_i$, the greatest summand less than $F_{n-1}$, guaranteeing that the sum $m=\sum_{i}^{}F_i+F_n$ has no consecutive Fibonacci numbers. Assume FTSOC that there exists two distinct good summations equal to each other; i.e., $$\sum_{i=1}^{m} F_{a_i}=\sum_{j=1}^{n} F_{b_j}$$where WLOG $a_m>a_{m-1}> \ldots>a_1 \geq 0$, $b_n>b_{n-1}\ldots>b_1 \geq 0$, $a_m>b_n$, and $a_{m-1} \geq a_m-2k+1$ Then, from the lemma, $a_m=b_n+1$ and subtracting $b_n$ from both sides of the equation, we get $$\sum_{i=1}^{m-1}F_{a_i}+F_{a_m-2}=\sum_{j=1}^{n-1} F_{b_j}$$ However, note that $b_{n-1} \leq b_n-2\leq a_m-3$ so we can subtract both sides of the equation by $F_{b_{n-1}}$. Repeating this operation, we either get that $0$ can be representable as the sum of a positive number of Fibonacci numbers, or if we do this operation $k$ times, we get that $\sum_{i=1}^{m-2}F_{a_i}+F_{a_{m-1}} \leq \sum_{j=1}^{n-k} F_{b_i}<F_{a_m-2k+1}-2$ by the lemma, both statements being contradictions. Call a sequence $\{a_i \}_{i \geq 0}$ FiBonaCCi if $a_{n+2}=a_{n+1}+a_n$ for $n\geq 0$. By our claim, the infinite set of sequences of the form $\{F_i+F_{i+a_1}+\ldots+F_{i+a_k}\}_{i=0}^{\infty}$ where $k \geq 0$ and $a_1 \leq a_2-2 \leq a_3-4 \leq \ldots \leq a_k-2k+2$ uniquely represent each natural number, and each of these sequences is obviously FiBonaCCi since each summand is a Fibonacci number.
megarnie
22.01.2022 16:11
Answer is $\boxed{\text{yes}}$. We claim that the function $f(n)=\left\lfloor \varphi n+\frac{1}{2}\right\rfloor$ is strictly increasing and it satisfies $f(1)=2$ and $f(f(n))=f(n)+n$ for all positive integers $n$ (IMO 1993 #5). First we will show that the function is strictly increasing. This follows as $\varphi>1$. It suffices to show that $f(f(n))=f(n)+n$. We have\begin{align*} f(f(n))-f(n)-n= & \left\lfloor \varphi \left \lfloor \varphi n+\frac{1}{2}\right \rfloor +\frac{1}{2}-f(n)-n\right\rfloor \\ f(f(n))-f(n)-n= & \left \lfloor \varphi n + n + \frac{\varphi +1}{2}-\varphi\left\{\varphi n+\frac{1}{2}\right\}\right \rfloor -f(n)-n \\ f(f(n))-f(n)-n= & \left \lfloor \varphi n + \frac{\varphi +1}{2}-\varphi\left\{\varphi n+\frac{1}{2}\right\}\right \rfloor - \left\lfloor \varphi n +\frac{1}{2}\right\rfloor \end{align*}First we will maximize $f(f(n))-f(n)-n$. Note that $f(f(n))-f(n)-n\le\left\lfloor \varphi n +\frac{\varphi +1}{2}\right\rfloor - \left\lfloor \varphi n +\frac{1}{2}\right\rfloor \le 1$. Now we will minimize $f(f(n))-f(n)-n$. Note that $f(f(n))-f(n)-n\ge \left\lfloor \varphi n+\frac{1-\varphi}{2}\right\rfloor -\left\lfloor \varphi n+\frac{1}{2}\right\rfloor\ge -1$. Thus, $f(f(n))-f(n)-n\in \{-1,0,1\}$ since it's an integer. Suppose $f(f(n))-f(n)-n=-1$ or $1$. Then $\varphi n +\frac{1}{2}$ is an integer, a contradiction. Thus, $f(f(n))-f(n)-n=0\implies f(f(n))=f(n)+n$. $\blacksquare$ Now we consider the infinite chains $n\to f(n)\to f^2(n)\ldots$, where $f^{-1}(n)=\emptyset$. Partition $\mathbb{N}$ into these disjoint chains. It's clear that all positive integers are in one of these chains. Since $f^{k+2}(n)=f^{k+1}(n)+f^k(n)$, each chain is fibonacci type. It suffices to show that there can't be finitely many such chains. Suppose there were. Then there must be finitely many $n$ so that $f^{-1}(n)=\emptyset$. Let $m$ be the largest such positive integer. Now let $f(k)=m+1$. Then we have $f(k+1)=m+2, f(k+2)=m+3, \ldots$. So for all $n\ge k$, $f(n)=n+c$ for some constant $c$. So for all $n\ge k$, $f(n+c)=2n+c\implies n+2c=2n+c\implies n=c$, a contradiction. $\blacksquare$
GrantStar
28.09.2023 21:40
Yes. Let $A=\{\lfloor \phi n\rfloor\}_{n\geq 1}$ and $B=\{\lfloor \phi^2 n\rfloor\}_{n\geq 1}$. Then, I claim such a partition is acheived by the sequences $X_n$ with starting values of $A_N,B_N$ for $N\in A$. First, observe the following: $A$ and $B$ parition the integers by Beatty as $\frac {1}{\phi}+\frac{1}{\phi^2}=1$. $B_n-A_n=n$ for all $n$ Now, we present a few claims. Claim: $A_n+B_n=A_{B_n}$. That is, $\lfloor \phi n\rfloor+\lfloor \phi^2 n\rfloor=\lfloor \phi\lfloor \phi^2 n\rfloor \rfloor$ Proof. Essentially rewrite the right hand side as $\lfloor \phi n +\phi\lfloor \phi n\rfloor \rfloor$. Now let $x=\phi n$. We have the claim rewrites to $\phi x -x +2\lfloor x \rfloor =\lfloor x +\phi \lfloor x\rfloor \rfloor$ or also $\phi x +x-2\{x\}=\lfloor x+\phi x -\phi\{x\}\rfloor$. This is true as the right side not under the floor is strictly larger than the left side but also at most $2-\phi <1$ larger than it. $\blacksquare$ Claim: $B_n+A_{B_n}=B_{B_{n}}$. That is, $\lfloor \phi^2 n\rfloor+\lfloor \phi\lfloor \phi^2 n\rfloor \rfloor=\lfloor \phi^2\lfloor \phi^2 n\rfloor \rfloor$ Proof. This is trivial as \[\lfloor \phi^2\lfloor \phi^2 n\rfloor \rfloor r=\lfloor \lfloor \phi^2 n\rfloor + \phi \lfloor \phi^2n\rfloor \rfloor =\lfloor \phi^2 n\rfloor+\lfloor \phi\lfloor \phi^2 n\rfloor \rfloor\]$\blacksquare$ Notice that these claims mean such a sequence $X_N$ goes like $\{A_N,B_N,A_{B_{N}},B_{B_{N}},\dots\}$. In particular, it will take the n'th value in $A$ and $B$ for $n=N,B_N,B_{B_N},\dots$. This finishes since By construction, no two terms appear in the same sequence Each $A$ term appears in the sequence. If the term is $A_i$ then if $i$ is in $A$ it is the first number in it's sequence. If not, then let $B_k=i$ so $B_k,A_k$ would share a sequence with $A_i$ and simply induct. Each $B$ is in a sequence with it's corresponding $A$ $\blacksquare$ Here is a table to visualize the sequences better. \[\begin{array}{c | c | c } \text{n} & \text{A} & \text{B} \\ \hline 1 & 1 & 2 \\ 2 & 3 & 5 \\ 3 & 4 & 7 \\ 4 & 6 & 10 \\ 5 & 8 & 13 \\ 6 & 9 & 15 \\ 7 & 11 & 18 \\ 8 & 12 & 20 \\ 9 & 14 & 23 \end{array} \]Remark: How did this make the test :skull: Remark: The sequences can be visualized as follows. Take the first $X$ sequence and highlight the row numbers it takes in the table. Then, the first row on the second $X$ sequence is the first non highlighted row. The third $X$ sequence starts at the new earliest unhighlighted sequence and so on
signifance
03.10.2023 02:29
The problem follows from the following lemma by partitioning N into groups $(n,f(n),f(f(n)),...)\forall n:f^{-1}(n)=\emptyset$, where $f:\mathbb N\to\mathbb N:f(x)<f(y)\forall x<y,f(1)=2,f(f(n))=f(n)+n$. Indeed, testing the first few terms, we find that $f^k(x)=F_{k+1}$ by induction and we claim that $f(n)=\lfloor\varphi x+\frac12\rfloor$ works. Manually computing (with details omitted) gives $$|\left(f(f(n))\right)-\left(f(n)+n\right)|=|\left(\varphi^2n+\frac12\varphi+\frac12-\varphi\left\{\varphi n+\frac12\right\}-\left\{\varphi^2n+\frac12\varphi+\frac12-\varphi\left\{\varphi n+\frac12\right\}\right\}\right)$$$$-\left(\varphi^2n+\frac12-\left\{\varphi n+\frac12\right\}\right)|=|\frac12\varphi-(\varphi-1)\left\{\varphi n+\frac12\right\}-\left\{\varphi^2n+\frac12\varphi+\frac12-\varphi\left\{\varphi n+\frac12\right\}\right\}|<\frac12\varphi<1.$$Since this is presumed to be an integer, it's equal to 0, so it indeed satisfies the lemma, as desired. It follows that our partitioning consists only of Fibonacci numbers, so it works! note: actually i was too lazy to manually type up f(f(n))-f(n)-n , so i stole this part from mr. botted immaculator from the 93imo5 thread; apparently doing your work on paper is not easy to writeup on latex, so basically i just searched around in that thread for this lemma (Actually the motivation for this construction follows from the genfunc derivation of fibonacci eq. that says $F_n$ is the closest integer to $\frac{1}{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^n$.)
Number1048576
04.03.2024 00:08
We claim that the answer is yes.
First, note that given two fibonacci-type sequences $(a_n)$ and $(b_n)$, if there is an integer $m$ such that $b_m < a_1 < b_{m+1} < a_2 < b_{m+2}$, the two sequences are disjoint.
Then, let one of the sequences $F_n$ be the fibonacci sequence. Then we will provide an inductive construction (where we induct on $n$) to get all of the numbers in between $F_{n}$ and $F_{n+1}$, so that if $a_j$ and $b_i$ are any numbers in between $F_n$ and $F_{n+1}$ and
$a_j < b_i$, then $a_{j+1}$ and $b_{i+1}$ are in between $F_{n+1}$ and $F_{n+2}$ and $a_{j+1} < b_{i+1}$.
Base: let the sequence containing $4$ be $4,7,\cdots$. Then the above condition holds.
Step:
Let $S$ be the set of numbers in between $F_{n}$ and $F_{n+1}$ which are already in a sequence. Note that for any $a_i$, $b_j$ $\in S$ with $a_i < b_j$, then $b_{j+1} - a_{i+1} = b_j + b_{j-1} - a_i - a_{i-1} > b_j - a_i$ as $b_{j-1} > a_{i-1}$ (as otherwise $a_i > b_j$).
Then, take any two consecutive numbers in $S$ $a_i < b_j$.
Define new sequences $(S_{x_n})$ as follows:
$S_{x_1} = b_j - x$, $S_{x_2} = b_{j+1} - x$ for every $x$ such that $b_j - a_i > x$ (as $b_{j+1} - a_{i+1} > b_j - a_i$ we won't run out of $x$s).
Then the conditions of the induction still hold for these new sequences, as $S_{x_1} < S_{y_1} \implies S_{y_1} < F_{n+1} < S_{x_2} < S_{y_2}$ by construction, but $S_{x_3} > F_{n+2} > S_{y_2}$, so $S_{x_i} < S_{y_i} < S_{x_{i+1}} < S_{y_{i+1}}$ for each $i$, and if $c_i$ isn't in between $a_i$ and $b_j$ then by construction
$S_{x_1} < c_i \implies c_i < F_{n+1} < S_{x_2} < b_{j+1} < c_{i+1} < F_{n+2} < S_{x_3}$, and similarly for if $S_{x_1} > c_i$, so we are done.
Could someone check this, as it seems dodgy for some reason.
HamstPan38825
01.01.2025 23:00
This problem has no real strategy to it -- just force it to work and it works. The answer is yes. We will construct two sequences $\{a_n\}$ and $\{b_n\}$, such that $a_n < b_n$ for each $n$ (just to make my life easier) such that the Fibonacci-type sequences $S_n$ starting with $a_n$ and $b_n$ in that order will partition $\mathbb N$, by induction. For our base case, set $a_1 = 1$ and $b_1 = 2$. Now, for the inductive step, assume we have constructed some nonoverlapping Fibonacci-type sequences $S_1, S_2, \dots, S_{n-1}$. Fix $a_n = a$ to be the smallest positive integer not present in any of $S_1, \dots, S_{n-1}$. The crux of the construction lies in finding an appropriate $b_n$. To do so, fix a large $N$ to be determined and consider all the $b \in (a_n, N]$ such that the Fibonacci-type sequence $S$, which we denote by $(a, b)$, coincides with some previous sequence $S_i$. Claim: For each sequence $S_i$, there exist at most $\left(\log_{1.5} N\right)^2$ positive integers $b \in (a_n, N)$ such that $(a, b)$ shares a term with $S_i$. Proof: Without loss of generality fix $S = S_i$ so that I don't have to do annoying indexing. If $(a, b)$ shares a term with $S = \{x_i\}$, it follows that there exists an index $k$ and a positive integer $n$ such that $aF_n + bF_{n+1} = x_k F_n + x_{k+1}F_{n+1}$, which can be rearranged to \[\frac{x_k - a}{b-x_{k+1}} = \frac{F_{n+1}}{F_n}.\]Claim: [a little housekeeping] We can pick $b$ such that we cannot have both $a - x_k > 0$ and $x_{k+1} - b > 0$ simultaneously. Proof: If $x_k < a$, then $x_{k+1} < 2a$ by definition of a Fibonacci-type sequence. So just pick $b > 2a$. (This is fine because $a$ is fixed already.) $\blacksquare$ So it follows that we must have $a < x_k < x_{k+1} \leq b$. Notice that there are at most $\log_{1.5} N$ indices $k$ such that $x_k < N$ as the consecutive ratio $\frac{x_{i+1}}{x_i} \geq 1.5$ always. Furthermore, for each index $k$, as $F_n$ and $F_{n+1}$ are relatively prime, we must have $x_k - a \geq F_{n+1}$, so $F_{n+1} \leq x_k - a < N$. Once again, there are at most $\log_{1.5} N$ such indices $n$ for each index $k$. Given $k$ and $n$, $b$ is fixed (if it exists), so it follows that there are at most $\left(\log_{1.5} N \right)^2$ such positive integers $b$, as needed. $\blacksquare$ (Technically there is the $b = x_k$ case, but that only contributes $\log_{1.5} N$ more, so it doesn't matter.) By the union bound, it follows that there are at most $(n-1)\left(\log_{1.5} N\right)^2$ integers $b \in (a, N)$ that coincide with one of the $n-1$ sequences $S_i$. But for sufficiently large $N$ for which $N > a+n\left(\log_{1.5} N\right)^2$, there will exist a desired $b$. Thus we can construct a sequence $S_n = (a_n, b_n)$ that does not coincide with any previous sequence, completing the inductive step. Now, notice that every integer must appear in one $S_i$ by our definition of $a$, and no two sequences coincide by construction. It follows that $\mathbb N = \bigcup_{i=1}^\infty S_i$, as needed. Remark: This is honestly a pretty natural problem to think about. In fact, I independently posed some variant of it to myself more than four years ago.