Game Show Problem

Game Show Problem Jacob Richey August 31,2009 Problem: You are on a game show. You start with a score of 0 points. You are then asked a series of questions. For each correct answer (C), your score is increased by 1, and for each incorrect answer (I), your score is divided by 2. After answering 𝑛 questions, how many distinct scores are possible? Solution: Let 𝑠 be a sequence of correct and incorrect answers and 𝑥𝑠 or 𝑠𝑥 be a sequence of answers 𝑥 added to the beginning or end of 𝑠. (For example, 𝐼𝑠𝐶𝐶 represents incorrectly answering, then answering according to 𝑠, then answering correctly twice.) Let 𝑠′ be the score of a sequence 𝑠. (For example, (𝐶𝐼𝐶)′ = 23 .) Let 𝐺𝑛 be the set of all sequences of length n with distinct value. Define a pair of transformation sequences to be two distinct sequences 𝑥 and 𝑦 both applied to some arbitrary sequence 𝑠. Then a pair of repeat transformations is one where (𝑠𝑥)′ = (𝑠𝑦)′ for all s. Finally, define a repeat to be two sequences 𝑎 and 𝑏 of equal length so that 𝑎′ = 𝑏′ . Claim: ∣𝐺𝑛 ∣ = 2∣𝐺𝑛−1 ∣ − ∣𝐺𝑛−3 ∣ with 𝐺0 = 1, 𝐺1 = 2 and 𝐺2 = 4. Lemma 1: (𝐼𝑠)′ = 𝑠′ . If a sequence begins with an incorrect answer, then the score after that answer is unchanged since 02 = 0. Trivially, we can add any number of 𝐼’s to the beginning of any sequence 𝑠 without changing its value. Lemma 2: 𝐶𝐶𝐼 and 𝐼𝐶 are a pair of repeat transformations that give rise to exactly 𝐺𝑛−3 repeats of length 𝑛. Also, they are the only pair of repeat transformations of length less than four. ′ ′ Note that (𝑠𝐶𝐶𝐼)′ = (𝑠𝐼𝐶)′ because 𝑠 +1+1 = 𝑠2 + 1, which holds for all 2 s. By Lemma 1, we also have that (𝑠𝐶𝐶𝐼)′ = (𝐼𝑠𝐼𝐶)′ . Now, say the sequence 𝑠 is of length 𝑘 − 3. The number of different sequences 𝑠𝐶𝐶𝐼 or 𝐼𝑠𝐼𝐶 simply relies on how many ways we can choose 𝑠; but, since it is of length 𝑘 − 3, we can choose it exactly ∣𝐺𝑘−3 ∣ ways. Thus, in producing 𝐺𝑘 recursively, we must exclude at least ∣𝐺𝑘−3 ∣ sequences. Now, to show that this pair of transformation sequences is unique among those with length less than or equal to 3, we simply need to write out all the possible transformations of lengths 0, 1, 2, or 3 on an arbitrary sequence 𝑠.

1

𝑘=0 𝑠 = 𝑠′ 𝑘=1 (𝑠𝐶)′ = 𝑠′ + 1 ′ (𝑠𝐼)′ = 𝑠2 𝑘=2 (𝑠𝐶𝐶)′ = 𝑠′ + 2 ′ (𝑠𝐶𝐼)′ = 𝑠2 + 12 ′ (𝑠𝐼𝐶)′ = 𝑠2 + 1 ′ (𝑠𝐼𝐼)′ = 𝑠4 𝑘=3 ′ (𝑠𝐶𝐶𝐼)′ = 𝑠2 + 1 ′ (𝑠𝐶𝐼𝐶)′ = 𝑠2 + 32 ′ (𝑠𝐶𝐼𝐼)′ = 𝑠4 + 14 ′ (𝑠𝐼𝐶𝐶)′ = 𝑠2 + 2 ′ (𝑠𝐼𝐶𝐼)′ = 𝑠4 + 12 ′ (𝑠𝐼𝐼𝐶)′ = 𝑠4 + 1 ′ (𝑠𝐼𝐼𝐼)′ = 𝑠8 The only two of these that have exactly the same value are 𝑠𝐼𝐶 and 𝑠𝐶𝐶𝐼; all the other pairs of expressions are equal either once or zero times, but certainly not always. Therefore, this pair of repeat transformations is unique among transformations of length less than or equal to 3. Lemma 3: Any pair of repeat transformations of length greater than 2 (aside from the 𝑠𝐶𝐶𝐼/𝐼𝑠𝐼𝐶 one) can be ignored, as they have all already been counted when considering repeats of 𝐺𝑛 of the form 𝑠𝐶𝐶𝐼/𝐼𝑠𝐼𝐶. Assume there is some pair of transformation sequences, 𝑥 and 𝑦, one of which is longer than three answers, that act on some sequence 𝑠 of length 𝑛 − 𝑘. Then the longer transformation sequence, suppose WLOG it is 𝑥, has length 𝑘 with 𝑘 ≥ 4. Now lets consider the partial transformation of 𝑥 on 𝑠 of total length 𝑛 − 3. (All but the last 3 answers of 𝑥 have been applied to 𝑠.) Let’s call this truncated sequence 𝑤. By Lemma 2, we know that the only way 𝑤 can always be a repeat in 𝐺𝑛 is if we apply the 𝐶𝐶𝐼/𝐼𝐶 transformation to it. Therefore, the one of the transformations 𝑥 and 𝑦 must end in 𝐶𝐶𝐼 and the other in 𝐼𝐶. However 𝑤 was constructed to begin with, it is a member of 𝐺𝑛−3 , and since it is a repeat of the desired form it was counted in our analysis in Lemma 2. Lemma 4: Any pair of transformations on an arbitrary sequence 𝑠 of length 2 or less, (i.e., the expressions listed above), that yield a positive solution for 𝑠′ , (as a negative score is impossible), have already been counted in the repeats given by the 𝑠𝐶𝐶𝐼/𝐼𝑠𝐼𝐶 repeat transformation pair.

2

We need only check all the pairs of two of the 7 transformations of length two or less, (i.e., all those in the above table under 𝑘 = 0, 𝑘 = 1 and 𝑘 = 2), and see if they have solutions that aren’t counted as 𝑠𝐶𝐶𝐼/𝐼𝑠𝐼𝐶 transformations. We 𝑑−𝑏 , note that the general solution to such an equation, 𝑎𝑠′ + 𝑏 = 𝑐𝑠′ + 𝑑 is 𝑠′ = 𝑎−𝑐 which is non negative only when 𝑑 ≥ 𝑏 and 𝑎 ≥ 𝑐 or 𝑑 ≤ 𝑏 and 𝑎 ≤ 𝑐. We also note that when the coeffecients of 𝑠′ are equal the equation has no solution, and when the transformation includes no correct answers, (i.e., 𝑏 = 𝑑 = 0), the solution is zero, which is never a repeat as it can only be generated in one way, namely as a sequence of incorrect answers. This eliminates all but two equations: 𝑠 = 2𝑠 + 1 and 𝑠 = 2𝑠 + 21 , whose solutions are 2 and 1, respectively. These give the equalities (𝐶𝐶)′ = (𝐶𝐶𝐼𝐶)′ and (𝐶)′ = (𝐶𝐶𝐼)′ . However, we note that both of these expressions are special cases of the equality (𝐼𝐶𝑥)′ = (𝐶𝐶𝐼𝑥)′ , with perhaps some 𝐼’s added at the front to balance their lengths. (They could be re-written as (𝐼𝐼𝐶𝐶)′ = (𝐶𝐶𝐼𝐶)′ and (𝐼𝐼𝐶)′ = (𝐶𝐶𝐼)′ .) Therefore, they were counted in our analysis in Lemma 2, and add no additional repeats. Proof of Claim: To recursively define 𝐺𝑛 , note that for each successive 𝑛 we can attach either a correct or an incorrect answer to the end of any sequence in 𝐺𝑛 . However, we must subtract off all the new repeated values we get in 𝐺𝑛+1 , and by the above analysis there are exactly ∣𝐺𝑛−2 ∣ of those cases. Therefore ∣𝐺𝑛+1 ∣ = 2∣𝐺𝑛 ∣ − ∣𝐺𝑛−2 ∣, which is the desired result. Note: In general, 𝐺𝑛 = 𝐹𝑛+2 − 1, where 𝐹𝑛 is the 𝑛th Fibonacci number and 𝐹1 = 1, 𝐹2 = 1.

3