0

Question: You have two numbers (a, b). At each step you can either multiply just one number by 2, or add any number (negative included) to both. What is the minimum number of steps to get from (a, b) to (0, 0)? Justify.

I’ve given this question a think and haven’t reached any solid conclusion, hence I’ve come to ask for any second opinions... all of which are absolutely welcome!

My approach was to start from the end goal of reaching (0, 0). In order to reach (0, 0) the final step has to be an addition, as no multiplication in the case of this question will reach 0... and I think due to a bit of a lack of understanding of what the question is actually asking for causes me to get stumped here.

Any suggestions/contributions would be greatly appreciated!

[The context of this question is from a problem-solving paper for university admissions and so it’s designed to be particularly challenging, although there should be a general solution, i.e. for n numbers, instead of just 2 numbers as in this question (a and b).]

MKY6
  • 29
  • Are you sure that this can be done? If a=0 and b=1, then how would you get to (0,0)? – gd1035 Jul 05 '18 at 20:44
  • This was the exact wording of the question and I think that is what I am finding challenging about it. It’s a very open-ended question and I the objective is to reach some sort of algorithm, i.e step-by-step method (likely algebraically) of reliably reaching (0, 0) in any case for any values of (a, b). – MKY6 Jul 05 '18 at 20:48

1 Answers1

2

So we start with $(a, b) $, the next thing we want to do is add a number to both parts so that one number is twice the other, that is transition to $(a+c, b+c) $ so that $b+c=2(a+c)$, thus $$ c=b-2a $$ and $$ (a+c, b+c)=(b-a, 2b-2a) $$ We then double the first, and subtract $2b-2a$ from both. Thus the sequence is $$ (a, b) \rightarrow (a+[b-2a] ,b+[b-2a]) =(b-a, 2[b-a] ) \rightarrow (2[b-a], 2[b-a] ) \rightarrow (0,0). $$ This is three steps. All there is left to do is show that it cant be done in two steps. As you've already realised, the last step must be addition to both sides, and if there is only two steps then the step before this must be doubling one of them, which leads to pairs of the form $(2c,c) $ or $(c,2c) $, which is not general.

Eddy
  • 1,139
  • 7
  • 12
  • Thank you so much for this, I can clearly see the whole jist of such a question now and the approach you made... it’s been a huge help!! – MKY6 Jul 05 '18 at 21:25