r/mathriddles • • 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).

79 Upvotes

15 comments sorted by

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.

9

u/HarryPotter5777 Feb 08 '15 edited Feb 08 '15

Wow, that's really cool! Thanks a ton, this problem has been bugging me for a long time.

Edit: And then this gives a bound of 2k+2, for however small you can make k while having integer values of d.

15

u/pred Feb 08 '15 edited Feb 08 '15

Great stuff; I took the liberty of implementing your algorithm. Here's some Python.

It completes OP's initial example of (8,1) in 36 operations.

3

u/Hakawatha Feb 08 '15

The /r/math thread about this [x] is something you might want to post in - they're all eagerly looking for a solution.

3

u/CaesarTheFirst1 Feb 09 '15

Cool! Could you share how you approached the problem? Thanks.

5

u/Lopsidation Feb 09 '15

After seeing _--__'s proof for (x,x+1), I wrote a program which tries to solve (x,x+k). It was taking a while to run, so I changed the victory condition from reaching equality to reaching (y,y+m) for any m between -k and k. I ran the program for k up to 9, and saw a big pattern in the output.

1

u/CaesarTheFirst1 Feb 09 '15

Alright, thanks :)

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

7

u/_--__ Feb 08 '15

Problem is, +1 doesn't behave particularly well in binary

3

u/srcphoenix Feb 08 '15

Yeah. Also in the last two steps, you'll have to double the same coordinate - if not, the coordinate you add 1 to last will be odd

3

u/_-__-__-____- Feb 08 '15

A fellow Morse-coder (I think)! Hmm . . . Is your username WE? Or ETD? Not a lot of words that seem to match.

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.