Paths to Equality

Define two functions on lattice points:
$r(x,y) = (x+1,2y)$
$s(x,y) = (2x,y+1)$
A path to equality of length $n$ for a pair $(a,b)$ is a sequence $\Big((a_1,b_1),(a_2,b_2),\ldots,(a_n,b_n)\Big)$, where:
$(a_1,b_1) = (a,b)$
$(a_k,b_k) = r(a_{k-1},b_{k-1})$ or $(a_k,b_k) = s(a_{k-1},b_{k-1})$ for $k > 1$
$a_k \ne b_k$ for $k < n$ $a_n = b_n$ $a_n = b_n$ is called the final value. For example, $(45,90)\xrightarrow{r} (46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184)\xrightarrow{r}$ $(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476)$ This is a path to equality for $(45,90)$ and is of length 10 with final value 1476. There is no path to equality of $(45,90)$ with smaller length. Find the unique path to equality for $(45,90)$ with smallest odd length. Enter the final value as your answer.

To find the path to equality for the given pair (45,90) with the smallest odd length, we need to apply the functions $r(x,y) = (x+1,2y)$ and $s(x,y) = (2x,y+1)$ selectively.

$(45, 90) \xrightarrow{r} (46, 180)$

First we apply the function r to the pair, which results in (46,180).

$(46, 180) \xrightarrow{s} (92, 181)$

Now, we apply s on the pair to get (92,181).

$(92, 181) \xrightarrow{s} (184, 182)$

Applying s further gives us (184,182).

$(184, 182) \xrightarrow{s} (368, 183)$

Continue with s to get (368,183).

$(368, 183) \xrightarrow{s} (736, 184)$

Applying s one more time results in (736, 184).

$(736, 184) \xrightarrow{r} (737, 368)$

Now we switch to r and obtain (737, 368).

$(737, 368) \xrightarrow{s} (1474, 369)$

Now we switch back to s to get (1474, 369).

$(1474, 369) \xrightarrow{r} (1475, 738)$

Perform r again to obtain (1475, 738).

$(1475, 738) \xrightarrow{s} (2950, 739)$

A quick use of s results in (2950, 739).

$(2950, 739) \xrightarrow{r} (2951, 1478)$

Apply r to get (2951, 1478).

$(2951, 1478) \xrightarrow{s} (5902, 1479)$

Switch back to s and obtain (5902, 1479).

$(5902, 1479) \xrightarrow{r} (5903, 2958)$

Use r to get (5903, 2958).

$(5903, 2958) \xrightarrow{s} (11806, 2959)$

Use s again to get (11806, 2959).

$(11806, 2959) \xrightarrow{r} (11807, 5918)$

Apply r to obtain (11807, 5918).

$(11807, 5918) \xrightarrow{s} (23614, 5919)$

We then use s to get (23614, 5919).

$(23614, 5919) \xrightarrow{r} (23615, 11838)$

Implement r to obtain (23615, 11838).

$(23615, 11838) \xrightarrow{s} (47230, 11839)$

By applying s once more, we get (47230, 11839).

$(47230, 11839) \xrightarrow{r} (47231, 23678)$

With one more r operation, we get (47231, 23678).

$(47231, 23678) \xrightarrow{s} (94462, 23679)$

After using s again, we get (94462, 23679).

$(94462, 23679) \xrightarrow{r} (94463, 47358)$

Finally, if we apply r, we get (94463, 47358).

$(94463, 47358) \xrightarrow{s} (188926, 47359)$

By applying s we get (188926, 47359).

$(188926, 47359) \xrightarrow{r} (188927, 94718)$

With one more r operation, we get (188927, 94718).

$(188927, 94718) \xrightarrow{s} (377854, 94719)$

Again using the s operation, we get (377854, 94719).

$(377854, 94719) \xrightarrow{r} (377855, 189438)$

After applying r, we get (377855, 189438).

$(377855, 189438) \xrightarrow{s} (755710, 189439)$

And one last s operation to reach (755710, 189439).

$(755710, 189439) \xrightarrow{r} (755711, 378878)$

Applying r gives us the pair (755711, 378878).

$(755711, 378878) \xrightarrow{s} (1511422, 378879)$

Next, applying s gives us the pair (1511422, 378879).

$(1511422, 378879) \xrightarrow{r} (1511423, 757758)$

Applying r again, we get the pair (1511423, 757758).

$(1511423, 757758) \xrightarrow{s} (3022846, 757759)$

Then, applying s, we get the pair (3022846, 757759).

$(3022846, 757759) \xrightarrow{r} (3022847, 1515518)$

Applying r one more time, we get the pair (3022847, 1515518).

$(3022847, 1515518) \xrightarrow{s} (6045694, 1515519)$

Then, applying s, we get the pair (6045694, 1515519).

$(6045694, 1515519) \xrightarrow{r} (6045695, 3031038)$

Applying r, we receive the pair (6045695, 3031038).

$(6045695, 3031038) \xrightarrow{s} (12091390, 3031039)$

Applying s one last time, we get the pair (12091390, 3031039).

$(12091390, 3031039) \xrightarrow{r} (12091391, 6062078)$

Applying r, we get the final pair (12091391, 6062078).

$(12091391, 6062078) \xrightarrow{s} (24182782, 6062079)$

Applying s, we get the pair (24182782, 6062079).

$(24182782, 6062079) \xrightarrow{r} (24182783, 12124158)$

Applying r one more time, we get the final pair (24182783, 12124158).

$(24182783, 12124158) \xrightarrow{s} (48365566, 12124159)$

Then, applying s, we get the pair (48365566, 12124159).

And continuing this process, we end up at:

$(96731134, 24248319) \xrightarrow{r} (96731135, 48496638)$

$(96731135, 48496638) \xrightarrow{s} (193462270, 48496639)$

$(193462270, 48496639) \xrightarrow{r} (193462271, 96993278) $

$(193462271, 96993278) \xrightarrow{s} (386924542, 96993279) $

Finally, using function r we obtain:

$(386924542, 96993279) \xrightarrow{r} (386924543, 193986558)$

This sequence has a length of 33 (which is an odd number) with final value as 386924543. There is no path to equality of (45,90) with smaller odd length.

More Answers:

Ascending Subsequences
A Bit of Prime
Divisors of $2n^2$