Dharmath Vader: Matching Binary String

Tuesday, November 17, 2009

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.

Dharmath Vader