13
$\begingroup$

A magic grasshopper sits at the origin of a number line. He can jump a distance of 1, 2, 4, 8, ... or any whole power of 2 in either direction. What is the smallest distance from the origin that requires at least 4 jumps?

$\endgroup$
7
  • 1
    $\begingroup$ 2^n * 4? Anyways I'm kinda confused as to what you mean. $\endgroup$ Commented Jul 13, 2023 at 14:02
  • $\begingroup$ I tried to reword it, so hopefully it makes more sense. $\endgroup$ Commented Jul 13, 2023 at 14:11
  • $\begingroup$ I got 32+8+2+1=43 $\endgroup$ Commented Jul 13, 2023 at 14:24
  • 1
    $\begingroup$ @newQOpenWid can you put that as an answer instead and explain how you got that $\endgroup$ Commented Jul 13, 2023 at 14:28
  • 1
    $\begingroup$ @DrXorile you mean without it grasshopper can exploit 2D? But it's already specified that the grasshopper sits on a number line, which is 1D. $\endgroup$
    – justhalf
    Commented Jul 14, 2023 at 4:49

4 Answers 4

11
$\begingroup$

Throwing this here before actually checking anything, but

  • any number that has 3 (or fewer) ones in its binary representation is trivially reached by jumping forward for each 1-bit.
  • any number that has only 1 zero in its binary representation is easily reachable: jump to the nearest 2^n-1 (all ones) above the target with 2 hops, then flip that single bit to zero by jumping backwards.

so let's try the smallest one that doesn't fall to these:

39 (binary 100111)

Oops, has a lot of ones at the end, so we can do 32 + 8 - 1

Has to be

43 (binary 101011) then.


EDIT: Proof of correctness

We've already shown above that by construction, all smaller numbers can be reached by 3 jumps or fewer; the only thing left is to show that this number cannot. Let's do that recursively.

- To get to 43 with the minimal number of hops, we'll need to do either 64-21 or 32+11.

So we need to show that neither 21 nor 11 can be reached in 2 hops.

- - To get to 21 w/ min. hops, we'll need to do either 32-11 or 16+5
- - To get to 11 (similarly), we'll need to do either 16-5 or 8+3

And that's enough, because none of 11, 5 and 3 are powers of two, and as such, cannot be reached with a single hop.

$\endgroup$
2
  • 1
    $\begingroup$ very nice and intuitive solution $\endgroup$ Commented Jul 13, 2023 at 23:19
  • $\begingroup$ nice additional proof. $\endgroup$ Commented Jul 14, 2023 at 8:18
15
$\begingroup$

A general answer for $h$ hops:

The smallest number requiring $h$ hops to reach is $\frac{2*4^{h-1}+1}{3} = 1,3,11,43,171,683,2731,10923,\dots$, which is A007583 in the OEIS.

If a number $N$ takes $h$ hops to reach from 0, it also takes $h$ hops to return to 0 from. Each hop in the return trip for $N$ will either add or subtract 1 from $N$'s least significant 1, because any smaller hop will simply have to be cancelled later, and any larger hops can be considered after this hop is taken.
It turns out that there's a simple process for determining which direction to go: If the least significant 1 is next to another 1, add to it. Otherwise, subtract from it.
Why does this work? If you subtract when you would add, then either your next hop is still an add (you wasted a hop), or it is now a subtract (you spent two hops clearing a run of two that would have taken either one or two hops normally). Likewise, if you add when you should subtract, then either your next hop is still a subtract (you wasted a hop), or it is an add on three or more numbers (nothing gained or lost), or it is an add on two numbers (you'll have to add when you should be subtracting - run this test again).

What does this mean?

Since each application of the above rule removes at least one 1, a number taking $h$ hops contains at least $h$ 1's.
Since the only hops that can remove multiple 1's are adds performed on runs of three or more 1's, every such run can be trimmed down to two to produce a smaller number with exactly $h$ 1's.
In such a number, sequences of $a$ adds followed by a subtract (an add cannot be the last hop) in the optimal path correspond to digit blocks of the form $0(01)^a1$. Since the block corresponding to $a+1$ can be obtained from the block for $a$ by replacing its final 1 with 011, and every minimal number with $h$ hops will consists purely of blocks spanning $2h$ digits, the smallest such number will consist of a single block that is as long as possible, whose binary digits look like $(10)^{h-2}11$, and this binary expansion can be shown to match the formula shown above.

$\endgroup$
2
  • $\begingroup$ Thank you. Very useful observations for the general case. $\endgroup$ Commented Jul 14, 2023 at 4:16
  • $\begingroup$ I prefer the following explanation to "why does it work": When we add 1 to rightmost 1, we flipped all 1s that are together and put 1 in the space of first 0. If we now subtract that generated 1, we did 2 operations to erase this group of 1s and leave the number the same. This means that with 2+ ones we lose nothing over subtracting. So, we should add, in case that generated 1 does not need to be subtracted and can be also added to. Meanwhile, if there is a single one, adding 1 cannot help over subtracting but can hurt, so we subtract. $\endgroup$ Commented Jul 14, 2023 at 11:20
8
$\begingroup$

My solution is:

$43 = 32 + 8 + 2 + 1$.

Firstly, note that the grasshopper's optimal strategy for any number between $2^n$ and $2^{n+1}$ is to jump either $2^n$ or $2^{n+1}$ depending on which power of $2$ the number is closest to. This reduces the number to a number under $2^n$, taking one step.

Secondly, note that the grasshopper can reach all numbers under $8$ in at most $2$ steps. Therefore, generalizing this, it can reach all numbers under $16$ in at most $3$ steps. However, if we do direct enumeration, we can note that only numbers $11 = 8 + 2 + 1$ and $13 = 8 + 4 + 1$ take $3$ steps to reach.

We can then note that numbers from $16$ to $32$ still take only $3$ steps to reach. The only possible way for a number from $16$ to $32$ to take $4$ steps to reach is if some path that leads to it uses the sequences $8+2+1$ or $8+4+1$. However, if we add these to $16$, we find out that the numbers resulted are actually closer to $32$ than to $16$, meaning the grasshopper can easily find a shortest path.

Finally, the shortest path by the grasshopper to reach all numbers between $32$ and $48$ is moving $32$ steps, first, getting a number under $16$. Therefore, we can use our solution for the $16$-problem over again. By our solution then, we have that all numbers between $32$ and $42 = 32+10$ take 3 steps to reach (all numbers from 1 to 10 take 2 steps to reach). But, we can verify $43 = 32 + 8 + 2 + 1$ takes 4 steps because it reduces to $13$ which takes $3$ steps and there are no shorter paths because reducing to $13$ is the optimal move.

$\endgroup$
3
$\begingroup$

I had a similar approach to Bass, but slightly different. It yielded the same result anyway.

The answer:

43

Approach:

Consider the binary representation of the number, starting from the higher digits. For the prefix to be 10, we need exactly one hop, because each (positive) hop corresponds to a digit in the binary number.

For a prefix of 1...10 we need 2 hops. the first will create the number 10...00, the second will be a backwards jump to create 1...10 (it can also be that the number ends with the sequence of 1s).

Then how do we continue? There are two options: if the previous step left us with a bunch of 0...0, we can repeat it. Otherwise it left us with 1...1, in which case we will do the exact same thing, but in reverse: We can either create a prefix 01 with one step or 0..01 with two.

Solution:

So we'll have to split the answer to cases. If the number starts with 10 (1 hop), it can continue to 1010 (2 hops) and then 101011 or 10101010 to create two hops. The best would be 101011 (43).

It could also continue to 1011.. (3 hops) and then 101101 (45).

If the number starts with 11.. (2 hops) it can continue as 1101.. (3 hops) and then 110101 (53) or 1101110 (110).

The lowest one being 43.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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