Given two non-negative integers, $A$ and $B$ , you can perform these four operations:

```
1. A+=B
2. B+=A
3. A+=A
4. B+=B
```

If
$A=2020, B=2021$
, is it possible to make
$A$
and
$B$
equal after
**
finite
**
operations?

**
Bonus: Given any non-negative integer
$A,B$
, if it is possible to make them equal, try to find a general strategy or algorithm to make them equal in your discussion. If there isn’t a way to make them equal, try to explain why.
**

Yes
No

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

There's actually a flaw of your approach. If doing 3rd operation 2021 times, then A will become A*2^2021 (Since you are multiplying A by two 2021 times)

Alice Smith
- 3 months, 2 weeks ago

Log in to reply

Just realised I had misread this - I'd thought you'd posted the incorrect solution! Sorry about that. I've deleted the report now.

Stewart Gordon
- 3 months, 2 weeks ago

I seem to have now found a correct solution. However, Brilliant isn't giving me the option to post a solution. I'm not sure if it only offers the option if I've submitted a correct answer, which I now can't do having submitted an incorrect answer.

Stewart Gordon
- 2 months, 4 weeks ago

Log in to reply

You can post the solution in the reply section first:)

Alice Smith
- 2 months, 4 weeks ago

Log in to reply

@Alice Smith
–
**
Algorithm
**

Let $Z_A$ and $Z_B$ be the greatest power of $2$ to divide $A$ and $B$ respectively.

- If $Z_A = Z_B$ and $A > B$ , execute operation 1.
- If $Z_A = Z_B$ and $A < B$ , execute operation 2.
- If $Z_A < Z_B$ , execute operation 3.
- If $Z_A > Z_B$ , execute operation 4.
- If $A = B$ , halt.

**
Trying it out
**

Given the initial values $A = 2020$ , $B = 2021$ , the algorithm halts at the 36th iteration, with $A = B = 67108864$ .

**
Why it works
**

Let $A_0, B_0$ be the initial values of $A$ and $B$ respectively. Let $A_n, B_n$ be successive values.

Let $A'_n = \frac{A_n}{\gcd(A_n, B_n)}$ and $B'_n = \frac{B_n}{\gcd(A_n, B_n)}$ for arbitrary $n$ .

Then the possibilities are:

- If $A'_n$ and $B'_n$ are both odd, and $A'_n > B'_n$ , we execute operation 1, giving $A_{n+1} = A_n + B_n, B_{n+1} = B_n, A'_{n+1} = A'_n + B'_n, B'_{n+1} = B'_n$ .
- If $A'_n$ and $B'_n$ are both odd, and $A'_n < B'_n$ , we execute operation 2, giving $A_{n+1} = A_n, B_{n+1} = A_n + B_n, A'_{n+1} = A'_n, B'_{n+1} = A'_n + B'_n$ .
- If $B'_n$ is even, we execute operation 3, giving $A_{n+1} = 2 A_n, B_{n+1} = B_n, A'_{n+1} = A'_n, B'_{n+1} = \frac{B'_n}{2}$ .
- If $A'_n$ is even, we execute operation 4, giving $A_{n+1} = A_n, B_{n+1} = 2 B_n, A'_{n+1} = \frac{A'_n}{2}, B'_{n+1} = B'_n$ .
- If $A'_n = B'_n (=1)$ , then $A_n = B_n$ , so we halt.

Obviously, when operation 3 or 4 has been picked, $A'_{n+1} + B'_{n+1} < A'_n + B'_n$ .

When operation 1 has been picked, $A'_{n+1}$ will be even, thus operation 4 will be picked next, giving $A'_{n+2} = \frac{A_n + B_n}{2} < A_n$ (since $A_n > B_n$ ). On the other hand, $B'_{n+2} = B'_n$ . Thus in this scenario, $A'_{n+2} + B'_{n+2} < A'_n + B'_n$ .

The same argument applies when operation 2 has been picked.

These show that, if you take out the temporary increases from operations 1 and 2, $A'_n + B'_n$ becomes a strictly decreasing sequence of positive integers. Since the minimum possible value occurs when $A'_n = B'_n = 1$ , it must eventually reach this point.

Stewart Gordon
- 2 months, 3 weeks ago

Do you mean lcm(A,B)?

Also, as Alice said, A+=A results in doubling.

Depicting all this by 2x2 integer matrices applied to the vector (A, B), I arrived at constraints on the solution matrix (a, b; c, d):

• determinant must be a power of 2

• aA + bB = cA + dB

Together, this seems to be impossible because A/B*2^n can never be integer.

I got the answer wrong but still don't know why.

Nathaniel Arnest
- 2 months, 4 weeks ago

My 2c: wlog assume gcd(A,B)=1. Then for any integer m there are integer a,b which solves aA+bB=m (extended Euclidean algorithm). a-B,b+A is also a solution and the determinant of (a, b; a-B, b+A) is also m which we could choose to be a power of 2. But I don’t know if there is a composition of the 4 2x2 matrices that yield any such solution matrix. I don’t know how to characterize the “composition space” (?), an aspect of linear algebra that eludes me.

I’m pretty sure this can be solved for any A,B and this can be proved via a simple algorithm.

Alice, a hint please!

Tom Truscott
- 2 months, 3 weeks ago

Aha, see “binary Euclid’s algorithm”. A sort-of backwards version of that solves 2020,2021 in 35 steps! Hint: start each step by finding which of A,B, or both have the lowest 1-bit. A proof that the algorithm always terminates would be welcome.

Tom Truscott
- 2 months, 3 weeks ago

A+=B

B+=A

As the addition is commutative

2 Helpful
0 Interesting
2 Brilliant
3 Confused

After the first operation, value of A has already changed. The question is specifically related to Computer Science, not Algebra.

Prakash Arora
- 3 months, 1 week ago

It's simple Add A, B no. of times and add B, A no. of times.

A×B=AB=B×A

A+=A........B no. of times

B+=B.........A no. of times

0 Helpful
0 Interesting
0 Brilliant
0 Confused

Find lcm or if one or both are prime then multiple both that'll be the way

0 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

Do 3rd operation 2021 times ( $=2020\times2021$ ) and 4th operation 2020 times ( $=2021\times2020$ )

In general, do 3rd operation ( $\frac{gcd(A,B)}{A}$ ) times and 4th operation ( $\frac{gcd(A,B)}{B}$ ) times