Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

tfgs's blog

Interesting Problem About Deleting Adjacent Characters in a Binary String
By tfgs, history, 6 hours ago, In English

You're given a binary string. You can delete two equal adjacent characters however many times you like. Is it true that no matter how you delete adjacent characters, there is a unique shortest string that you can end up with?

I've been stuck on this for a while now. I suspect that the answer is yes, but I have no idea how to prove it. Please help me prove or disprove.

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

»
6 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

noone solves these hard things

→ Reply
»
6 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

Go touch some grass, bro. The obvious counter example is 001 in which you can end up with both 0 and 1 at the end.

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Sorry, I forgot to mention they need to be equal.

    → Reply
»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Idk why but this lowkey feels AI generated

→ Reply
»
83 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Final string will match regexp 0?(10)*1?. After all pairs of 00 and 11 eliminated total length will be the same. To make both 1010... and 0101... from same string by deleting pairs is impossible

→ Reply
  • »
    »
    62 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I agree that the final string either looks like 0101... or 1010..., but didn't understand your reasoning for why 0101... and 1010... from the same string is impossible. What do you mean that "total length will be the same"? Length of what object?

    → Reply
    • »
      »
      »
      50 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think he means the total length of the final string.

      → Reply
»
50 minutes ago, # |
  Vote: I like it +2 Vote: I do not like it

The answer is yes. Proof:

The only two possible resulting strings are 1010... and 0101... Consider a reversal of the process: starting with the end string and adding pairs of adjacent characters to produce the original string. It is impossible for to produce the same string from both of these resulting strings, so only one of them is a possible result.

→ Reply
  • »
    »
    18 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why is it impossible to produce the same string from 0101... and 1010... by adding 00s and 11s?

    → Reply
»
24 minutes ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Flip every character on an even position, now the problem is that the operation is removing 10 or 01(since you're removing 2 characters at a time all other parities of positions are preserved, so doing this operation is just removing a 01 or 10 without the rest of the string being affected). You can always do that until the string is all 0s or all 1s. Let's say there are $$$x$$$ zeroes and $$$y$$$ ones in the new string. If $$$x>y$$$, the answer to the original problem is 01010... of length $$$x-y$$$, if $$$x<y$$$ it's 10101... of length $$$y-x$$$.

→ Reply