Flee Jumping on Number Line

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

utkarshgupta

2280 posts

utkarshgupta

#1 h Dec 11, 2015, 3:59 PM • 2 Y

Y by Adventure10, Mango247

An immortal flea jumps on whole points of the number line, beginning with $0$ . The length of the first jump is $3$ , the second $5$ , the third $9$ , and so on. The length of $k^{\text{th}}$ jump is equal to $2^k + 1$ . The flea decides whether to jump left or right on its own. Is it possible that sooner or later the flee will have been on every natural point, perhaps having visited some of the points more than once?

This post has been edited 2 times. Last edited by djmathman, Apr 15, 2016, 5:59 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dgrozev

2459 posts

dgrozev

#2 h Dec 19, 2015, 8:28 AM • 5 Y

Y by Pluto1708, Assassino9931, Adventure10, Mango247, kiyoras_2001

It's enough to prove that being at the point $x$ at its $k$ -th move, the flea can make some jumps and after that to reach $x\pm 1$ .
Indeed, let it jumps $m+1$ times to the right and the last $m+2$ -th jump be to the left. Thus it would be at the point:
$x+(2^{k}+1)+(2^{k+1}+1)+\dots +(2^{k+m}+1) - (2^{k+m+1}+1)=x-2^{k}+m.$ Now, choosing $m=2^k\pm 1$ , we prove the claim.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kreegyt

10 posts

kreegyt

#3 h Apr 22, 2016, 10:16 AM • 2 Y

Y by Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#4 h Nov 10, 2019, 6:22 PM • 1 Y

Y by Adventure10

I claim it is possible.

Lemma: Given any $k\in \mathbb{N}$ , there exists some $n>k$ such that
$(2^k+1)+(2^{k+1}+1)+\cdots+(2^{n-1}+1) - (2^n+1) = 1.$ Proof: Let $f(n)$ be the above expression. We know $f(k+1) = (2^k+1)-(2^{k+1}+1) = -2^k$ . We claim $f(n+1)-f(n)=1$ for all $n>k$ . Indeed,
$\begin{align*} f(n+1)&= (2^k+1)+\cdots+(2^{n-1}+1)+(2^n+1) - (2^{n+1}-1),\\ f(n)&=(2^k+1)+\cdots+(2^{n-1}+1) - (2^n+1) \\ \implies f(n+1)-f(n) &= (2^n+1)-(2^{n-1}-1) + (2^n+1) = 1. \end{align*}$ Therefore, $f(k+1 + 2^k+1)=1$ , so setting $n=2^k+k+2$ works. $\blacksquare$

Now it is easy to see by induction on $n\in \mathbb{N}$ that we can reach all $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathlogician

1051 posts

mathlogician

#5 h Oct 20, 2020, 2:32 AM • 1 Y

Y by Chiaquinha

Note that this following claim essentially implies the problem.

Claim: For any $n$ , we can go from $n$ to $n+1$ in a finite number of moves.

Proof: Suppose that the move made from $n$ is the $k$ th total move Kelvin has made. Now for each $k \leq i \leq 2^k + k - 1$ , send Kelvin $2^i +1$ to the left, and finally send Kelvin $2^{2^k+k}+1$ to the right. I claim that this shifts Kelvin's position right by exactly $1$ . Indeed, one can check that $\sum _{i = k} ^{2^k+k-1} 2^i + 1 = \sum _{i=k} ^ {2^k+k-1} 2^i + 2^k = (2^{2^k+k} - 1) - (2^k-1) + 2^k = 2^{2^k+k}$ which is exactly $1$ less than $2^{2^k+k} + 1$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Pluto1708

1107 posts

Pluto1708

#6 h Jan 8, 2021, 11:19 AM

Y by

utkarshgupta wrote:

An immortal flea jumps on whole points of the number line, beginning with $0$ . The length of the first jump is $3$ , the second $5$ , the third $9$ , and so on. The length of $k^{\text{th}}$ jump is equal to $2^k + 1$ . The flea decides whether to jump left or right on its own. Is it possible that sooner or later the flee will have been on every natural point, perhaps having visited some of the points more than once?

Plain Old Russian Beauty!
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

nprime06

187 posts

nprime06

#7 h Jan 11, 2021, 1:13 AM • 1 Y

Y by fukano_2

Solution with fukano_2.

We prove the statement with induction, with the base case (jumping on $n=0$ ) is trivial.

Claim. if we achieve $n$ , we can get to $n+1$ .
Proof. We show that there exists a choice of $b$ such that $(2^a+1)+(2^{a+1}+1)+\cdots +(2^{b-1}+1)-(2^b+1)=1,$ which obviously proves the claim. Simply select $b=2^a+a+2$ ; the sum evaluates to
$\begin{align*} S&=(2^a+1)+(2^{a+1}+1)+\cdots +(2^{b-1}+1)-(2^b+1)\\&= 2^a(2^0+2^1+\cdots + 2^{b-a-1})+(b-a)-(2^b+1)\\&= 2^a(2^{b-a}-1)+(b-a)-(2^b+1)=2^b-2^a+b-a-2^b-1\\&=b-2^a-a-1=2^a+a+2-2^a-a-1=1, \end{align*}$ as needed.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Enderman_1010

1786 posts

Enderman_1010

#8 h Jan 11, 2021, 1:17 AM

Y by

utkarshgupta wrote:

An immortal flea jumps on whole points of the number line, beginning with $0$ . The length of the first jump is $3$ , the second $5$ , the third $9$ , and so on. The length of $k^{\text{th}}$ jump is equal to $2^k + 1$ . The flea decides whether to jump left or right on its own. Is it possible that sooner or later the flee will have been on every natural point, perhaps having visited some of the points more than once?

You spelled "flea" as "flee" on the title and the OP

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MrOreoJuice

594 posts

MrOreoJuice

#10 h Aug 10, 2021, 3:56 PM • 1 Y

Y by SatisfiedMagma

The answer is yes. Assume it is possible to reach $n$ at the $k^{\text{th}}$ jump. Now assume the flea jumps to the right till the next $r$ jumps.
Position after $r$ jumps would be
$n + 2^{k+1} + 1 + \cdots + 2^{k+r} + 1 = n + 2^{k+r+1} - 2^{k+1} + r$ Again assume at the $k+r+1^{\text{th}}$ jump the flea jumps to it's left. So then position at the $k+r+1^{\text{th}}$ jump will be $=n + 2^{k+r+1} - 2^{k+1} + r - 2^{k+r+1} - 1 = n - 2^{k+1} + r - 1$ Setting $r = 2^{k+1} + 2$ we get that the position at the $k+r+1^{\text{th}}$ jump would be $n+1$ . This shows it is possible to reach from the number $n$ to the number $n+1$ . To show that it is possible to reach $1$ , jump left $2$ times and at the $3^{\text{rd}}$ jump, jump to the right.

Edit: Did I misread the problem? (If so, I might edit it later).

This post has been edited 2 times. Last edited by MrOreoJuice, Dec 4, 2021, 3:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rafaello

1079 posts

rafaello

#11 h Sep 30, 2021, 1:36 PM

Y by

Claim. There exists $n$ such that the following is true for any $x$ ,
$(2^{n+1}+1)-(2^{n}+1)-\ldots-(2^{x}+1)=1.$ Proof. Indeed, this is equivalent to $2^{x}+x=n+1.$ $\square$

Now, define $\{a_n\}$ as $a_{i+1}=2^{a_i}+a_i+1$ and $a_1=1$ . Now in $k$ th jump if $k=a_i-1$ the flea moves right and otherwise it moves left. We achieve every natural, done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheProblemIsSolved

20 posts

TheProblemIsSolved

#12 h Oct 6, 2021, 7:25 AM

Y by

We claim that it is possible to reach every positive integer. Suppose we want to reach a positive integer $n$ . We go $n+3$ steps to the right and $1$ step to the left.
The position of the flea is,
$\begin{align*} & \left(\sum_{i=1}^{n+3}2^i + 1\right) - 2^{n+4} - 1 \\ =&\ 2^{n+4} - 2 + n+3 - 2^{n+4} - 1\\ =&\ n \end{align*}$ edit: oops misread the problem

This post has been edited 1 time. Last edited by TheProblemIsSolved, Oct 6, 2021, 8:02 AM
Reason: sadge

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikemath40

500 posts

ilikemath40

#14 h Dec 27, 2021, 2:57 PM

Y by

Any OTISer? :pilot:

We will claim that it is possible that Kelvin reaches all the positive integer coordinates at least once.

First, lets define a sequence where $a_1=1$ and $\forall n\ge 2, a_n=a_{n-1}+2^{a_{n-1}}+1$ . The first few terms of this sequence are $1, 4, 21$ . Then lets now make some sets of numbers.

$\begin{align*} &\{ -(2^1+1), -(2^2+1), 2^3+1 \} \\ &\{ -(2^4+1), -(2^5+1), \dots, -(2^{19}+1), 2^{20}+1 \} \\ \vdots \\ &\{ -(2^{a_k}+1), -(2^{a_k+1}+1), \dots, -(2^{a_{k+1}-2}+1), 2^{a_{k+1}-1}+1 \} \end{align*}$
Now we can see that the sum of all the numbers in each of these sets is equal to 1. Thus if we add together all of these sets we will reach every natural number. $\blacksquare$

This post has been edited 1 time. Last edited by ilikemath40, Dec 27, 2021, 2:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mogmog8

1080 posts

Mogmog8

#15 h Nov 19, 2022, 4:37 PM • 3 Y

Y by centslordm, Mango247, Mango247

Define $S_{k,\ell}=-2^{\ell+k+1}-1+\sum_{i=\ell}^{\ell+k}(2^i+1)=-2^{\ell+k+1}-1+(k+1)+2^{\ell}(2^{k+1}-1)=k-2^{\ell}.$ If we choose $k=2^{\ell}+1,$ this sum becomes $1.$ Hence, choosing $(k_1,\ell_1)=(1,2^1+1)$ and $(k_i,\ell_i)=(\ell_{i-1}+k_{i-1}+2,2^{\ell_{i-1}+k_{i-1}+2}-1)$ for $i\ge 2,$ we obtain disjoint sums that all have sum one. We claim by induction that the flea can visit all natural numbers. For the base case, the flea can get to one by $S_{k_1,\ell_1}.$ For the inductive step, from $m,$ the flea can use $S_{k_{m+1},\ell_{m+1}}$ to get to $m+1.$ $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Msn05

39 posts

Msn05

#16 h Dec 1, 2022, 5:57 PM

Y by

The answer is yes.

We define $a_k$ the number of steps needed to go from $0$ to $k$ . Note that
$1=-(2^1+1)-(2^2+1)+(2^3+1)$
$2=1-(2^4+1)-(2^5+1)-\cdots-(2^{4+2^4-1}+1)+(2^{4+2^4}+1)$
$3=2-(2^{4+2^4+1}+1)-(2^{4+2^4+2}+1)-\cdots-(2^{4+2^4+2^{4+2^4}-1}+1)+(2^{4+2^4+2^{4+2^4}}+1)$
$k=(k-1)-(2^{a_{k-1}+1}+1)-(2^{a_{k-1}+2}+1)-\cdots-(2^{a_{k-1}+2^{a_{k-1}-1}}+1)+(2^{a_{k-1}+2^{a_{k-1}}}+1)$
$k+1=k-(2^{a_{k}+1}+1)-(2^{a_{k}+2}+1)-\cdots-(2^{a_{k}+2^{a_{k}-1}}+1)+(2^{a_{k}+2^{a_{k}}}+1)$
So by induction we get that
$n=(n-1)-(2^{a_{n-1}+1}+1)-(2^{a_{n-1}+2}+1)-\cdots-(2^{a_{n-1}+2^{a_{n-1}-1}}+1)+(2^{a_{n-1}+2^{a_{n-1}}}+1)$
Thus the flea can visit all points with positive integer coordinates.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#17 h Dec 17, 2022, 2:14 AM

Y by

It is possible. It suffices to show that from any point $n$ on the number line, Kelvin can get to $n+1$ .

Suppose that Kelvin has already jumped $k$ times. Then, we may jump the next $2^{k+1}+1$ jumps in the negative direction, and then the next jump in the positive direction: this yields a net difference of $-\left(2^{k+1} + 2^{k+2} + \cdots + 2^{k+2^{k+1}} + 2^{k+1}\right) + 2^{k+1+2^{k+1}} + 1 = 1,$ which means that Kelvin can reach $n+1$ , as required.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JAnatolGT_00

559 posts

JAnatolGT_00

#18 h Dec 23, 2022, 8:54 PM • 3 Y

Y by Mango247, Mango247, Mango247

We claim that the answer is positive. It's suffice to prove, that from point $n$ flea can jump to $n+1;$ if flea reached point $n$ on $k-$ th move, let it makes $2^{k+1}$ jumps to left and one jump to right - it works, since the new coordinate is $n+2^{k+2^{k+1}+1}+1-\sum_{i=1}^{2^{k+1}} (2^{k+i}+1)=n+1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4175 posts

john0512

#19 h Mar 29, 2023, 11:50 PM

Y by

Lemma 1: For any positive integer $n$ , $(2^{2^n+n}+1)-((2^n+1)+(2^{n+1}+1)\cdots +(2^{2^n+n-1}+1))=1.$ This is because $(2^{2^n+n}+1)-((2^n+1)+(2^{n+1}+1)\cdots +(2^{2^n+n-1}+1))$ $=2^{2^n+n}-2^{2^n+n-1}\cdots -2^n-(2^n-1)=1.$
Now, define the sequence $a_n$ recursively as $a_1=1,a_n=2^{a_{n-1}}+a_{n-1}+1,$ so for example the first 4 terms are $1,4,21,2097174.$

Now, by Lemma 1, observe that $(2^{a_2-1}+1)-\sum_{i=a_1}^{a_2-2} 2^i+1=1$ $(2^{a_3-1}+1)-\sum_{i=a_2}^{a_3-2} 2^i+1=1,$ and so on so in general $(2^{a_{n+1}-1}+1)-\sum_{i=a_n}^{a_{n+1}-2} 2^i+1=1,$ so we can employ an algorithm where we move forwards if the move number is of the form $a_n-1$ for some $n$ , and move backwards otherwise. This allows us to reach $n-1$ on move $a_n-1$ due to the prefix sums, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Danielzh

480 posts

Danielzh

#20 h May 11, 2023, 12:11 AM

Y by

We claim that it is possible.

The flea can simply jump right for the first $k$ moves, and then jump left on the $k+1$ th move. Representing the jumps as numerical values, we can write the expression as

$\begin{align*} \sum _{n = 1} ^{k} (2^n + 1) - (2^{k+1}+1) = k + 2^{k+1} - 1 - 2^{k+1} = k - 1 \end{align*}$
Since $1 \le k \le + \infty$ , we are done. $\blacksquare{}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

gracemoon124

872 posts

gracemoon124

#21 h Aug 3, 2023, 10:12 PM

Y by

Notice how $2^{n+1}-1=2^n+2^{n-1}+\dots +2+1$ , so we can write
$2^{n+1}+1=(2^n+1)+(2^{n-1}+1)+\dots (2+1)-(n-3).$ Rearranging, we get
$(2^n+1)+(2^{n-1}+1)+\dots +(2+1)-(2^{n+1}+1)=n-3$ so take $n=k+1$ , where $k$ is the value we want to get. Therefore, it is possible.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HoRI_DA_GRe8

587 posts

HoRI_DA_GRe8

#22 h Nov 15, 2023, 2:10 PM

Y by

$2^k+1+2^{k+1}+1+\cdots+2^{k+2^k-1}+1-(2^{k+2^k}+1)=2^k(2^{2^k}-1)+2^k-(2^{k+2^k}+1)=-1$
So randomly move to a very very big number,then come back with this algorithm,then repeat $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pinkpig

3761 posts

pinkpig

#23 h Nov 23, 2023, 12:00 AM

Y by

WLOG, assume the immortal flea is tricking us and is actually a frog. Now, call the frog Kelvin.

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueprimes

314 posts

blueprimes

#24 h May 29, 2024, 1:26 AM

Y by

At any point, if the flea makes right jumps $2^a + 1, 2^{a + 1} + 1, \dots, 2^{a + n - 1} + 1$ then does a left jump of $2^{a + n} + 1$ , its net change in distance is
$\sum_{i = a}^{a + n - 1} (2^i + 1) - (2^{a + n} + 1) = 2^a(2^n - 1) + n - (2^{a + n} + 1) = n + 1 - 2^a.$ From here, simply choose $n = 2^a$ which in total moves the flea to the next integer. Then repeat this process starting at $0$ and we are guaranteed to have visited every nonnegative integer at least once.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Basu_Dev

17 posts

Basu_Dev

#25 h Jan 25, 2025, 11:11 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

324 posts

Ilikeminecraft

#26 h Mar 26, 2025, 3:35 AM

Y by

Claim: For any $k,$ there exists a $n$ such that $2^k + 1 + 2^{k + 1} + 1+ \dots + 2^n + 1 - (2^{n + 1} + 1)= 1$ Proof: Take $n = 2^{k} + k.$

This trivializes!

Z K Y