Sunday of what is now in the modern era the 5-day MEA weekend. Hell, why not just give them the whole week off? I am a half inch away from being that parent who regales the kids with tales of having walked miles to school in winter weather unmitigated by global warming—and only two days off for MEA!
Since the end of the long weekend was coming into view, Lydia finally glanced at the math problem she'd been assigned over the break. Take a guess who was looking at it next. Right when Illinois was driving for the winning field goal against the Badgers, too. If next Saturday the Gophers were to beat Maryland, while Ohio State wins at home against Wisconsin—by no means certainties but both events more likely than not to occur—then the Gophers would be in first place of the Big Ten West by two games with four to play. Our schedule gets tough after that, I know. But on the last Saturday of the regular season, we have a home game against Wisconsin, and it's beginning to look like it's not a pipe dream to think that the championship of the Big Ten West could be on the line. How much fun would that be? When I was 9, the Gophers beat Wisconsin on the last weekend of the season to claim a share of the Big Ten title. That was the last time. Fifty-two years.
I am clearly setting myself up to be crushed. Here is Lydia's math problem:
King Arthur was the ruler in Camelot who had all those knights and a round table. He loved inviting the knights over for parties around his round table. If there was something pleasant that the king could give to only one knight—an extra dessert, a dragon to chase, etc.—he had them play a game to determine who would get it.
The game went like this. First, King Arthur put numbers on the chairs beginning with 1 and continuing around the table, one chair for each knight. He had the knights sit down so that every chair was occupied. Then he stood behind the knight in chair 1 and said, "You're in." Next, he moved to the knight in chair 2 and said, "You're out," and the knight left his seat and went off to stand at the side of the room to watch the rest of the game. Next, he moved to the knight in chair 3 and said, "You're in." Then he said "You're out" to the knight in chair 4, and that knight left his seat to stand at the side of the room.
The king continued around the table in this manner. When he came back around to the knight in chair 1, he said either "You're in" or "You're out," depending on what he had said to the previous knight. (If the previous knight was "in," then the knight in chair 1 was now "out," and vice versa.)
The king kept moving around the table, alternately saying, "You're in" or "You're out" to the knights who remained at the table. If a chair was now empty, he simply skipped it. He continued until only one knight was left sitting at the table. That knight was the winner.
YOUR TASK: Of course, the number of knights varied from day to day, depending on who was sick, who was away chasing dragons, and so on. Sometimes there were only a handful of knights present, but other times there could be a hundred or more. The question for you is: If you knew how many knights were going to be at the table, how could you quickly determine which chair to sit in to win the game?
Develop a general rule, formula, or procedure that will predict the winning seat in terms of the number of knights present. Explain why your rule works.
By the time I'd read all that, the Badgers had lost and the Gopher game was on. It's not like I had an immediate idea about what the answer was, so to put Lydia off—it's her homework, dammit, not mine—I told her to figure out who wins if there's 2 knights, 3, 4, 5, 6 and up to 10. That should keep her busy, I thought, and maybe there will be a pattern. She was gone about a half hour before returning with what I guess she's been taught to call a "t-chart." It looked sort of like this, but with a lot of erasures:
| # knights | winning chair |
| 2 | 1 |
| 3 | 3 |
| 4 | 1 |
| 5 | 3 |
| 6 | 5 |
| 7 | 7 |
| 8 | 1 |
| 9 | 3 |
| 10 | 5 |
While she was working up her t-chart, I stewed over the problem enough to conclude:
(1) A knight sitting in an even-numbered chair at the start of the game will always be eliminated on the first trip around the table;
(2) If there are an even number of knights at table, then an even number will be eliminated, and the next round will commence with the knight in chair 1 being "in"; and
(3) Consequently, if the number of knights at table is given by 2n where n is a positive integer (so the number of knights at the start of the game is 2, 4, 8, 16, etc.), then each successive round always has an even number of knights remaining, and the knight in chair 1 wins.
So that covers a few of the possibilities. What about all the others? Lydia's table suggests that, after the regular "recursions" to chair 1 being the winner, each additional knight at the start of the game just moves the eventual winning chair up to the next odd number. If there are 16 knights to start, sit in chair 1. If there are 17, sit in chair 3. If there are 18, sit in chair 5. Etc.
But that doesn't really satisfy the requirement in the problem concerning a "general rule, formula, or procedure" that allows you to predict the winning chair quickly. Suppose you are told that the game begins with 107 knights sitting around the table. Which chair wins? Quick!
For that, another "t-chart":
| Distance from last 2n | Winning chair |
| 0 | 1 |
| 1 | 3 |
| 2 | 5 |
| 3 | 7 |
| 4 | 9 |
| x | 2x + 1 |
So if there are 107 knights at the start of the game, the winning chair is #87, because 107 is 43 more than 26 = 64, and 1 more than twice 43 is 87. Lydia will be writing this up at around 9:45 tonight, unless it's at 8:45 tomorrow morning. She leaves for school at 9:10.
Comments