Signaling Problem Solution via Proof by Contradiction

December 11, 2012: We began our final session of our Signalling Problem Math Circle with a few rounds of Exploding Dots, this time in binary.  The large number of explosions in binary (base two) compared to decimal (base ten) was such fun.  I asked the group how many different numbers could be represented in binary with just 5 boxes for dots (units place through sixteens place, as calculated by the kids).  The kids were unsure, but played with maximizing the number of explosions.  C proposed a rule that once the sixteens box was “full” (ready to be exploded), we put the appropriate number of dots in the units box, creating a continuous repeating loop (and therefore nearly continuous explosions).  D, X, A, and J loved this idea.  V and S were more interested in the mathematics than the explosions.  Unfortunately, M was absent and not able to voice her opinion.  A extended C ‘s idea with a proposal that we use base one to generate non-stop explosions.  We debated and concluded that base one does not exist, then returned to binary.  It took some hard work, but the kids did conclude that we could represent 31 different values in the five-box binary machine.

Last week the kids had written numbers on slips of paper for use in the Exploding Dot machine. This week we did a few more of these, with the students deciding which base system to use for each number.  I was so sure that for the large numbers (99, 8 billion, etc.)  they’d choose the ease of decimal over the tedium of binary, but they wanted more explosions, so chose binary.  We discussed how different systems are useful in different scenarios.  I began a discussion of the use of binary in computer science and robots, but other than D, the kids were more interested in acting out the Signalling Problem than in discussing how zeroes and ones can represent on and off switches, so we returned to that problem.

I left the five-box binary Exploding Box machine on one board and moved the group to the other board.  We reviewed the 2 codes that our group had devised in prior weeks to solve the Basic Signalling Problem.  All were still stumped, however, on how to solve “Level Three” of the problem, in which 30 different messages needed to be sent.  This whole time, a solution was on the other board, in Exploding Dots format.  None of the kids made the connection.  I questioned and nudged, nudged and questioned.  More engineering approaches emerged, but no more mathematical approaches sprang forth.  Since this was the final class, I reframed the question:  “Could you somehow use binary to solve this problem?”

“Yes,” said the students, at first.  Then, after a bit of thought, the group consensus changed to “No.”  No one believed that one candle turned on or off in each of 5 windows could make up as many as 30 combinations.  Since our group members are age 10 and younger, they are not familiar with one of my favorite fields of mathematics, combinatorics.  I pointed to the other board, containing the work we had been doing earlier in the session.  I asked, “How many numbers can you represent in a five-box binary Exploding Dot machine?”

“31”

“How many messages can you represent in a five-window system with 2 values per window?”

No one was sure, but all reiterated that is certainly wasn’t as many as 30.  I asked them to name a code number that wouldn’t work using candles to express the number in binary.  X suggested 86.  J suggested 200. D suggested trying numbers we already were using in the code: 13 and 36.  We found that 13 worked, but the others didn’t.  D proposed that we change the code so that only numbers that do work with this system be used.  “What numbers would those be, then?” I asked.  The kids suspected that any number from 1 to 31 would work, and tried some.  We did not try all of these numbers because the group grudgingly was able to see the connection to exploding dots and to generalize that they all would.  I say “grudgingly” because this solution seemed to defy their number sense (combinatorics often has that effect) and also because they wanted to try more numbers but also to get on with the play.

So binary did work with the candles, but what really excites me about this solution is how the kids came to it.  No one saw the solution until we made the assumption that a proposed solution did not work, and I charged the group with proving that it did not work.  The kids then were able to determine that certain examples did in fact work:  proof by contradiction.  This is an important mathematical reasoning skill, and young children can do it!

At this point,   we got out our flashlights and performed.  D, V, S, C, and A played people in the windows, J played the captain and X the alien.  They acted out all 3 codes that emerged over our six weeks.  Unsurprisingly (since the Kaplans mentioned this to me) the proper right/left orientation in binary was confusing.  It was a short play, and a fun play.  Then everyone went home.  I hope that the kids have gone home with a stronger sense of place value, digits, and different number systems.  They might not know these terms, but do understand these concepts.  To follow up on these concepts at home, I would recommend using Exploding Dots to do more addition, and to do subtraction, which we never had time for.  The Dots make “borrowing” and “carrying” intuitive.  I’d recommend that the older kids in the group try more alien arithmetic as a way to move into algebraic thinking.  Everyone would probably enjoy more discussion about Plato, and uses for different bases.  I like to think that everyone will continue to jump out of their seats with excitement as their mathematical thinking evolves.  I also hope to see some of the younger kids from this group in our winter math circle on Mathematical Logic.

For you interested adults and teens who have been following this Math Circle, I found Hubert Dreyfus’s paper connecting the use of binary in computer science with Plato’s Socratic Dialogues:  “From Socrates to Expert Systems: The Limits and Dangers of Calculative Rationality.”  I’ve also read that the movie The Matrix is actually a retelling of the Allegory of the Cave.  Haven’t seen it though.

Expect to see a whole batch of photos from this math circle on the website within a few days.

Wishing you all a great winter break.

— Rodi

[juicebox gallery_id=”10″]