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?
Labels:
Combinatorics,
expected value,
probability,
Random,
sequence,
string
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.
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:
Posts (Atom)