Lesson 15-2: Regular Polygons and Schedules (Day 152)

Chapter 8 of Wayne Wickelgren's How to Solve Problems is called "Working Backward." Here's how it begins (and no, I won't read the chapter backward and start with the end instead):

"The method of working backward is similar to the method of contradiction (Chapter 7) and the method of drawing inferences about the goal (Chapter 3) in that all three focus on the goal to a great extent and consider it rather than the givens as the starting point for the problem-solving process. However, working backward differs in the way the goal is considered in relation to the givens."

Wickelgren explains the process further:

"We start at the end point and try to determine preceding statements, which need not necessarily be given statements but which, when taken together, will produce the goal."

And he tells us why it ultimately works:

"Nevertheless, the method is frequently very useful in such problems, because the unique starting point so frequently directs you to just those aspects of the given information that are relevant to the solution."

Wickelgren tells us to be careful when working with binary operations -- that is, operations that combine two or more inputs to obtain an output:

"A conjunction of inputs is related to a single output statement with binary or ternary operations, and this is equally true working forward or backward."

He also warns us that working backward is often more difficult than working forward, but:

"Nevertheless, there is a large class of problems to which the method of working backward is appropriate, and some examples are given in the following section."

But before we get to the examples, let me post some Square One TV music. As luck would have it, the Fat Boys produced three songs for the show, and one of them is called "Working Backwards." So this would be the perfect song to post today.

But unfortunately, only the other Fat Boys songs, "One Million Is Big" and "Burger Pattern," are posted on YouTube as separate songs. Thus I must post a full Square One TV episode. Even though the song is the first skit of the episode, several commercials are posted (for nostalgic reasons) before the opening theme song. So you might wish to skip to 3:14 for "Working Backwards":

Notice that the beginning of the video has a scene from "One Billion Is Big" (the headline "Fat Boys Sell One Million Records.") Oh. and by the way, I like the part where the three backup girls start singing the refrain. They come in dancing -- backwards, of course!

As far as I know, neither Barry Carter nor anyone else has recorded the lyrics for this song. So let me write down the lyrics to the best of my ability:

WORKING BACKWARDS
Sung by the Fat Boys

1st Verse:
Tonight our show begins at ten,
There's a lot we got to do 'til then.
We gotta rehearse, we gotta eat,
Put our makeup on and find time to sleep.
What time do we need to start?
Let's take the backwards day apart.
Working backwards, we'll figure it out,
And show the world what we're all about!

Refrain:
Working backwards is the way,
To solve this problem, working backwards.
Working backwards is the way,
To solve this problem, working backwards!

2nd Verse:
*We got part of the day to fix our hair,
We need a half hour in the makeup chair.
They start their job at nine-thirty,
What time do we eat, my friend Markie Dee?
Thirty minutes is all it takes,
To eat a salad, to share a steak.
So tell the chef dinner starts at nine,
Working backwards is working fine!

(repeat refrain)

3rd Verse:
We need to nap before we eat,
About forty-five minutes of catching Z's.
We gotta rest, I hear my drum machine,
The lights go out at eight-fifteen.
We can't forget rehearsal time,
An hour and a quarter for beats and rhymes.
So rehearsal starts at seven o'clock,
Beat box, tell me, what time have you got?
Let's see -- my watch says seven o'clock already,
Wow, we better get moving right now!

(repeat refrain)

*This is the only line I'm not sure about. The lead rapper is saying something about fixing the hair -- I wonder whether he's saying "part of the day" (which is what this song is all about) or whether he's actually giving the names of his hair stylists. Maybe "day" is actually "Fay" or "Kay," but I can't be sure of the other name. Unfortunately, I don't know who the Fat Boys' hair stylists are.

Here's another Square One TV show about problem solving -- "Point of View":

This time, Barry Carter does provide the song lyrics:

http://wordpress.barrycarter.org/index.php/2011/06/10/square-one-tv-point-of-view-lyrics/#.WuE0AIjwaUk

CHANGE YOUR P.O.V.
Sung by Obelisk/Larry Cedar
Produced by Outlook/Inlook

Narrator (Larry Cedar): “In a far away bazaar, Tracy and Jeff try to solve the mystery of hieroglyphics, but right now, they’re caught up in an intense game of chess…”

I don’t know the facts of your problem.
I don’t know the details involved.
But one thing that problems have all got in common
Is more than one way to be solved.

Change your point of view.
Look at the problem in a way that’s fresh and new.
Strange, but yes it’s true.
You will never be stumped if you change your point of view.

Jeff to Tracy: “Maybe he can help us decode the hieroglyphics!”

If you’re stuck on a word problem,
Why not try and act it out?
Go through each step using objects.
Soon you’ll see what it’s about.

Sometimes it helps to work backwards,
Just like re-tracing your path.
Life is the pits boy, but don’t have a snit boy.
We’ll find a solution with math.

Change your point of view.
Look at the problem in a way that’s fresh and new.
Strange, but yes it’s true.
You will never be stumped if you change your point of view.

If it’s a difficult problem,
Try and solve an easy one.
Simpler but similar problems,
Help you see just how it’s done.

Try to discover a pattern.
Dare to jump into the mess.
Look for relations,
And try combinations,
And boldly come up with a guess.

A graph makes things clearer.
It might get you nearer your goal.
Or draw up a chart,
Or tackle just part of the whole.

But change your point of view.
Look at the problem in a way that’s fresh and new.
Strange, but yes it’s true.
You will never be stumped if you change your point of view.
You will never be stumped if you change your point of view.
You will never be stumped if you change your point of view.

Oh, notice the first line of the fourth stanza -- "Sometimes it helps to work backwards." So let's finally start working backward and look at Wickelgren's first problem, the doubling-game problem:

Three people play a game in which one person loses and two people win each game. The one who loses must double the amount of money that each of the other two players has at the time. The three players agree to play three games. At the end of three games, each player has lost one game and each person has $8. What was the original stake of each player?

The author informs us that working backward is the perfect way to solve this problem. So he labels the three losers P_1, P_2, and P_3, and then he makes a chart.

                        P_1  P_2  P_3
End of game 3 $   8 $   8 $   8
End of game 2      4      4    16
End of game 1      2    14      8
Beginning           13      7      4

"Note that if the players did not all end with the same amount of money, it would be impossible to determine what each player started with, because the order in which the players won and lost would make a difference."

Wickelgren's next example involves a variety of Nim games. The version in this book is often referred to as Static Nim. It's easy to find Nim games online. Even though Wickelgren's exact Nim game isn't  given at the following link, I'd rather cut-and-paste. The following link refers to a famous game of Static Nim played on the TV show Survivor:

http://math2.uncc.edu/~hbreiter/The%20Secret%20of%20NIM.htm

In the October 24, 2002 episode of the CBS television show "Survivor: Thailand," the two tribes were presented with a mathematically based Immunity Challenge. They faced a circle of 21 flags.  The two tribes had to take turns removing flags from the circle and they could either remove 1, 2, or 3 flags in each turn.  At the end of the game, called Thai 21 on the TV show, the tribe that took the last flag would win the challenge.  In the show, the Chuay Gahn tribe outsmarted the Sook Jai tribe. What is the mathematics behind this game and what is a successful strategy for winning? 

Stop reading and try to determine the optimal strategy by working backward. Here's the goal:

"If you conjecture yourself to be in the goal state, this state would clearly consist of being the [tribe] whose turn it is to move, and there being anywhere from one to [three flags in the circle.]"

In working backwards, here's the last step:

In the TV game, the teams drew straws to determine which team went first. Both teams seemed to have strategies, but a member of the Sook Jai team slipped up in the middle of the game and enabled the Chuay Gahn team to win.  The Chuay Gahn team apparently realized that they needed to leave exactly four flags remaining after their next to last move.  Then no matter how many (1, 2, or 3) flags the Sook Jai tribe took, there would be either 1, 2, or 3 flags for the Chuay Gahn tribe to take on their final move.  Therefore, the Chuay Gahn tribe's strategy was to make sure that they left exactly 4 flags in the circle after their next to last move.  

And here's the next-to-last step, which generalizes to a full game strategy:

To be sure they would be able to do this, the Chuay Gahn tribe needed to leave exactly 8 flags in the circle after their third to last move.  If they did this, then no matter how many (1, 2, or 3) flags Sook Jai tribe took, the Chuay Gahn tribe could then take 1, 2, or 3 to leave exactly 4 flags in the circle.  This pattern leads to the strategy for this game: "Leave a multiple of 4 flags at the end of each player's turn."

As Wickelgren puts it:

"The lesson in this problem is that you should not be too easily discouraged from working backward by a multiplicity of preceding states, if this multiplicity is only a temporary phenomenon or a one-time sprouting of branches of the tree followed by no further increase."

Let's skip to another problem that Brian Harvey discusses on his Logo page, the water jar problem:

http://people.eecs.berkeley.edu/~bh/v1ch14/pour.html

You are at the side of a river. You have a three-liter pitcher and a seven-liter pitcher. The pitchers do not have markings to allow measuring smaller quantities. You need two liters of water. How can you measure two liters?

Stop reading and try to solve the problem, working backward. Actually, Wickelgren's example has five liters (or quarts) as the goal state rather than two liters.

Notice that Harvey, at the Logo link, doesn't work backwards. Instead, he actually has Logo produce the entire state-action tree, except that it eliminates redundant steps in order to keep the size of the tree manageable. Let's follow Wicklegren, who works backwards, to achieve his goal of five quarts by listing the possible final steps:

1. 2 quarts in 7-quart jar, pour in 3 quarts from 3-quart jar
2. 3 quarts in 7-quart jar, pour in 2 quarts from 3-quart jar
3. 4 quarts in 7-quart jar, pour in 1 quart from 3-quart jar
4. 7 quarts in 7-quart jar/1 quart in 3-quart jar, pour 2 quarts from large to small jar
5. 6 quarts in 7-quart jar,/2 quarts in 3-quart jar, pour 1 quart from large to small jar

The author decides that the fourth option is best, and so his subgoal is to have 1 quart in a jar. Here is the final solution:

Pour from river to 7

Pour from 7 to 3

Pour from 3 to river

Pour from 7 to 3 [1 left in 7, subgoal achieved]

Pour from 3 to river

Pour from 7 to 3 [1 left in 3]
Pour from river to 7
Pour from 7 to 3 [5 left in 7]

As usual, I want to skip directly into the Geometry example. It is, in fact, to prove the Pythagorean Theorem (yes, the one I taught my class yesterday) using the following givens:

(1) the axioms of Euclidean geometry
(2) the definition of the area of a rectangular figure (length times width)
(3) the assumption that the areas of nonoverlapping figures are additive.

You might recall that there are two proofs of the Pythagorean Theorem given in Geometry classes -- those based on similarity (as endorsed by the Common Core), and those based on area (such as the one given in the U of Chicago text). A quick glance at givens 2 and 3 (essentially the Area Postulate of Lesson 8-3) hints that an area-based proof is desired. And congratulations -- you just worked backwards to discover the last step of the proof (namely, that the area of the square with side c is the sum of the areas of the squares with sides a and b).

But Wicklegren's proof is different from that given in the U of Chicago text -- and I can't even find it among the 122 proofs of the theorem given at the Cut the Knot website!

His trick is to let T be the area of the original triangle. Assuming that a is the longer leg, then the area of the square on a is 2T plus an extra rectangle a(a - b). No triangle fits in the square on b, the shorter leg, but if we extend the square by a rectangle b(a - b), then two triangles fit. So the sum of the two squares on the legs is:

a^2 + b^2 = 4T + a(a - b) - b(a - b) = 4T + (a - b)^2

Then the author fits four triangles and a square (a - b)^2 inside of the triangle on c -- a step which is more commonly done in Pythagoras proofs, such as Proof #3 at Cut the Knot:

https://www.cut-the-knot.org/pythagoras/index.shtml

The difference between Wickelgren and Proof #3 is that the latter requires the area of the triangles to be known, while Wicklegren's proof could be given directly after Lesson 8-3 of the text.

The last problem in the text is repeated from Chapter 2:

You are given a mathematical system consisting of a set of elements (A, B, C) with two binary operations (call them addition and multiplication) that combine two elements to give a third element. The system has the following properties:

(1) Addition and multiplication are closed.
(2) Multiplication is commutative.
(3) Equals added to equals are equal.
(4) The left distributive law applies; that is, C(A + B) = CA + CB for all A, B, C in the set.
(5) The transitive law also applies.

From these given assumptions, you are to prove the right distributive law -- that is, that (A + B)C = AC + BC, for all A, B, C in the set.

The working backwards step is (A + B)C = X and X = AC + BC, so that property (5), the transitive law, can be used to obtain the goal. As it turns out, this is easy -- property (2), the commutative law, allows us to write (A + B)C = C(A + B). Then we use the left distributive law (3) to obtain CA + CB, which we can rewrite using the commutative property as AB + BC:

"Thus, (A + B)C = AC + BC, by the transitive law for equality, and the theorem is proved."

This is what I wrote last year about today's lesson:

Lesson 15-2 of the U of Chicago text is called "Regular Polygons and Schedules." Just like Lesson 13-3 from last month, 15-2 naturally lends itself to an activity, so this will be considered the activity for this week.

The text defines a round-robin tournament as a tournament in which each competitor (or team) plays each other competitor exactly once. True round-robins are rare at the highest levels of sports. The first two rounds of the World Baseball Classic and first round of the World Cup (of soccer) divide the field into groups of four nations each, and each group is played as a round-robin tournament. After the first two baseball rounds or first soccer round, the tournaments become single-elimination instead.

On the other hand, round-robin regular seasons are fairly common in high school sports. During football season, every team in the league plays every other team. It might be easy to schedule the four-team round-robins by hand, but the school from which I graduated is in a seven-team league. So the U of Chicago text provides a method of complete a seven-team round-robin:

1. Let the 7 teams be vertices of an inscribed regular 7-gon (heptagon).

2. Draw a chord and all chords parallel to it. Because the polygon has an odd number of sides, no two chords have the same length. This is the first week's schedule.

3. Rotate the chords 1/7 of a revolution. This is the second week's schedule.

4. Continue rotating 1/7 of a revolution for each week. Because in a week no two chords have the same length, no pairing repeats. In a total of seven weeks, the schedule is complete.

Here is the resulting schedule as given by the U of Chicago text:

1st week: 7-2, 6-3, 5-4, 1 bye

2nd week: 1-3, 7-4, 6-5, 2 bye

3rd week: 2-4, 1-5, 7-6, 3 bye

4th week: 3-5, 2-6, 1-7, 4 bye

5th week: 4-6, 3-7, 2-1, 5 bye

6th week: 5-7, 4-1, 3-2, 6 bye

7th week: 6-1, 5-2, 4-3, 7 bye

In my alma mater's league, from one year to another, the home games become away games and vice versa, and then the schedule itself rotates so that the first week match-ups are contested the second week, the second week match-ups are contested the third week, and vice versa. Many of the stronger teams don't actually take the bye week -- instead they play special games against out-of-state teams.

If there are an even number of teams, then the extra team is placed at the center, and a radius is drawn in addition to the chords -- this replaces the bye week. For example, we can add an eighth team to the list above by having the eighth team play the team with the bye.

Here is the activity. Students should begin by cutting out the circle, drawing the parallel chords, and leaving the numbers where they are, so that the circle can be rotated to match up with the numbers.