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).]
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.