Pages

Bookmark and Share
Showing posts with label string. Show all posts
Showing posts with label string. Show all posts

Thursday, January 21, 2010

Drawing letters

A string of alphabets are randomly generated one letter at a time. Each time, one obtains the letter $A,\cdots,Z$ with probability $p(A),\cdots, p(Z)$. Given that the sum of these probabilities is 1, what is the expected number of draws before the string "DHARMATH" appears?

Tuesday, November 17, 2009

Matching Binary String

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.