MathDB
2017 T8: Strings Determined by Flipping Coins

Source:

January 29, 2017
2017team

Problem Statement

Alice and Bob have a fair coin with sides labeled CC and MM, and they flip the coin repeatedly while recording the outcomes; for example, if they flip two CC's then an MM, they have CCMCCM recorded. They play the following game: Alice chooses a four-character string A\mathcal A, then Bob chooses two distinct three-character strings B1\mathcal B_1 and B2\mathcal B_2 such that neither is a substring of A\mathcal A. Bob wins if A\mathcal A shows up in the running record before either B1\mathcal B_1 or B2\mathcal B_2 do, and otherwise Alice wins. Given that Alice chooses A=CMMC\mathcal A = CMMC and Bob plays optimally, compute the probability that Bob wins.
Back to ProblemsView on AoPS