I randomly came up with this problem and tried to solve it, but unfortunately, I couldn't.
The problem is:
Given an array of length $$$n \geq 2 $$$ of positive integers, is it possible to make all elements equal doing the following operation any number of times (possibly zero)? In one operation we can pick any two different indices $$$i, j$$$ multiply $$$a_i$$$ by $$$2$$$, and add $$$1$$$ to $$$a_j$$$.
I've tried to bruteforce arrays of length $$$2$$$ up to $$$20$$$. $$$[1, 2]$$$, $$$[1, 3]$$$, $$$[1, 4]$$$, $$$\dots$$$ $$$[19, 20]$$$, and it is possible to make all elements equal. The question is: Is the answer for this problem always "YES" for any $$$n \geq 2$$$?
It is interesting problem indeed.
I spent a few minutes on it and came up with a solution for $$$n = 2$$$. I claim that the following algorithm works.
Let our numbers be $$$a$$$ and $$$b$$$. Add $$$1$$$ to $$$a$$$ until it is a prefix of $$$b$$$.
Let $$$b$$$ be $$$a$$$ concatenated with some string $$$c$$$. While $$$a$$$ is still a prefix of $$$b$$$, multiply $$$a$$$ by two and, if the first character of $$$c$$$ was not zero, add $$$1$$$ to $$$a$$$. Informally speaking, here we greedily add characters of $$$b$$$ one by one.
Repeat previous steps until success.
The second step has a problem: when we multiply $$$a$$$ by two, we can mess part of the already matched prefix. However, after repeating the first step, $$$c$$$ would have a form of a huge number of zeroes with the number $$$10$$$ in the end. It is easy to see that the next round of our algorithm would make $$$c$$$ roughly equal to the logarithm of its old length (thus, much shorter). And if the bad carry did not happen, we may see that after we process the whole string $$$c$$$, the "next" $$$c$$$ would be like the same number, but with each old zero corresponding to the addition followed by multiplication, and each one corresponding to single addition. And since the number of ones in any string is not greater than the number of all characters, the "new" $$$c$$$ would be smaller than the old one. Here "smaller" means not longer, and if the length is the same, then strictly smaller lexicographically.
In order to complete the proof, we also need to do some casework with short $$$c$$$ (I would say, of lengths up to $$$3$$$). I am lazy to do that, but I believe that it everything should be fine, because of the bruteforce.
It is also easy to see that the solution for $$$n = 2$$$ gives us a solution for all $$$n = 2^k$$$, because we can split numbers in pairs, solve the problem in pairs, and then solve the problem on the halved array twice (for the first numbers on each pair and then for the second numbers).
If $$$n$$$ is not a power of two, then, I think, the problem is also solvable, but much less elegant.
Wait, the statement says you have to do $$$(+\ 1)$$$ and $$$(\times\ 2)$$$ both simultaneously in one operation. Moreover, it is not allowed to have $$$i = j$$$.
Or am I missing something?
We look at their binary notation, so prefix doesn't change when we multiply by 2.
I think you are right.
I think, you are missing something. Yes, I didn't write explicitly that whenever I do some operation to one number, the second one is automatically applied to another.
However, it seems like clyring is right and the proof is indeed contains a flaw. Fortunately, he also fixed the problem with the additional casework (apparently, I did not check it yet). Thanks to him!
I don't understand your argument for why $$$c$$$ is decreasing, but it definitely contains a mistake. Consider $$$c = 1110$$$, and choose $$$x$$$ so that initially $$$(a,b) = (x, x1110)$$$. Then, your strategy first goes to $$$(a,b) = (x0, x1111)$$$ and then to $$$(a, b) = (x1, x11110)$$$, and again $$$c = 1110$$$. (This works for any number of ones followed by a zero.)
Here's a slightly modified version with a more explicit proof of correctness:
To keep the wordiness manageable, let an operation X mean adding one to $$$a$$$ while doubling $$$b$$$, and an operation Y mean adding one to $$$b$$$ while doubling $$$a$$$.
Let $$$k = \mathrm{length}(c)$$$, and suppose $$$k \geq 3$$$. Then, one of the following four strategies can reduce $$$k$$$.
1: If $$$c$$$ consists only of ones, we may perform operations X, Y, Y in that order. Then, $$$a_{\text{new}}$$$ is $$$a_{\text{old}} + 1$$$ followed by two zeros, while $$$b_{\text{new}}$$$ is $$$a_{\text{old}} + 1$$$ followed by $$$1 + k_{\text{old}}$$$ zeros. So, $$$a$$$ is still a prefix of $$$b$$$, and $$$k$$$ has decreased by one.
Otherwise, $$$a$$$ is also a prefix of $$$b + 1$$$, since no carry can happen while adding one. So, let $$$d$$$ be the string such that $$$a$$$ concatenated with $$$d$$$ is equal to $$$b + 1$$$. Notice that $$$c$$$ and $$$d$$$ have the same length.
2: If $$$d$$$ has a leading zero, we may perform one operation Y, and $$$c_{\text{new}}$$$ consist of all but the first bit of $$$d$$$. This decreases $$$k$$$ by one.
3: Otherwise, if $$$d$$$ contains at least one zero, we may perform operations Y, then X. Then, $$$c_{\text{new}}$$$ consists all but the first bit of $$$d_{\text{old}}$$$, followed by a $$$0$$$. So, $$$c_{\text{new}}$$$ is not all ones and $$$d_{\text{new}}$$$ is exactly $$$d_{\text{old}}$$$ rotated left by one bit. Since $$$d$$$ contains at least one zero, repeating these operations will eventually rotate a zero into the leading position, and we can then use strategy 2 to reduce $$$k$$$ by one.
4: Otherwise, $$$d$$$ consists only of ones. Then, performing two operations $$$Y$$$ will make $$$b$$$ become with $$$a_{\text{old}} + 1$$$ followed by $$$k_{\text{old}}$$$ zeros, and $$$a$$$ consist of $$$a_{\text{old}}$$$ followed by two zeros. Next, perform four operations X to make $$$a$$$ consist of $$$a_{\text{old}} + 1$$$ followed by two zeros and $$$b$$$ consist of $$$a_{\text{old}} + 1$$$ followed by $$$k_{\text{old}} + 4$$$ zeros. Finally, perform three operations Y. $$$a_{\text{new}}$$$ consists of $$$a_{\text{old}} + 1$$$ followed by five zeros, while $$$b_{\text{new}}$$$ consists of $$$a_{\text{old}} + 1$$$ followed by $$$k_{\text{old}} + 2$$$ zeros followed by two ones. Since $$$k_{\text{old}} \geq 3$$$, $$$k_{\text{old}} + 2 \geq 5$$$, and so $$$a_{\text{new}}$$$ is a prefix of $$$b_{\text{new}}$$$, and the difference in their lengths (equal to the length of $$$c$$$) has decreased by one.
A short brute-force script I wrote shows how to finish off each small $$$c$$$:
$$$0$$$ -> XYYYYXYXX
$$$1$$$ -> XYY
$$$00$$$ -> YXYY
$$$01$$$ -> YXYXYY
$$$10$$$ -> XYYYYYXXXXYXYY (Yes, really. At least 14 operations are needed.)
$$$11$$$ -> YXXYYXYXYY
Indeed the answer is yes for any $$$n$$$. nikgaevoy already briefly described above how to use a solution for $$$n = 2$$$ to lift a solution with problem size $$$n$$$ to a solution with problem size $$$2n$$$. (See also this beautiful related problem: 1408F - Two Different) That leaves only the matter of solving the problem for odd $$$n$$$. But it turns out that there is a solution for odd $$$n$$$ that is no less elegant. Indeed, it only needs two tools and has no case-work!
The first tool is that repeatedly doubling $$$a_1$$$ without regard for how large it gets enables essentially complete control over $$$a_2$$$ through $$$a_n$$$, since they can be stepped (+1) by (+1) up to any desired value.
The second tool is performing operation $$$(i, j)$$$ and then operation $$$(j, i)$$$. This updates $$$(a_i, a_j)$$$ to $$$(2a_i+1, 2a_j+2)$$$, which is equivalent to doubling both $$$a_i + 1$$$ and $$$a_j + 2$$$. This is almost a clean, no-mess doubling of two entries at a time, which makes it easy to work around the large powers of two generated by the first tool.
Putting it all together: Start by choosing some large enough $$$k$$$ and then repeatedly doubling $$$a_1$$$ and incrementing the other entries until half are equal to $$$2^k \cdot a_{1, \text{initial}} - 1$$$ and the other half are equal to $$$2^k \cdot a_{1, \text{initial}} - 2$$$. Then, use the second tool to inflate up one pair at a time until $$$a_2$$$ through $$$a_n$$$ are all equal to $$$2^{3 \cdot \lfloor \frac{n}{2} \rfloor} \cdot a_1$$$ minus either 1 or 2. Finally, double $$$a_1$$$ exactly $$$3 \cdot \lfloor \frac{n}{2} \rfloor$$$ times to get rid of all the "minus either 1 or 2" happening in $$$a_2$$$ through $$$a_n$$$.
nikgaevoy clyring That's really interesting, thanks to you for working on the proof.