Thursday, January 28, 2021

Lesson 9-8: The Four-Color Problem (Day 98)

Today I subbed in an eighth grade science class. It's in my first OC district -- I've subbed at this school before, but not in this particular classroom. I will do "A Day in the Life" today as it's middle school -- and also because it's a science class. Yes, I'm returning to my old habit of comparing any middle school science class to what I taught (or failed to teach) at my old charter school.

8:30 -- This is the district where at middle schools, three periods meet in numerical order. But as it turns out, first period is the teacher's conference period.

Near the end of this period, a fire drill begins. Fortunately, there is no evacuation needed -- compare this to last week, when an evacuation occurred during my fourth period conference and students had to report to their first period class, so I suddenly had students.

9:40 -- Second period arrives. This is the first of two honors eighth grade science classes.

The students have a Go Formative quiz today. The regular teacher was hoping to set me up in her Go Formative for the day, but she can't -- that requires Formative Premium, which costs money. The same thing happened during my long-term assignment -- the regular teacher ended up giving me his password, since he doesn't have a premium account either.

The quiz is on Newton's Laws of Motion. Since these are honors students, most of them appear to finish the assessment quickly. The students have an online Equal and Opposite Reactions game to play, as well as a Bill Nye video on motion.

As I've been doing all week, I sing the Palindrome Song today. And I tell them that it's from Square One TV, a show that ended just before Bill Nye the Science Guy premiered in 1993. (Indeed, I suspect that my local TV station aired Bill Nye in the spot vacated by Square One TV.) Today's episode is actually the series finale, which first aired in 1998.

10:40 -- Second period leaves for snack break.

10:55 -- Third period arrives. This is the second of two honors eighth grade science classes.

It's just the luck of the draw that I get a conference followed by two honors classes today. There was also a sub yesterday, and he drew the three non-honors classes.

11:55 -- Third period leaves for lunch.

12:45 -- As is typical for this district, academic support begins. Students log into Zoom from home if they need extra help.

One girl does try to show up for support, but I miss her -- I only notice her comment in the Zoom chat a few minutes after she leaves. Then again, there's no guarantee I could have helped her anyway. (Of course she's not in the honors classes, so it's possible she had a question about her quiz tomorrow.)

2:00 -- Academic support ends, thus completing my day.

OK, let's compare this class to science at the old charter school. Like most science classes in California these days, this class uses the Preferred Integrated Model of the Next Generation Science Standards. I was at the charter school during the transition to the new standards, so the correct thing for me to do was teach Physical Science to eighth grade my first two years there. By my third year, the first Integrated cohort makes it to eighth grade -- but by then there's a separate science teacher. Then again, Newton's Laws count as Physical Science, and so it's likely that I would have taught this to eighth grade each year anyway.

In the classroom, I find texts for the four units taught in Integrated Science 8, albeit in Spanish. I use Google to translate the names of these four units:

1. Change over Time

2. Energy and Movement

3. Understand the Waves

4. Human Beings and Their Place in the Universe

The texts are titled California Inspire Science, published my McGraw-Hill. Notice the irony here -- for the first few years of NGSS, the district had no science texts for the new standards, and so science teachers had to cover the whole curriculum online. And now the new science texts are finally here -- right when the pandemic begins.

The first unit is all about how our planet changes over time, as well as evolution of species. The second and third units are Physical Science -- the second unit was clearly taught to eighth graders both before and after the dawn of NGSS, but the unit on waves is fairly new. And as I've mentioned on the blog before, the last unit on astronomy was once taught to sixth graders as part of pre-NGSS Earth Science.

At my old charter school, if I followed the Illinois State text, then I would have taught the four main units of Physical Science as listed in the NGSS to my eighth graders. These four units are:

1. Matter

2. Motion

3. Energy

4. Waves

That's right -- energy and movement count as one unit in Inspire but two units in Illinois State. And with motion being the second unit for both Inspire and Illinois State, I would have reached it around the same time as this district -- just after Thanksgiving.

Here's what the motion unit would have looked like at the old charter school -- including the science projects that appeared in the Illinois State text. This schedule follows the four-week cycle that I suggested in previous science posts:

Week of November 28th, 2016 -- MS-PS2-1: Apply Newton's Third Law .. (Unit 4 Science Test covering standards MS-PS1-6 and 2-1)

Week of December 5th -- Science Projects (Water Bottle Rocket, Egg Crash Box)

Week of December 12th -- MS-PS2-2: Plan an investigation to .. forces ..

Week of January 10th, 2017  -- Science Projects (create your own forces project)

Week of January 17th -- MS-PS2-3: Ask questions about .. magnetic forces (Unit 5 Science Test covering standards MS-PS2-2 and 2-3)

Week of January 23rd: Science Projects (How can electricity cause magnetism?)

Week of January 30th: MS-PS2-4: Construct and present arguments .. gravitational ..

Week of February 6th: Science Projects (How do forces act on objects? Weight on Other Planets)

Week of February 13th: MS-PS2-5: Conduct and investigation and ... fields (Unit 6 Science Test covering standards MS-PS2-4 and 2-5)

Week of February 21st: Science Projects (sandpaper friction, magnet-levitated trains)

Recall that here, a "unit" is simply my own way of numbering the four-week chunks of time during which I give two science projects and one science test.

Some of the projects listed here might not work during the pandemic, but they should have been feasible back in 2016-17. Oh, and I could have shown the students some Bill Nye videos, just like this teacher -- except that I could have sung the Bill Nye songs just as I now sing Square One TV. (The song in today's Bill Nye episode is "All in Motion.")

Lecture 12 of Prof. Arthur Benjamin's The Mathematics of Games and Puzzles: From Cards to Sudoku is called "Winning Ways -- It's Your Move." Here is a summary of the lecture:

  • In our previous lecture, we focused on the game of Chess, but of course there are many other games of strategy that lead to interesting mathematical questions. And armed with the proper insights, these games and questions can be conquered by the mathematically inclined player.
  • There are three types of games -- ones where the last player to move wins (Chess, Checkers, NIM, Cram, Domineering), ones where the winner is the first to create a structure (Tic Tac Tow, Hex, Connect Four), and ones where the winner accumulates the most (Scrabble, Go).
  • In Cram, players take turns placing dominoes on a 4 * 8 chessboard. Northrop's Game is played on the full board, where each player has eight checkers on his first rank. Players can only move forward along each file and can't pass an opponent. The last player to move is the winner.
  • NIM is a two-player game. There are piles of coins. You can take as many as you want from any one pile. The player who takes the last coin is the winner. For example, if there are three piles with 7, 5, 4 coins, you might take 4 coins from pile 1, then I take 2 coins from pile 2, and so on.
  • Charles Bouton came up with a winning strategy in the early 20th century. If there are two unequal piles and it's your turn, then take enough to the larger pile to make them equal. Then you are guaranteed to win. From a good position, all opponent moves go to a bad position.
  • If there are three or more piles, use the binary system. For example, suppose the three piles have sizes 13, 10, 6. In binary, 13 = 8 + 4 + 1, 10 = 8 + 2, 6 = 4 + 2. A good position contains an even number of each power of two -- since there's a single 1, you should take 1 from the 13 pile.
  • As it turns out, Northrop's game is just NIM in disguise. The number of spaces between checkers corresponds to the number of coins in each pile. And even Cram is a version of NIM -- in both games, the players take turns, the last move wins, and both are finite impartial games.
  • Sprangue and Grundy proved the following theorem: Every finite impartial game where whoever makes the last move wins can be transformed into a game of NIM. We can assign a NIM number, or "nimber," to each set of empty squares.
  • Chomp is an impartial game that is not equivalent to NIM. Players take turns chomping off a square on a rectangular chessboard, which eliminates all squares above it and to its right. T he player that takes the last square loses.
  • There is an existence proof that a winning strategy exists for the first player. Suppose taking the square in the upper right is a good move, then the first player should do so. If it's bad, then the second player has a good response to it -- which the first player preempts by doing so herself.
  • In a variant of Hex, red goes first. Then blue can either make the next move, or decide this one time to switch places and play as red. So red shouldn't start too strongly (such as in the center) or blue will want to switch. This is called the pie rule.
  • Indeed, I cut, you choose is a strategy to divide a cake into two pieces. If there are three or more people wanting cake, then the first player moves the knife until someone says stop. That person takes 1/3 of the cake, and then this is reduced to the two-person case.
  • Connect Four is a more complex version of Tic Tac Toe. White and Black take turns dropping checkers into a vertical 7 * 7 board. The winner is the one who places four in a row. White should begin in the center to force a win. If White doesn't, Black should start one spot closer to center.
  • Here are some Connect Four tips: appreciate the center column, create (and guard against) double threats, make forcing moves, and be patient and ponder parity.
  • Computers can beat humans in so many games. One game that has yet to be cracked by a computer is Go.
  • Games and mathematics are alike in many ways -- in both cases, we learn how to apply rules in the correct order in order to reach a goal. This is why some schools teach puzzles such as Rubik's Cube to young students.
This completes another highly enjoyable course. I've seen many other MTBoS teachers introduce puzzles to their math classes for the same reason. And today's U of Chicago lesson is, in many ways, just one big puzzle.

Lesson 9-8 of the U of Chicago text is called "The Four-Color Problem." This lesson doesn't appear anywhere in the modern Third Edition, because this is one of those "extra" lessons that we include mainly for fun.

In the past, I've mentioned several books and lectures which discuss the Four-Color Conjecture. One of these was David Kung's lectures. [2021 update: Let me snip out David Kung's lectures here, since we're now watching Arthur Benjamin's lectures.]

I wish to link to a member of MTBoS who actually teaches the Four-Color Theorem in class:

http://eatplaymath.blogspot.com/2015/10/the-four-color-theorem-and-pumpkin-time.html

Lisa Winer is the author of this post that is over five years old. She doesn't specify in what state she lives, nor does she make it easy for me to figure out what grade or class this is.

Anyway, in Winer's class, she uses the term "chromatic number" to describe the fewest number of colors required to fill in a map. The Four-Color Theorem, therefore, states that the chromatic number of any planar map is four. On a Mobius strip the maximum chromatic number is six, and of course on a torus the maximum is seven.

It's time to return to Euclid. Of course, he writes nothing about Four Colors or reflections across an axis, and so we proceed with the next proposition instead:

Proposition 11.

To draw a straight line perpendicular to a given plane from a given elevated point.


Propositions 11 and 12 are both constructions. Many of Euclid's propositions are constructions -- indeed, "The First Theorem in Euclid's Elements" (that is, Proposition I.1) featured in Lesson 4-4 is actually a construction.

Classical constructions are performed with a straightedge and compass, and David Joyce writes about the importance of actually proving constructions as theorems. But it's awkward to ask our students to perform a construction in three dimensions.

In this construction, we have a point A and a plane P, and we wish to construct the line perpendicular to P through A. How can our students do this? Is P the flat plane of the paper and A a point floating up in space?

It might be interesting to attempt Euclid's construction in the classroom. Here's how: We choose A to be a point on the ceiling and P is the plane of the floor. Thus our goal is to draw a point on the floor directly below A.

The key to this construction is to hang a rope from point A -- a rope that should be longer than the room is high. We can pull the rope at any angle and double-mark the points where the rope is touching the floor. I say "double-mark" because the point on the floor (where the rope touches) is marked (say with chalk), and then the point on the rope (where the floor touches) is marked (say with a piece of tape). The rope now can serve as a compass -- the point of the compass is at A, and the opening of the compass is set to the distance between A and the tape. The locus of all points on the floor that are the same distance from A as the point marked on the floor is a circle, and the locus of all points on a given line on the floor that are the same distance from A is a pair of points. So if we have a point (say B) drawn on a line on the floor, then we could find the unique point C on that line such that AB and AC are congruent.

All the lines on the floor can be drawn in chalk. There will be some plane constructions drawn on the floor as well, so we could use a large compass where the pencil has been replaced with chalk.

OK, so let's begin the construction. We start by drawing any line on the floor, and then we label any point on that line B. We now find C on this line exactly as given above -- we double-mark B on both the rope and floor, and then swing the rope to find C such that AB = AC.

Now we use the chalk compass to find the perpendicular bisector of BC. The midpoint is D.

Then we double-mark D with a second piece of tape, and then find the point on the last line we drew (that is, the perp. bisector of BC), to be labeled E, such that AD = AE. The second piece of tape must be higher up than the first since AD < AB, and so there's no danger of confusing which piece of tape is which.

Finally, we find the perpendicular bisector of DE. The midpoint is F. Euclid's G and H are any points on this last line -- their location doesn't matter. Only F is relevant here. AF is the desired line through A that is perpendicular to the plane of the floor, and F is directly below A.

Of course, this whole construction seems silly because of gravity. We can just hang a rope freely from A, label the point where the rope touches the ground F, and then we're done! The difference, of course, is that Euclid's three-dimensional space isn't physical space, and so there's no direction that's "favored" because of gravity or any physical force.

And so I'm not quite sure how David Joyce has in mind when he says he wants "the basics of solid geometry" to be taught better. Does he include Euclid's spatial constructions -- does he really want students to perform them? Or maybe he merely desires that students visualize the proofs in their minds while looking at the proof.

(Do you remember Euclid the Game, which is played on computers? Maybe in higher levels, players can make three-dimensional constructions that are difficult to perform in the real world!)

By the way, we can still modernize Euclid's proof:

Given: the segments and angles in the above construction.
Prove: AF perp. plane P

Proof:
Statements                              Reasons
1. bla, bla, bla                         1. Given
2. BC perp. plane (EDDA)   2. Proposition 4 from last week
(Call it plane Q. In the classroom, Q is an invisible plane parallel to a wall.)
3. GH | | BC                            3. Two Perpendiculars Theorem (planar version)
4. GH perp. plane Q               4. Perpendicular to Parallels (spatial, Tuesday's Prop 8)
5. AF in plane Q                     5. Point-Line-Plane, part f (ADF all in plane Q)
6. GH perp. AF                       6. Definition of line perpendicular to plane
7. AF perp. plane (GHDE)   7. Prop 4 (AF perp. DE is part of "Given")
8. AF perp. plane P                 8. From construction (both lines were drawn in plane P)

It might be tricky to reconcile this proof with the "rope" construction from above. In Euclid's construction, AD is designed to be perpendicular to BC, likewise AF is perp. to DE. Both of these perpendicular constructions technically occur in planes other than the floor -- yet earlier I direct you to perform perpendicular constructions on the floor -- which is the wrong plane.

But think about it -- given a point A and a line, how do we construct a line through A perpendicular to the given line? The answer is that, using the compass, we find points B and C on that line that are equidistant from A, and then find the perpendicular bisector (in that plane) of BC.

But technically, all we really need is D, the midpoint of BC. Then the line through points A and D is automatically the perpendicular bisector of BC in the correct plane. It doesn't matter how we obtain the midpoint D -- all that matters is that we find it. This includes finding the perpendicular bisector of BC in the wrong plane (that is P, the plane of the floor). This is why Euclid is able to assert and use statements like AD perp. BC in his proof, even though this isn't obvious from our ropes. (And as it happens, the perpendiculars in plane P appear later in the proof anyway, so we might as well construct these.) In the end, let's just stick to the Four-Color Theorem and two-dimensional reflections.

Today I'll post my second pandemic-friendly activity (especially after posting yesterday's making surfaces activity -- that's what the lesson was about, but it's hard to do in a pandemic). I'm not sure how to find a Four-Color activity online -- but when in doubt, just go to Desmos:

https://www.desmos.com/calculator/r1rwm2lymo

So students can create their own maps in Desmos and demonstrate how to four-color them.

I'll keep last year's worksheet on reflections -- but then again, I suspect that these could be "desmofied" as well.


No comments:

Post a Comment