MohamedMagdy's blog

By MohamedMagdy, history, 3 years ago, In English

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$$$?

  • Vote: I like it
  • +80
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

  1. Let our numbers be $$$a$$$ and $$$b$$$. Add $$$1$$$ to $$$a$$$ until it is a prefix of $$$b$$$.

  2. 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.

  3. 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      We look at their binary notation, so prefix doesn't change when we multiply by 2.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      In one operation we can pick any two different indices $$$i,j$$$ multiply $$$a_i$$$ by $$$2$$$, and add $$$1$$$ to $$$a_j$$$.

      I think you are right.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    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:

    Spoiler
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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$$$.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

nikgaevoy clyring That's really interesting, thanks to you for working on the proof.