Activity: The Centauri Challenge (Day 26)

The following activity is another one from Michael Serra's text -- it appears in his Chapter 15, since this one often goes with two-column proofs (and proofs appear in his book late). In this activity, strings consisting of the letters P, Q, R, and S are converted into others using four rules (that end up being our postulates):

Rule 1. Any two adjacent letters in a string can change places with each other. (PQ=>QP)
Rule 2. If a string ends in the same two letters, then you may substitute a Q for those two letters. (RSS=>RQ)
Rule 3. If a string begins in the same two letters, then you may add an S in front of those two letters. (PPR=>SPPR)
Rule 4. If a string of letters starts and finishes with the same letter, then you may substitute an R for all the letters between the first and last letters. (PQRSP=>PRP).

Then the text gives the following theorem, PQQRSS=>QRQ. (Notice that I chose to write "=>" where the text writes ">>" since, after all, we've already used the former to denote the hypothesis and conclusion of a conditional.)

Proof:
Statements            Reasons
1. PQQRSS          1. Given
2. PQQRQ            2. By Rule 2
3. QPQRQ            3. By Rule 1
4. QRQ                 4. By Rule 4

So for the students, this is a puzzle which gets them thinking about the logical structure of proofs without having to think about geometry.

The text calls this the "Centauri challenge," which I assume refers to Alpha Centauri, the closest star system to the sun. Notice that many of the Cooperative Problem Solving challenges in Serra are said to take place in a futuristic lunar colony. For this one, the inhabitants of this colony are trying to communicate with aliens from (Alpha) Centauri, but apparently, the Centaurian alphabet consists of only four letters.

My worksheet contains all of Challenge 1, then adds Challenge 2 as a Bonus. In case you're curious, here are my answers to Challenge 2.

1. Can you produce a string of five or more letters that cannot be reduced to RQ?

My answer is that I can't -- but now I must prove it. Here is my proof, in paragraph form:

Proof:
Our string has five letters, but there are only four letters available. So one of those letters must appear at least twice! (This is called the Pigeonhole Principle.) Let's call the letter that appears twice X. (I know, it's actually P, Q, R, or S, not X, but here I'm using X as a variable to stand for one of the letters P, Q, R, or S, since I want this proof to be as general as possible.)

Using Rule 1, we take the first appearance of X and change it with the letter on its left. Now take that X and change it with the new letter on its left. Keep doing this until the X is the first letter. Now take the last appearance of X and change it with the letter on its left. Keep doing this until this other X is the last letter.

Now our string begins with X and ends with X. So by Rule 4, it becomes XRX. Using Rule 1, we can change the first X and the R to obtain RXX. Finally, this string ends in the same two letters (whatever letter the X stands for), so by Rule 2, it becomes RQ. QED

After doing this, the second question becomes obvious.

2. One of the rules of Centauri can be removed without losing any of the first five theorems proved in Challenge 1. Which of the rules can be removed?

Look at which rules have been used in the post so far, and notice which one's missing. That's the rule that can be removed. I like the similarity between determining which theorems are provable with or without a certain rule, and finding out which theorems in geometry require a Parallel Postulate.

Here is the activity: