Eventual Pairs

Because this has been posted under logic, I tend to believe that Goh has some way to solve it by hand which bizzares me.

I solve it through breadth first search.

1
2
3
4
5
6
7
8
9

from collections import deque
def f(a,b):
    queue = deque([(a,b,0)])
    while queue:
        a, b, i = queue.popleft()
        if a == b:
            return a, i
        queue.append((a+1,2*b,i+1))
        queue.append((2*a,b+1,i+1))

Running f(300,301) gives 9668 in 10 steps.

Represent the possible turns using binary digits: $0 : (a,b) \mapsto (2a , b + 1), \quad 1 : (a,b) \mapsto (a + 1, 2b).$ In this notation, binary strings represent compositions. For instance, $01$ denotes the composition given by $01(a,b) = 0(1(a,b)) = (2a + 2, 2b + 1).$ The script below generates all binary strings with 10 or fewer characters, applies the corresponding sequences of turns to 300 and 301, and prints those strings that produce a pair of matching numbers. The only sequence that produces a pair of matching numbers is $1100001011$ , which has length 10. Therefore, the smallest value of $M$ is 10. The pair produced by $1100001011$ is $(9668,9668)$ , so $N = \boxed{9668}$ .

Here is one more interesting observation. For all $x$ , $1100001011(x , x + 1) = (32x + 68 , 32x + 68).$ This means that for any pair of starting values $x$ and $x + 1$ , the minimum number of turns to get matching numbers is at most 10. There are some pairs for which a smaller number of turns is possible. For example, the starting numbers 4 and 5 both become 68 after applying the seven-turn sequence corresponding to $1101000$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

strings = ["0", "1"]
for j in range(9):
    copy = []
    for s in strings:
        copy.append(s + "0")
        copy.append(s + "1")
    strings = copy
    strings.insert(0,"1")
    strings.insert(0,"0")
def f(p,d):
    if d == 0:
        return [p[0] * 2 , p[1] + 1]
    return [p[0] + 1, p[1] * 2]
for s in strings:
    p = [300,301]
    l = list(s)
    while len(l) > 0:
        d = l.pop()
        p = f(p,int(d))
    if p[0] == p[1]:
        print(s, p)