We are given two binary strings $A$ and $B$ each of length $2n$. Both strings contain equal number of ones and zeros to each other. We write $A$ on top of $B$, so that each element of $A$ is paired with each element of $B$ at the corresponding position.
We call the two strings a "match" if there are at least $n$ common elements where the element of $A$ at a certain position matches that of $B$ at that position.
Prove that, we can cyclically shift $B$ a number of times (and wrap around at the end/beginning) so that $A$ and $B$ form a match.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment