M2S3: From 11 to 25

Logic Level 3

In the game of M2S3, the goal is to use minimum number of steps to get from one number to the next. In each step, you can either

multiply by 2, or
subtract 3.

For example, if we wanted to get from 8 to 11, we could do so in 5 steps:

$\large 8 \overset{-3}{\longrightarrow} 5 \overset{\times2}{\longrightarrow}10 \overset{-3}{\longrightarrow} 7\overset{\times2}{\longrightarrow}14 \overset{-3}{\longrightarrow}11.$

What is the minimum possible number of steps required to get from 11 to 25?

The answer is 7.

14 solutions

Arjen Vreugdenhil
Feb 21, 2017

Relevant wiki: The M2S3 Game

Working backward: to have $25$ in step 0,

step 1 must have $28$ ,

step 2 must have $14$ or $31$ ,

step 3 must have $7$ , $17$ , or $34$ ,

step 4 must have $10$ , $20$ , ( $17$ ), or $37$ (we ignore $17$ because we already found a quicker way from $17$ to $25$ ),

step 5 must have $5$ , $13$ , ( $10$ ), $23$ , or $40$ ,

step 6 must have $8$ , $16$ , $26$ , ( $20$ ), or $43$ ,

step 7 must have $4$ , $11$ , ( $8$ ), $19$ , ( $13$ ), $29$ , or $46$ ,

and we see that $11$ can lead to $25$ in no less than 7 steps.

int a[] = new int[1000];
int old_n = 0, n = 0;
int step = 0;

a[n++] = 25;
int goal = 11;
boolean found = a[0] == goal;

while (!found) {
    step++;
    System.out.print(""+step+" steps: ");
    int start_n = old_n; old_n = n;
    for (int i = start_n; i < old_n; i++) for (int opt = 0; opt < 2; opt++) {
        int new_a = -1;
        switch (opt) {
            case 0: if (a[i] % 2 == 0) new_a = a[i]/2;
                    break;
            case 1: new_a = a[i]+3;
        }
        if (new_a < 0) continue;

        if (new_a == goal) found = true;
        int j = 0; while (j < n && a[j] != new_a) j++;
        if (j >= n) {
            System.out.print(" "+new_a);
            a[n++] = new_a;
        }
    }            
    System.out.println();
}

Output:

1 steps:  28
2 steps:  14 31
3 steps:  7 17 34
4 steps:  10 20 37
5 steps:  5 13 23 40
6 steps:  8 16 26 43
7 steps:  4 11 19 29 46

Moderator note:

Great explanation of how to work backwards. Compared to the working forward approach, this greatly reduces the number of cases we have to look at. For a visual representation, see Kevin Chung's solution.

Common mistakes:

An approach claims that when working backwards, we should always divide by 2 each time we get an even number, and add 3 each time the number is odd. Though this claim is true when going from 11 to 25, can you find a counter example?
An approach that considers the number of $\times 2$ that we need, and then minimizes the number of $-3$ that we need. However, this the naive optimization doesn't necessarily yield the actual minimum. Though this claim is true when going from 11 to 25, can you find a counter example?

Working backwards is a smart strategy! Unlike the straightforward method where each number branches out two cases, this method has fewer cases to consider.

Christopher Boo - 4 years, 3 months ago

In response to Challenge Master note:

One

The easiest counterexample would be going from $31$ to $25$ , which can be done in two steps: $25 \leftarrow 28 \leftarrow 31.$ If we would mindlessly divide by two for each even number, we would miss this solution.

Two

The "naive" approach assumes that the minimal solution must have the smallest possible number of multiplications with two. But it might be that adding a few doubling operations removes the need for even more subtractions.

I have not found a counterexample. In fact, the computer tells me that for $x,y < 20\:000$ , the "naive" solution to find a path $x \to y$ is actually the minimal path...

Arjen Vreugdenhil - 4 years, 3 months ago

For 2, I was concerned about "But it might be that adding a few doubling operations removes the need for even more subtractions."

After digging further into the theory, I now start to believe that the naive approach does indeed yield the best solution. Let me lay it out:

Suppose we want to go from $a$ to $b$ where we multiply by 2 $n$ times. We must have $2^n a > b$ and $3 \mid 2^n a - b$ .

Consider the binary base representation of these numbers.
Let $a = a_x a_{x-1} \ldots a_0 \, _2$ .
Let $b = b_y b_{y-1} \ldots b_0 \, _2$ .
Let $c = \frac{ 2^na - b } { 3} = c_z c_{z-1} \ldots c_1 \, _2$ .

Claim: (possibly slightly off in the indexing) Given exactly $n$ multiplications, the minimium number of steps is equal to:
$\begin{aligned} MS(a,b,n) & = n + ( \text{ number of 1's in } c_i \text{ for } i = 10 \text { to }n-1) \\ & + c_z c_{z-1} \ldots c_{n} \,_2 \text{(interpreted as a decimal)} \end{aligned}$

Other than the $n$ multiplications, the latter terms account for how best to subtract 3 optimally - If you subtract twice, just push it before a multiplication, until there is no more multiplication signs, in which case you have to subtract all of them.

Claim: (not fully certain) Over all $n$ , $MS(a,b,n)$ is minimial when $n$ is minimal. IE The naive solution is the best.
(This part is tricky because $c$ changes.)

Calvin Lin Staff - 4 years, 3 months ago

You may want to edit your comment to make the last part legible.

My investigation last night went along similar lines as yours. I have no watertight proof, but come very close-- and the computational evidence is strong too.

Arjen Vreugdenhil - 4 years, 3 months ago

Yesterday I ended up writing $S(x,y,n) = n + q + \#_2 r,\ \ \ \ p = \frac{2^nx - y}3 = 2^nq + r,\ \ r < 2^n$ with precisely the same meaning as your formula for $MS(a,b,n)$ .

Here are my further thoughts. I focus on the case $3\not|x,y$ , in which $n$ must be even iff $x\equiv y$ and odd iff $x\not\equiv y$ mod 3.

Increasing $n$ by two results in $p' = 2^nx + p$ , which leaves the existing digits of $r$ unchanged, but adds digits in the front. The value of $q$ does not decrease, since $q = \lfloor p/2^n\rfloor = \lfloor \tfrac13(x - y/2^n)\rfloor$ is an increasing function of $n$ .

Arjen Vreugdenhil - 4 years, 3 months ago

@Arjen Vreugdenhil – I observed a similar pattern too. If only one of $a$ , $b$ is divisible by $3$ , then it is impossible to reach $b$ from $a$ .

If both $a$ and $b$ are divisible by $n$ , then the problem becomes equivalent to multiply by 2, subtract 1. $(\times 2, - 1)$ . I believe a similar algorithm can be followed for this case.

For the remaining cases where $a$ , $b$ are both not divisible by $3$ :

We want to show that $MS(a, b, n)$ is minimal when $n$ is minimal. The sequence of numbers is bounded above by $2b$ . As we increase $n$ , we are increasing the multiplications occurring in the sequence, and since the sequence cannot cross $2b$ , cycles are formed.

$MS(11, 25, 3) = 7$ . The sequence is $11 \to 8 \to 5 \to 10 \to 7 \to 14 \to 28 \to 25$ .

$MS(11, 25, 5) = 11$ . The sequence is $11 \to 8 \to 5 \to 2 \to 4 \to 8 \to 5 \to 10 \to 7 \to 14 \to 28 \to 25$ . The $5\to 2 \to 4 \to 8 \to 5$ cycle is unnecessary.

As a result, $MS(a, b, n)$ increases as $n$ increases. These cycles are redundant, and can be eliminated by choosing a smaller $n$ . Hence to minimize $MS(a, b, n)$ , we should minimize $n$ .

Pranshu Gaba - 4 years, 3 months ago

@Pranshu Gaba – Pranshu, I appreciate your contribution pointing out the cycles. However, I am not yet convinced why increasing the number of multiplications $n$ should necessarily generate cycles.

My algorithm to generate a sequence is as follows (for the case $3 \not\div x,y$ ): First, let $n$ be the smallest positive integer such that $2^n x > y$ and $n$ is even if $x \equiv y$ or $n$ is odd if $x \equiv -y$ mod 1. Then calculate $p = \frac{2^nx - y}3,$ and split $p = 2^nq + r$ with $r < 2^n$ . The sequence is now generated as follows: first, execute the subtraction " $-3$ " $q$ times. Then multiply " $\times 2$ " $n$ times; after the $(n - k)$ -th multiplication perform a subtraction " $-3$ " iff the $k$ -th bit of $r$ equals 1. I summarize this sequence by writing $q|r$ with $r$ in its binary representation. For the examples you give we have $MS(11,25,3):\ p = \frac{8\cdot 11-25}3 = 21 = 8\cdot 2 + 5;\ \Longrightarrow\ 2|101;$ $MS(11,25,5):\ p = \frac{32\cdot 11-25}3 = 109 = 32\cdot 3 + 13;\ \Longrightarrow\ 3|01101;$ and we easily add $MS(11,25,7):\ p = \frac{128\cdot 11-25}3 = 461 = 128\cdot 3 + 77;\ \Longrightarrow\ 3|1001101.$

Your claim seems to be that the sequence $2|\dots$ (two subtractions starting at 11) has the same effect as the sequences $3|01\dots$ , and $3|\dots$ has the same effect as $3|10\dots$ . This is easy to check: $11 \to 8 \to 5\ \ \ \text{vs.}\ \ \ 11 \to 8 \to 5 \to 2 \to 4 \to 8 \to 5,$ and $11 \to 8 \to 5 \to 2\ \ \ \text{vs.}\ \ \ 11 \to 8 \to 5 \to 2 \to 4 \to 1 \to 2,$ but I would like to see proof that this kind of cycling will always happen. In a way my observation that with increasing $n$ , $r$ only adds binary digits up front without changing the existing digits claims the same thing, but a more intuitive proof of cyclic behavior would be nice.

Arjen Vreugdenhil - 4 years, 3 months ago

@Arjen Vreugdenhil – It is in fact not necessary that increasing the number of multiplications should generate cycles. If $a$ is large, then there would be no cycles initially, and it would take more number of multiplications before cycles start to generate. I just wanted to show a rough idea of why the number of steps increases as the number of multiplications increases.

Your algorithm very elegantly shows why MS(a, b, n) is a non-decreasing sequence with respect to $n$ , and therefore number of steps required strictly increases as $n$ increases.

Pranshu Gaba - 4 years, 3 months ago

Since we are having so much fun, I put together a Wiki page about this here . Feel free to add/edit/etc.!

Arjen Vreugdenhil - 4 years, 3 months ago

From what I can see, the only way in which 2 might not yield an optimal solution is if we have a negative target. For instance, to go from 1 to -20 doesn't require any $\times2$ s: $1 \overset{-3}{\longrightarrow} -2 \overset{-3}{\longrightarrow} -5 \overset{-3}{\longrightarrow} -8 \overset{-3}{\longrightarrow} -11 \overset{-3}{\longrightarrow} -14 \overset{-3}{\longrightarrow} -17 \overset{-3}{\longrightarrow} -20$ But it's obviously better to do this: $1 \overset{-3}{\longrightarrow} -2 \overset{-3}{\longrightarrow} -5 \overset{\times2}{\longrightarrow} -10 \overset{\times2}{\longrightarrow} -20$

Stewart Gordon - 4 years, 3 months ago

I’m not as advanced as most of you, but what I did is work out that 25 isn’t a multiple of 2, so the only way of getting to 25 is -3, which then meant the previous number was 28. 28 is a multiple of 7, which can be reached by x2 7 twice. 11 - (2x3) = 11-6=5. 5x2=10. 10-3= 7. 7x2= 14 x2= 28. 28-3= 25. You count your steps, and there are 7 steps. I hope this way of explaining helps younger users understand the problem 😬

Raquel Perez - 2 years, 6 months ago

These are 8 steps

Amit Nimbiwal - 1 week, 1 day ago

Chung Kevin
Feb 22, 2017

If we tried to work forwards, then each time we have 2 possible paths to go, and after $n$ steps there are $2^n$ possibilities to track. Instead, if we work backwards, we can eliminate some paths - If we had an odd number then we could only have "subtract 3" to get there, instead of "multiply by 2".

We display the steps in the following table. If the number is odd, then we just add 3 and display it directly below. If the number is even, then we split off where the left branch divides by 2, and the right branch adds 3.

We see that the first 11 appears in the 7th previous step. Hence, the answer is 7.

Great work!

Abdelhamid Saadi - 4 years, 3 months ago

Good eye! I've fixed it

Pi Han Goh - 4 years, 3 months ago

Beautiful diagram! It shows all the possibilities after $n$ steps from the end very clearly.

Pranshu Gaba - 4 years, 3 months ago

Very Professional diagram! And its easy to read!

Bella Woodbridge - 2 years, 10 months ago

Marta Reece
Feb 12, 2017

The sequence of operations is: $-3,-3,\times2,-3,\times2,\times2,-3$ .

To arrive at it, we can start by determining the minimum number of multiplications by 2. A single one will not get us high enough. Two will result in a number which will have a remainder of 2 after division by 3. We need 25, which has a remainder of only 1. Subtracting 3's before or after multiplication by 2 will not change the value of the remainder, so multiplying twice will not work. So the minimum number of multiplications by 2 is 3.

To minimize the number of subtractions, we want to do them before multiplication whenever possible. (We would have to subtract 3 twice instead of once if it is done later.) Subtracting 3 from 11 twice gets us down to 5. (Any lower and multiplying by 2 three times ends in too small a number.) We multiply once, to get 10, and see if we can subtract a 3 and still get above 25 after multiplying by 4. We can do that once, and get 7. 7 times 4 is 28. Subtract 3 and we are done.

Moderator note:

This solution claims that: The minimum number of steps from $a$ to $b$ is given by:
1. Fiind the minimum $n$ such that $2^n a > b$ and $2^n a \equiv b \pmod{3}$ .
2. Now, going from $2^na$ to $b$ , we minimize the number of "subtract 3" that is needed (see Pranshu's binary counting).

Can you spot the logical error(s) made? Can you find a counter example where this algorithm doesn't yield the minimum number of steps?

There is some observation to eliminate invalid solution, but it is still not clear to me what is the promising way to solve this problem. Do you know what step you should take next? Or there are still some trial and errors?

Christopher Boo - 4 years, 3 months ago

Reading your solution for the first time, this line could use some explanation for why we are dividing by 3. There is no division by 3 mentioned in the original problem. "Two will result in a number which will have a remainder of 2 after division by 3."

Rufus Littlefield - 4 years, 3 months ago

The solutions given was not meant to be a general solution applicable to all such problems, only a rational way of arriving at an answer to this particular problem. So counter-examples are likely to exist.

Marta Reece - 4 years, 3 months ago

In the discussion on Arjen's solution, even though there is a logical gap, it seems like there are no counter-examples. This provides support that the gap could be patched (by tracking through all of the details).

Calvin Lin Staff - 4 years, 3 months ago

Your solution are equivalent to mine. ☺️

Hannes Camitz - 4 years, 3 months ago

As already pointed out, you need to show that the number of "Multiply by 2" steps should be 3. (I suggest breaking this down into three questions:

Why not 7 or more?

Why not 4 or 6?

Why not 5?

Those are each dealt with easily, but shouldn't be omitted.)

But that aside, I think it's helpful to note that just doing those three steps would result in 88, i.e. an excess of 88-25=63=3*21=3(8+8+4+1). That gives a pretty good idea of how to minimize the number of "Subtract 3" steps. (And yes, the choice to write 8+8 rather than 16 is deliberate.)

Peter Byers - 4 years, 3 months ago

As already pointed out, you need to show that the number of "Multiply by 2" steps should be 3. (I suggest breaking this down into three questions:

Why not 7 or more?

Why not 4 or 6?

Why not 5?

Those are each dealt with easily, but shouldn't be omitted.)

Alternately, though, you could deal with all of those at once, in the form: Can we get the desired result, 25, by doing (in any order) 4 or more "Multiply by 2" steps and 2 or fewer "Subtract 3" steps?

No we cannot, because the smallest possible result of those steps would be $(11-3-3)*2*2*2*2=80.$

Peter Byers - 4 years, 3 months ago

Stewart Gordon
Feb 21, 2017

As a first attempt, we keep doubling until we reach a number that is greater than 25 and congruent to 25 modulo 3. Obviously, we can then reach 25 without any further doubles - just keep subtracting 3. The challenge is to find the optimum points at which to subtract 3.

In this case, we double 3 times, to 88. We have to subtract 63. Subtracting 3 after doubling thrice is just subtracting 3 from the final result. Subtracting 3 after doubling twice is equivalent to subtracting 6 from the final result. Subtracting 3 after doubling once is equivalent to subtracting 12 from the final result. Subtracting 3 before any doubling is equivalent to subtracting 24 from the final result.

63 = 24 + 24 + 12 + 3 gives us the minimum number of subtractions, a total of $\boxed{7}$ steps.

If we tried doubling more times, we would have to subtract 151, 327, etc. In each case, we would only have to subtract more 24s, therefore this cannot possibly lower the total number of steps.

Moderator note:

Can you spot the logical error(s) made? Can you find a counter example where this algorithm doesn't yield the minimum number of steps?

I got lost in the part "subtracting 3 after doubling thrice is just subtracting 3..." can you clarify?

Christopher Boo - 4 years, 3 months ago

Subtracting 3, 6, etc. from the final result. I've added this phrase for clarification.

Stewart Gordon - 4 years, 3 months ago

I understand it now, thanks for the clarification!

Christopher Boo - 4 years, 3 months ago

Good solution!

I'd like to add an explanation on why the first part works. Let's say the difference is $x$ . Subtracting $3$ from $x$ doesn't affect the remainder of $x$ when divided by $3$ . Hence, we must multiply $x$ by $2$ until it is greater than the target number and is divisible by 3.

Christopher Boo - 4 years, 3 months ago

Great solution! I loved how you systematically found out the optimum number of steps. It is more efficient to subtract as soon as possible, but we don't want to subtract too much that we go below 25.

By writing 63 as sum of 24, 12, 6, and 3, it becomes clear what is the maximum number of times we can subtract 24. In other words, we want to find $a, b, c, d$ such that $a \times 2^3 + b \times 2^2 + c \times 2 + d \times 2^0 = \frac{88 - 25}{3}$ and $a + b + c + d$ is minimized.

We see that $2 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 21$ , so the minimum number of subtractions is $2 + 1 + 1 = 4$ and we doubled $3$ times, so a total of $7$ steps.

Pranshu Gaba - 4 years, 3 months ago

I like how you used the binary number to help calculate the minimum number of steps.

However, I would like to point out that your approach makes an assumption about certain values. Can you spot that assumption?

Hint: Where does Pranshu's counting break down? For example, if we only multiplied by 4, how many steps do we need to use to subtract 63?

Calvin Lin Staff - 4 years, 3 months ago

If we tried doubling more times, we would have to subtract 151, 327, etc. In each case, we would only have to subtract more 24s, therefore this cannot possibly lower the total number of steps.

I think the error is in this statement. If we doubled more times, then we are allowed to subtract higher powers of 2 like 48, 96, etc. We cannot directly say that doubling more times will result in more steps.

If we only multiplied by 4, then we can't subtract 24. $63 = 3(5 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$ , so we would need 5 + 0 + 1= 6 steps to subtract 63.

Pranshu Gaba - 4 years, 3 months ago

With respect to the CM note:

Hint: In order to minimize $f(x) + g(x)$ we cannot simply find the value of $c$ that minimizes $f(x)$ , and then calculate $f(c) + g(c)$ .

Hint: Where does Pranshu's counting break down? For example, if we only multiplied by 4, how many steps do we need to use to subtract 63?

Calvin Lin Staff - 4 years, 3 months ago

A Former Brilliant Member
Jun 17, 2018

Given that there are two operations, this immediately jumped out to me as a binary tree problem (I have no idea if that's the correct name, or if that name refers to something completely different but it's the only thing I can think to call problems like this). By that I just mean a problem than can be drawn out using a binary tree like structure. The root of the tree being 11 in this case, and each child node being the result of one of the two possible operations. Then, let each branch extend until either it has a value greater than or equal to 28 or less than or equal to 0 (since 28 would allow 1 additional step to get to 25, where larger values would require reduction before being useful which just adds extra steps. It is impossible to reach a value greater than 0 once it is reached given these operations), or it is the target value. Then compute the shortest path from the root to a target node and that's the number of steps. This particular problem is actually simple enough you could write it out by hand using this method. Idk if this image is going to show (and go easy I made it in paint), but you'll see I used arrows to indicate loops instead of just writing the whole tree again. Also one shady use of an asterisk that I hope should still be obvious what I mean.

Fwiw, i think you can also stop every time you reach a number that was already part of the tree (like 8 and 11), since any path through the current node will correspond to a shorter path through the earlier appearance.

PS Nice observation to remove any value above 28, since repeated subtractions of 3 can be accomplished quicker by subtracting before multiplying by 2.

C . - 2 years, 9 months ago

Alvin Hu
Jun 19, 2018

11-3=8 8-3=5 5x2=10 10-3=7 7x2=14 14x2=28 28-3=25

Vandan Agrawal
Sep 9, 2019

Well, what I did was make a node-edge graph with edges being arrows and wrote down possible combinations. Not the most efficient way I guess but managed to get the answer with it.

Hamza Zreiqat
Nov 14, 2018

11-3=8 8-3=5 5x2=10 10-3=7 7x2=14 14x2=28 28-3=25

Nothing Nothing
Jun 13, 2018

Solution -3,-3,×2,-3,×2,×2,-3

11, 8, 5, 10, 20, 40, 80, 160.

A Former Brilliant Member - 2 years, 11 months ago

Shayan Ali
Jun 11, 2018

So my approach was much less insightful and naive than almost everyone here, but I spent a good amount of time on it and I was proud of myself enough to share it here. I basically wrote up some python code (copied below) that would take a start point (i) and an end point (o), and randomly either multiplied by 2 or subtracted by 3. It would save that list of operations, until our 'counter' (which started at 11) either goes above 2x25 or below 0. If that happens then the counter would go back to 11 and our list, p, is emptied (basically start all over again). After running several runs of this method for "path(11,25)" I found that 7 was the smallest length of "p" that I got, which I'm sure has some statistical significance too of being the shortest path.

In a nutshell, it's a computer doing random (but bounded) trial and error to find different paths from 11 to 25, the shortest of which over several runs was 7, which gave me enough confidence to believe that the shortest route is 7 steps. [s,s,m,s,m,m,s].

This problem actually got me to sign up for Brilliant, I'm really looking forward to what you all think, and the insight (if any) to be provided on this method. I'll be checking some of the courses too, really excited to be learning properly again!

import random
def path(i,o):   #i=start, o=end

    c = i   #c is the counter
    p = []  #p is our path
    operations = ['s','m']   #s for subtract and m for multiply

    while c>0:
        rand_op = random.choice(operations)

        if rand_op=='s':
            c=c-3
            p.append('s')

        else:
            c=c*2
            p.append('m')

        if c>2*o or c<0:
            c=i
            p=[]

        print(c)    

        if c==o:
            break

    print(p)
    print('End')

Mountain Du
Jun 11, 2018

Working forwards, we can see that the output in mod 3 is only affected by the x2 function, not the -3 function. Thus, the quantity [11x 2^y (mod 3)] would have to be congruent to [25 (mod 3)], given that y is the number of times that x2 is used.

However, since we can only make the actual quantity smaller with the -3 function, the quantity [11x 2^y (mod 3)] would have to be greater than 25. And, because we want to minimize the number of steps it takes to the final output, we want to find the smallest quantity that fits these criteria) We find that the smallest possible quantity that fits these criteria to be 88 (as 11 and 22 are both too small, and 44 is not congruent with 25 in mod 3). Thus, y = 3.

Playing around with 88 a bit:

8( 11 ) - 25 = 63

8( 11 ) - 63 = 25

8( 11 ) + 21( -3 ) = 25

Thus, 21 effective uses of -3 are needed to bring 88 to 25.

Working backward from there:

8( 11 ) + 21( -3 ) = 25

8( 11 ) + 20( -3 ) -3 = 25

{4( 11 ) + 10( -3 )} x2 -3 = 25

{2( 11 ) + 5( -3 )} x2 x2 -3 = 25

{2( 11 ) + 4( -3 ) -3 } x2 x2 -3 = 25

{[( 11 ) + 2( -3 )] x2 -3 } x2 x2 -3 = 25

{[ 11 -3 -3 ] x2 -3 } x2 x2 -3 = 25

Therefore, we can get from 11 to 25 in 7 steps

Grant Bulaong
May 19, 2017

The " $\times 2$ " step "toggles" the number's congruence $\mod 3$ from either $1$ to $2$ or vice versa while the "subtract 3" step retains the number's congruence $\mod 3$ . $11 \equiv 2 \mod 3$ $25 \equiv 1 \mod 3$ Since the numbers satisfy the congruences above, the " $\times 2$ " step must be done on $11$ an odd number of times. Clearly, " $\times 2$ " should be executed at least $3$ times.

If we immediately perform the " $\times 2$ " step three times, the resulting number will be $11\times 2 \times 2 \times 2 =88$

This requires a reduction of $63$ , so the " $-3$ " step will need to be repeated a total of $21$ times.

[A] If a " $-3$ " step was done after the last " $\times 2$ " step, the resulting number be will smaller by $-3$ .

This equivalent to repeating the " $-3$ " step once.

[B] If a " $-3$ " step was done before the third (and last) " $\times 2$ " step but after the second, the resulting number be will smaller by $(-3)\times 2 = -6$ .

This equivalent to repeating the " $-3$ " step twice.

[C] If a " $-3$ " step was done before the second " $\times 2$ " step but after the first, the resulting number be will smaller by $(-3)\times 2 \times 2= -12$ .

This equivalent to repeating the " $-3$ " step $4$ times.

[D] If a " $-3$ " step was done before the first" $\times 2$ " step, the resulting number be will smaller by $(-3)\times 2 \times 2 \times 2= -24$ .

This equivalent to repeating the " $-3$ " step $8$ times.

The " $-3$ " step requires $21$ repetitions, and these can be done in four steps by carrying out [D] twice, [C] once, then [A] once. Thus. the total number of steps required is $3+4=7$ .

Deepesh Agarawal
Feb 26, 2017

Since 25 cannot be obtained by multiplying with 2 hence we need to get 28 so that we can subtract 3. Now in the given example we have been given the fastest way to obtain 14 (which is 28/2) from 8 (which is 11-3) BHAM!!! solution obtained... 4 (from example) + 1(for 11-3) + 2 (to get 25 from 14 which is x2 followed by -3)

You have made some interesting observations. Can you explain why there are no other shorter ways to reach 28?

Agnishom Chattopadhyay - 4 years, 3 months ago

Jase Jason
Feb 15, 2017

Just work backwards, and divide by two every time you get an even number, and add 3 every time an odd number appears since you cannot get an even number from multiplying by two and cannot get an odd number by subtracting 3 from an odd.

This algorithm worked in this problem, but it doesn't always work. Why should we divide by 2 every time we get an even number?

When we work backwards, we can perform either division by 2 or add 3. When we get a odd number, we have to add 3 since the sequence has only integers. However, when we have an even number, we can choose between either choice.

Consider the case where we want to reach 25 from 31.
We start with 25. We have to add 3, we get 28. Now if we want to reach 31, it would make sense to add 3 instead of dividing by 2 even though we are at an even number.

Pranshu Gaba - 4 years, 3 months ago

That's what I did too. Working backwards but always accounting for both possible steps. This shows the "feeder numbers" which work, and we can also see why 7 is the minimum.

Chung Kevin - 4 years, 3 months ago

I see. Thanks, I didn't see much of it and just rammed my way through. I just got lucky for this question, I guess.

Jase Jason - 4 years, 3 months ago

Nice logic! :-)

Ojasee Duble - 4 years, 3 months ago

I don't think this actually works, because the very last operation (to get from 25 to 11) is adding 3 to an even number: 25 + 3 = 28 ; / 2 = 14 ; / 2 = 7 ; + 3 = 10 ; / 2 = 5 ; + 3 = 8 ; + 3 = 11 Following the stated rule, you would end in an infinite loop: ... 5 ; + 3 = 8 ; / 2 = 4 ; / 2 = 2 ; / 2 = 1 ; + 3 = 4 ...

Rufus Littlefield - 4 years, 3 months ago

M2S3: From 11 to 25

The answer is 7.

14 solutions

Moderator note:

Moderator note:

Moderator note:

0 pending reports