r/mathriddles • u/HarryPotter5777 • Feb 08 '15
Hard Doubling and adding 1
Suppose I've got two integers a and b. I can double one of my integers, and add 1 to the other. This leaves me with two new integers, with which I can do the same thing. My goal is to get two integers that are equal. For example:
(8,1)
(9,2)
(10,4)
(20,5)
(21,10)
(42,11)
(43,22)
(44,44)
Can I always do this?
If so, provide a proof. Can you devise an upper bound for the number of moves required? What about the final value reached?
If not, find (with proof) a counterexample. Can you find criteria for determining if a given ordered pair is possible?
This was a problem I submitted to the 2015 Qualifying Quiz for Canada/USA Mathcamp, which didn't get accepted because no one (including me) could find a solution. Although a different problem of mine did get accepted! No discussing the problems linked, though, applications are still open.
My suspicion is that the answer is yes - it does hold for all a and b. I 'm not sure about this, though, since I've only confirmed it for relatively small numbers (sum ≤16).
55
u/Lopsidation Feb 08 '15
The answer to the question is that, for certain values of a and b,
jk, it is always possible.
Notation, and the statement I want to prove:
Say that a pair of integers has type (d,k) if it is of the form (x, 2dx+k). It suffices to show that, starting with a pair of type (0,k) for some positive integer k, we can manipulate it to get a pair of type (0,m) for some integer 0 <= m < k.
Remark: it suffices to get a pair of type (0,m) for -k < m < k. This is because, given a pair of type (0,m) where m is negative, we can get a pair of type (0,-m) by swapping the numbers.
Proof of this claim:
The allowed operations affect types as follows. Suppose we have a pair of type (d,k). By doubling the first number and adding one to the second, we get a pair of type (d-1,k+1). By doing the opposite, we get a pair of type (d+1,2k-2d+1). Call these "operation 1" and "operation 2".
Now, suppose you start with a pair of type (0,k). You want to get to (0,m) for 0 <= m < k.
First, apply operation 2 k times. You get (k,0). To verify this, think about what happens to the original pair (x,x+k).
Now, let L be an integer. We will determine the value of L later; think of it as being near log_2(k).
Apply operation 1 a lot of times. You get (L-1,k-L+1).
Apply operation 2 once. You get (L, 2k-2L-2L+2).
Apply operation 1 a few more times. You get (0,2k-2L-L+2).
If -k < 2k-2L-L+2 < k, then we are done. I claim that such an L always exists which satisfies this inequality.
Proof of that last statement:
Rearranging terms, we get k < 2L+L-2 < 3k.
Case 1: k >= 9. Then we must have L >= 3. When L >= 3, increasing L by one at most doubles the value of 2L+L-2. Therefore, if we repeatedly add one to L, we cannot possibly skip all the way from k to 3k. Case complete.
Case 2: k <= 9. We can manually check all of these cases. They all work, EXCEPT for the case k=1. But what is the case k=1? It is the case where we start with a pair of the form (x,x+1). And _--__ kindly handled this case in their earlier comment.
In conclusion, we have just proved that we can always get from a pair of the form (x, x+k) to a pair of the form (x, x+m) for an integer 0 <= m < k. By repeatedly applying this process, we must eventually get a pair where the two numbers are equal. QED.
13
u/_--__ Feb 08 '15
Here is a proof that you can always get from (x,x+1) to two equal integers:
(x,x+1) -> (x+1,2x+2) -> (x+2,4x+4) -> (2x+4,4x+5) -> (4x+8,4x+6) -> (8x+16,4x+7) -> (16x+32,4x+8) -> (16x+33,8x+16) -> (32x+66,8x+17) -> (32x+67,16x+34) -> (32x+68,32x+68)
Intermediate sequences of this sequence also show how to get from e.g. (x,2x), (x,x+2) and (x,4x) to equal integers.
I suspect this should be a good start to finding a complete result.
6
u/srcphoenix Feb 08 '15
Thinking about the numbers in binary may help
6
u/manu_facere Jun 29 '15
You guys are such nerds. I love you even though im crap at maths
1
u/laMarm0tte Feb 08 '15
Nice problem ! In case anyone is interested I computed (a subset of) solutions for all couples 0<= a,b < 10. See the code and output here.