A+=B

Computer Science Level 1

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

4 solutions

Lingga Musroji
Feb 22, 2021

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

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

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

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

Alice Smith - 2 months, 4 weeks ago

@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

Parth Maniyar
Mar 1, 2021

You can make any two non negative numbers equal by using This operation one time only
A+=B
B+=A
As the addition is commutative

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

Yash Jain
May 20, 2021

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

Jeel Vachhani
Mar 26, 2021

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

A+=B

4 solutions

0 pending reports