MathDB

8

Part of 2017 CMIMC Team

Problems(1)

2017 T8: Strings Determined by Flipping Coins

Source:

1/29/2017
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.
2017team