Tuesday, February 23, 2021

Lesson 11-4: The Midpoint Formula (Day 114)

Today I subbed in a high school special ed class. It is in my first OC district. It's basically the same special self-contained class that I mentioned earlier this month, in my February 3rd post. There's no "A Day in the Life" today.

The students are given a worksheet with five three-digit addition problems. They are allowed to use a calculator, and most of them do -- but one guy tries three of them without the calculator. In these problems, one number is a multiple of 100, which is why he decides to take them on. He gets two of them correct, but makes a mistake on the third, writing 800 + 223 = 923. I tell him to try it on the calculator, after which he realizes his error. This is in fact an advantage to having a calculator in this situation -- it allows me to correct silly mistakes without arguments.

Another guy uses the calculator for all five problems, except that he presses the + key instead of =, so for 800 + 223 he presses 800 + 223 +. This gives him a running total of all the addends so far, and so since this is the fourth problem, his answer for this problem is over 2000. I direct him to start over and make sure that he presses the = key at the right time. After the worksheet, the students work on a familiar website, IXL.

Today is Eightday on the Eleven Calendar:

Resolution #8: We follow procedures in the classroom.

This is one of the few resolutions that these students need to follow -- they have many procedures not found in a gen ed classroom, including those for getting lunch and bringing it back to the classroom.

I don't sing any songs today -- I almost never do for this class. Also, just as I alluded to in my February 3rd post, these students stay on campus after lunch for "academic support" -- the gen ed students go home and log in to Zoom if they need tutorial help. Today, the students get to dance around to music in a special room during academic support. Thus it's not as if they needed me to sing any songs today -- they get their music from the computer during dance time anyway.

EDIT: The delayed 2020 Putnam exam was given on Saturday, February 20th. This post is dated the Tuesday after the exam -- traditionally the day when I discuss Putnam problems on the blog. I maintain this tradition by inserting this discussion into this post.

This year, I wish to discuss two of the Putnam problems. As usual, the first will be Problem A1, since at least in theory, this is the simplest problem:

A1. How many positive integers N satisfy all of the following three conditions?
(i) N is divisible by 2020.
(ii) N has at most 2020 decimal digits.
(iii) The decimal digits of N are a string of consecutive ones followed by a string of consecutive zeros.

Recall that this is technically the 2020 Putnam that was delayed due to the pandemic. It's a Putnam tradition to mention the year in at least one of the problems. This year, a whopping four of the twelve problems mention 2020 -- A1, A5, B1, and B4.

And indeed, I recommend that students factor the year number on the night before the exam, since the problem that mentions that number often requires its factorization. Indeed, Problem A1 involves multiples and divisors, and so the factors of 2020 are very relevant. (Before you ask, notice that for the next Putnam, 2021 = 43 * 47.)

We observe that 2020 = 20 * 101. Further factorization of 20 isn't relevant because we already know a divisibility rule for 20 -- the last two digits must be 00, 20, 40, 60, or 80. Since our numbers consist only of 0's and 1's, the only digit pair we need to consider here is 00. Now we know how many zeros our numbers have -- at least two. And as soon as we have the zeros, we don't even need to think about the factor 20 again -- the zeros take care of it.

Now we must consider divisibility by 101. (This is called square-alpha at Dozens Online -- that is, it's one more than the square of the base.) It's easy to see that 1111 = 101 * 11 is the first multiple of 101 that contains only 1's. Putting our 1's and 0's together, this gives us the first number on our list:

111100

And we can have any number of zeros after the four 1's -- from two up to 2016 (since the total number of digits is at most 2020):

111100...00 (2015 list entries starting with 4 ones)

It might take a while to figure out the next repunit (that is, all 1's) multiple of 101 -- it's 11111111, which is equal to 1111 * 100001:

1111111100...00 (2011 list entries starting with 8 ones)

One repdigit divides another if the number of 1's in the first divides the number of 1's in the second. So this tells us that the number of 1's must be a multiple of four. Combining this with the fact that there are at least two 0's, this gives us all the numbers in our list:

2015 list entries (starting with 4 ones)
2011 list entries (starting with 8 ones)
2007 list entries (starting with 12 ones)
2003 list entries (starting with 16 ones)
..
15 list entries (starting with 2004 ones)
11 list entries (starting with 2008 ones)
7 list entries (starting with 2012 ones)
3 list entries (starting with 2016 ones)

Thus our final answer is the sum 2015 + 2011 + 2007 + 2003 + .. + 15 + 11 + 7 + 3 -- and recall that no calculator is allowed on the Putnam. But notice that this is the sum of an arithmetic sequence, and so we can use our "Gauss 1-100" trick to find the sum:

2015 + 3 = 2018
2011 + 7 = 2018
2007 + 11 = 2018
2003 + 15 = 2018
..

How many copies of 2018 are there? The number of addends in the sum is 2016/4 = 504, and so the number of pairs is half of this. But let's take half of 2018 instead -- in other words, there are 504 addends and the average of them is 1009. This is easier to multiply without a calculator:

1009 * 504 = 504500 + 4036 = 508536

which is the correct answer. There are over half a million numbers in our list that satisfy the properties (i), (ii), and (iii) given above.

If I show this problem to high school students, they should at least grasp the concept of what we're doing, since it's just addition, subtraction, multiplication, and division. There are a few leaps of abstraction that might confuse students though -- for example, why is it that we can add extra 0's to the end of the number without affecting its divisibility by 2020? We'll have to remind them that adding an extra 0 multiplies the number by 10 -- and multiplying only produces more factors of the number without taking any of them away.

The second problem I wish to discuss is Problem B2. That's because it mentions a game that might be appealing to our students:

B2. Let k and n be integers with 1 < k < n. Alice and Bob play a game with k pegs in a line of n holes. At the beginning of the game, the pegs occupy the k leftmost holes. A legal move consists of moving a single peg to any vacant hole that is further to the right. The players alternate moves, with Alice moving first. The game ends when the pegs are in the k rightmost holes, so whoever is next to play cannot move and therefore loses. For what values of n and k does Alice have a winning strategy?

This is a a very nice game to set up in the classroom. We divide the students into pairs, and they can take turns playing Alice and Bob in order to discover the winning strategy. It's also good for the teacher to play Bob against a student to play the role of Alice. (The student should be Alice since, after all, the questions asks us to find her winning strategy, not Bob's.)

We might start with, say k = 3 and n = 8. A simple game might look like this:

1. 2-7 3-4
2. 7-8 1-2
3. 2-5 4-6
4. 5-7A

This means, on the first move, Alice moves a peg from hole 2 to hole 7 and Bob moves a peg from hole 3 to hole 4. On the fourth move, Alice moves a peg from hole 5 to hole 7 and wins (A for Alice).

An easy way to find a strategy is to consider simple cases first. For example, suppose k = 1 -- that is, that there's only one peg. It's now trivial to find a winning strategy for Alice:

1. 1-8A

And this obviously works for any value of n -- just move the peg to the last hole in one move. So we see that Alice has a winning strategy for k = 1 and any value of n.

Let's see what happens when k = 2. When n = 8, we can see that Alice has no way to win -- if Bob plays correctly, he can force a win. Let's try it:

1. 1-3 2-4
2. 3-5 4-6
3. 6-7 5-8B

Bob wins by mimicking Alice -- whenever she moves one peg, he moves the other. He has mentally divided the board into pairs of holes -- 1/2, 3/4, 5/6, 7/8. Whichever hole Alice moves her peg to, Bob moves the other peg to the paired hole. Sooner or later, Alice moves a peg into either hole 7 to 8, thus allowing Bob to move the other peg into the other hole and win.

Of course, Bob can only make these pairs if n is even. And k doesn't have to be 2 -- it can also be any even number. Then both the pegs and holes are paired -- whenever Alice makes a move, Bob moves the paired peg (so if Alice moves peg 3, Bob moves peg 4 and vice versa) into the paired hole.

This suggests that Alice has a winning strategy if either k or n is odd -- that would prevent Bob from making pairs from the start. For example, if k = 2 and n = 7, Alice should start with the following move:

1. 1-3

Now with pegs in holes 2 and 3, Alice can divide the rest of the board into pairs -- 4/5 and 6/7. Now she can do to Bob what he does to her in the k, n even case -- whenever Bob moves a peg, Alice makes the paired move and wins:

1. .. .. 3-5
2. 2-4 4-7
3. 5-6A

If k is a larger even number like 4 and n is odd, Alice should begin with the following move:

1. 1-5

which allows her to pair all the remaining holes starting with 6/7, 8/9, and so on.

If k is odd, it's actually helpful for Alice to imagine that there is an invisible (k+1)st peg in the (n+1)st hole, so that there are now an even number of pegs to be paired. Alice's first move is then to pair this invisible peg with one of the real pegs. If both k and n are odd -- for example, k = 3, n = 7 -- then Alice should begin with:

1. 3-7

Now when Bob moves, he breaks the 1/2 pair, allowing Alice to make a pair on her next move. (Notice that even though both k + 1 and n + 1 are even, this invisible peg doesn't produce a win for Bob. That's because this invisible peg begins unpaired, so Alice can pair it. On the other hand, in the k, n even case, all the pegs begin paired, so Alice can only break a pair that Bob can repair on his move.)

If k is odd and n is even -- for example, k = 3, n = 8 like the original problem I gave above -- then Alice should pair the first peg with the invisible peg:

1. 1-8

Then the hole pairs are 2/3, 4/5, up to n/invisible peg.

So Bob wins with k, n both even, and Alice wins with at least one of k, n odd. This is a fascinating problem that I hope our students can enjoy.

Lesson 11-4 of the U of Chicago text is called "The Midpoint Formula." In the modern Third Edition of the text, the midpoint formula appears in Lesson 11-7.

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

Lesson 11-4 of the U of Chicago text covers the other important formula of coordinate geometry -- the Midpoint Formula. As the text states, this is one of the more difficult theorems to prove.

In fact, the way we prove the Midpoint Formula is to use the Distance Formula to prove that, if M is the proposed midpoint of PQ, then both PM and MQ are equal to half of PQ. The rest of the proof is just messy algebra to find the three distances. The U of Chicago proof uses slope to prove that actually lies on PQ. Since we don't cover slope until next week, instead I just use the Distance Formula again, to show that PM + MQ = PQ, so that M is between P and Q. The algebraic manipulation here is one that's not usually used -- notice that instead of taking out the four in the square root of 4x^2 to get 2x (as is done in the last exercise, the review question), but instead we take the 2 backwards inside the radical to get 4, and then distribute that 4 so that it cancels the 2 squared in the denominator.



No comments:

Post a Comment