Interesting Problem About Deleting Adjacent Characters in a Binary String

Revision en1, by tfgs, 2025-03-14 20:21:09

You're given a binary string. You can delete two 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.

Tags math, proofs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English tfgs 2025-03-14 22:45:17 10 Tiny change: 'elete two adjacent ' -> 'elete two **equal** adjacent '
en1 English tfgs 2025-03-14 20:21:09 440 Initial revision (published)