Consider the following game involving a deck of cards. We are only concerned abo

Question

Consider the following game involving a deck of cards. We are only concerned about the color of the
cards, red and black; we ignore the suits and the denominations. The rules for a given game are
sequences of “R”s and “B”s corresponding to red and black cards. For example, one game has the three
rules: (1) BB, (2) RR, and (3) BRBR. The object of the game is to see if you can use the rules to
transform a starting sequence to a goal sequence. At stages along the way, you can apply the rules as
follows, as many times as you wish: you can insert the sequence corresponding to the rule anywhere in
your current sequence (and you always have enough cards to do this as many times as you would like),
or you may remove the sequence corresponding to the rule from your current sequence. For example,
we can transform the starting sequence RB to goal sequence BR as follows. From RB we can use Rule
(1) to insert BB at the beginning and get BBRB, and then use Rule (2) to insert RR on the end, resulting
in BBRBRR. Applying Rule (3) to this last sequence we can remove the four cards in the middle to get
BR, so we have gone from RB to BR in three steps using each rule once.

a) Suppose the rules are (1) BB, (2) RRR, and (3) RRBRB. Show that you can go from RB to BR,
but you cannot go from R to B.

b) Suppose the rules are (1) BB, (2) RRR, (3) RBRB. Show that you cannot go from RB to BR.
c) For each set of rules in part a) and b), show that every sequence can be transformed into one of
the following six, (), B, R, RR, BR, BRR, where () is the “empty sequence” (an empty hand of
cards).

d) Show that for both the rules in part a), and for the rules in part b), for any sequence x1, x2, x3, ..., xm
there is another sequence y1, y2, y3, ... yn such that x1, x2, x3, ..., xmy1, y2, y3, ... yn can be eliminated
completely by the rules, resulting in ().

Explanation / Answer

For a, count the number of Rs and Bs in each rule. You can never add or subtract letters in any increment except that number. If you start with 1 R and 0 Bs, is it possible to end up with 0 Rs and 1 B?

For b, I don't know the answer specifically, but the thing that jumps out at me is that (2) has 3 Rs, and (3) only has 2. That means that you have to use the rules a different number of times in order to maintain 1 R and 1 B. 2x(2) for every 3x(3). I wonder if you can use that?

For c, try thinking of applying modular arithmetic to the problem. I can think of the sequence BBBBRRRRBBBB as 4B 4R 4B. Using the rules from a, I know that I can reduce this easily using rules (1) and (2), eliminating the Bs completely and eliminating all but 1 R. So... Any even numbered chain of Bs can be eliminated completely, and any odd numbered chain can be reduced to 1B. Similarly, a chain of Rs can be reduced to either 0R, 1R, or 2R. So you don't have to worry about any scenario where B > 1 or R >2.

Now, you can break your chain down into a sequence of segments that are either BR or BRR. Pairs of adjacent sequences will either be BRBR, BRBRR, BRRBR, or BRRBRR. Can you find ways to reduce those sequences even further? Off the top of my head, I found BRBR => RR, BRRBR => 0, BRBRR => 0, and BRRBRR => R. Thus, any chain can be reduced to a sequence of Rs, which will be at most 2R (after using rule (2) to reduce it again).

You still have to consider the ends of your chain, though. You might have some tail at the beginning or end that was not long enough to form one of the sequences we reduced.

Please ask if you have further quaries. thanks

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.