Oliver Steele

What follow are some notes from talking about the elections and the presidential primaries with my children, and some metaphors that I found helpful in thinking about the topics. They’re not otherwise related to each other, except that they all came up over the last couple of days.

1. Votes are Agents

The wikipedia article about voting systems, and the Newsweek article When Math Warps Elections describe a number of different systems: in particular, the America plurality system where you casts only one vote (presumably for your favored candidate, unless you’re voting strategically); approval voting, where you vote for all the candidates your find acceptable (again, unless you’re voting strategically); and ranked-choice or instance-runoff voting, where you rank the candidates, and the candidate who was highest on the smallest number of ballots is removed from all of them until only one candidate remains.

It can be hard to compare these systems. The wikipedia lists some criteria, but it’s a few hours time to learn enough about the theory in this area to apply them.

So here’s a less formal way to think about this, using a metaphor that’s more familiar to most of us (including kids) than the language of the economic theories:

You’re building a robot. The job of the robot is to vote for a candidate, on your behalf. Your robot may need to vote several times: the real election may be built out of a number of micro-elections with different sets of candidates. The reason you’re delegating this to a robot instead of doing this yourself is that it’s logistically easier, and faster, to get each voter to build a robot¹ once than to get each voter to show up for each micro-election.

One way the voting systems differ is in how much you get to tell your robot; and, therefore, what your robot does in the elections where your first-choice candidate isn’t on the ballot². In a plurality system, you can only tell the robot your first-choice candidate; your robot has to sit out the micro-elections where your candidate isn’t on the ballot. In an approval system, where you’ve selected several unranked candidates, your robot doesn’t have enough information to vote in those elections where more than one of your candidates is on the ballot. In an instant-runoff system, your robot always knows how to vote the same way as you.

Kids seem to have a sense that there’s something a bit off about strategic voting; and, therefore, about systems that require it. (Among other problems, strategic voting is a bit like learning test-taking skills for the SAT: it provides an advantage for those who have thought of it, which may bias the election.) In the robot metaphor, strategic voting comes about only when your robot is too stupid to do what you want it to in every micro-election, so you have to decide what to tell it in order to get it to vote right in the micro-elections that you think are more likely to come up, or more likely to matter.

2. Primaries and Decision Theory

[This is unrelated to the first topic, except that they're both about elections.]

Let’s say you want to run for president. To do this effectively, you need a certain amount of manna (money, endorsements, and organizational backing); each bit of manna increases your chances of winning.

There’s a mana provider with a lot of huge amount of manna, who’s willing to make a deal with you: after you accept the terms of the deal (and only after), they’ll decide whether to anoint you (this is the process by which they give you all their manna); and if you don’t, you agree to drop out of the race.

This deal has a up side — that you’ve got more manna, and therefore you’ve increased your chances of winning the election if you’re anointed — and a huge down side — that if you accept the deal and the manna provider doesn’t anoint you, you’ve decreased your chances of winning the election to zero (because then you’ve promised not to run).

Let’s say you have a 20% chance of winning the election on your own, and that being anointed increases your chances by 20%. Then the payoff matrix looks like this:

Now let’s say you have only a 50% chance of being anointed. Then your chance of winning the election if you reject the deal is 20% (in this case it doesn’t matter whether you would have been anointed not), and your average chance of winning the election if you accept the deal is also 20%. It’s not obvious whether you should accept the deal or not; it depends on your risk tolerance.

But now let’s throw a couple of other factors into the mix. Both of these factors have the effect that your chance of being anointed is correlated with your chance of winning the election.

First, the manna provider could attempt to anoint you exactly when your chances of winning are greater anyway (by using some tool, such as polls or an interim election, to estimate these chances). If instead of having a 20% chance of winning the election without anointment, you either have a 30% chance or a 10% chance (you don’t know which when you make the deal), and you’ll be anointed if it turns out (after you make the deal) that it was closer to 30%, then the matrix looks like this:

The other factor that increases the correlation between being anointed and winning the election is that if you are not anointed, someone else is, and this decreases your chances of winning the election, say by 20% (but not to less than 1%).

Then the matrix looks like this:

The mana providers, of course, are political parties; and this is why candidates join parties.

What’s in it for the manna providers? This is just strategic nomination, to avoid splitting the vote in a plurality voting system. Interestingly, strategic nomination is analogous to strategic voting, only proactive, and aggregated at the level of the political party.

—

¹ These are really simple robots, and we can build them all by putting checkboxes or numbers on a paper ballot.

² The other ways they differ are in how they many micro-elections there are; how they determine who runs in each of those; and how the results of the micro-elections are aggregated to determine the winner of the overall election.

Division-free GCD

A few years ago I described an algorithm for computing the greatest common denominator without division. (Euclid’s algorithm requires division, in order to compute the remainder.) Although less efficient than the standard algorithm, I found it easier to teach to my children when they were learning to add fractions.

I’ve made a movie of the steps involved here. (The Quicktime player has a bug: if the movie plays the first step over and over, try waiting it out, but if it doesn’t get past the first step after three or four times, then press your browser’s Reload button.)

Division-free LCM

Yesterday Paula Feynman asked me if there was a similar algorithm for finding the least common multiple. I came up with this one on the drive home. It can be used at grade school level — my children learned it in about half an hour — and I used their help (and the influence of Edwin Hutchins) to figure out a teachable presentation.

The movie is here. (As before, if the movie plays the first step over and over, try waiting it out, but if it doesn’t get past the first step after three or four times, then press your browser’s Reload button.)

Euclid, Meet Gauss

This algorithm is a great warm-up for Gaussian elimination. The numbers in the second and third columns are co-factors: their respective products with the two inputs sum to the number in the first column. (This is why the first two rows are initialized to the identity.) From there down, it’s Gaussian elimination: replace a row by a linear combination of rows, until the leading term in one of them has been annihilated. Since there are only two rows, you can work in place (by extending the table downwards), instead of copying the matrices to a new location each time.

The difference between this algorithm and standard Gaussian elimination is in the set of permissible operations. Since this algorithm doesn’t allow you to divide a row by a scalar (alternatively, to multiply by a non-integral rational) in order to produce unity, you’re limited to operations within the ring of integers. This restriction ensures that the operations preserve the number-theoretic properties of the inputs, which is what lets you recover the GCD and its co-factors at the end.

Sure enough, after I showed my son how the algorithm worked, I was able to easily show him how to invert a matrix in order to solve a family of systems of equations. (He had already worked with systems of equations in school, and we had worked on representing a system as a matrix last week.)

Nothing New Under the Sun

While writing this posting, I discovered that the division-free technique for computing the GCD was actually Euclid’s original algorithm.

Similarly, I belatedly found that most of the technique for computing the LCM of two numbers was also previously known (probably as of a century ago?). The “table method” of the “extended Euclidean algorithm” computes the co-factors, in pretty much the same way. However, that method, at least as described at Wikipedia, stops short of actually computing the LCM. It also relies on modular arithmetic; I think my version is more useful for elementary education. So maybe I’m bringing something to the table — so to speak.

Here’s a picture I drew to explain addition and subtraction of fractions to the sixth-grader:

We also ended up using a variant on Euclid’s algorithm for finding the GCD. It uses subtraction instead of division and remainder; it’s in general less efficient, but it’s easier to explain and can be easier to do in your head, when the numbers are small.

Construct a series whose first two terms are the inputs, and then continue as follows: each successive term is the absolute value of the difference between the preceding two terms — that is, simply subtract the smaller from the larger. If you reach one, the GCD is one; if you reach zero, the GCD is the previous term. (Or, you could also let the series peter out to zero, but the way I’ve stated it is simpler in practice.)

• 24 and 16: 24, 16, 8, 8, 0.
• 9 and 7: 7, 9, 2, 7, 5, 3, 2, 1.
• 12 and 9: 12, 9, 3, 6, 3, 3, 0.
• 35 and 28: 35, 28, 7, 21, 14, 7, 7, 0.

An added advantage is that the first step lends itself to an optimization that almost always short-circuits the whole process, at least for sixth-grade math problems. Take the difference of the two inputs and test whether that divides both of them. If it does, that’s the GCD.

I posed a second-grader the question of what nine squared was. She reasoned that ten squared is 100, and nine times ten is ten less then that, and nine times nine is nine less than that, so the answer is 81. Then I asked her what eight squared was, and she was flummoxed. She saw that it was a similar problem to the one she’d just solved, but wasn’t sure how to apply the analogy.

Here are the pictures that showed her how to figure out the answer. We drew the location of the squares on a multiplication grid:

and I introduced the idea of a “solution structure”. A solution structure is a graphical representation of the steps of a solution. This is the section that represents the relation between 9² and 10².

Two problems can have different numbers but the same structure. This is the problem structure for both problems shown together:

And then she got it.

But this leads to the arithmetic problem of 81 minus 17, which was harder, for this seven-year-old, than 100 minus 10 minus 9. There are several ways to compute the difference betweeen 81 and 17. The hard ways are to count down by 17, or to do two-digit subtraction and carry the one. The easy way is to adjust the problem to 84 minus 20, and count down two tens to 64. But how can you show that 81-17 = 84-20?

Here’s what didn’t work: explain that adding three to both the minuend and the subtrahend leaves the difference unchanged. Seven was too early for something this symbolic. We used a number line instead:

The difference is the blue bar. Moving it on the number line moves its ends by the same amount, without changing the length of the bar itself. Conversely, you can move both ends by the same amount without changing the length of the line between them.

Problem solved.

Last weekend, I shared some interesting properties of numbers with my kids.

The great thing about explaining something to a non-expert is that you have to actually understand the topic. (This is why making teaching universities and research universities the same actually makes sense.) If you hide behind a formalism, the explanation won’t work. Usually, this means that you didn’t understand why the formalism worked either.

This is why I thought “why are far away things smaller?” was such a great question. “Similar triangles” answers are brittle, and if a tiny error makes far away things come out bigger instead, you won’t catch yourself until you got to the end of the proof.

Some of the interesting properties of numbers are: that (n + 1)×(n-1)=n²-1: that the perfect squares (0,1,4,9,…) go up by successive odd numbers (1,3,5,…); and that the area of a triangular number (1+2+…+n) has a closed form. These properties are easy to show using algebra, but to a child, the algebra doesn’t make sense.

Multiplication and division are grounded in visuospatial concepts, which is why these number theoretical results are easy to understand. What would a proof that stayed grounded in visuospatial concepts look like?

Properties of Addition

Addition is associative:

and commutative:

Multiplication is Commutative

The commutative law is that a×b=b×a. If a rectangle a high and b wide represents a×b , this is the same as saying that rotation is area-preserving:

Or, in the case of three factors, volume preserving:

Distributive Law

Associativity

Difference of Squares

The perfect squares are 0, 1, 4, 9, 16, …. The differences between successive squares are the odd numbers: 1, 3, 5, 7, 9, ….

In algebra, this is because the n² terms in (n+1)²=n²+2n+1 and in n² cancel, leaving 2n+1. Here’s why this is true in geometry:

Product of Alternates

The product of two numbers adjacent to a median, is one less than the square of the median. For example, 5²=25, and 6×4=25-1=24. Algebraically, this is because (n+1)(n-1)=n²-1. Geometrically:

Triangle Numbers

In closed form, the sum of the numbers from 1 to n is n(n+1)/2. One algebraic proof for this uses induction: substitute each of k+1 and k for n, and compute the difference.

There are two geometric proofs. The first requires two cases: one for even n, and one for odd. The second is simpler, but requires a bit of algebra: you need to draw two triangles, and compute twice the area; at the end, you divide by two.

First, the two-case proof, and some terminology. Cut a line at an integer mark as nearly in half as you can. The big piece is the superhalf. The little piece is the subhalf.

For an even number such as 6, the subhalf and superhalf are the same as the half (3). For an odd number such as 5, the subhalf (2) and superhalf (3) differ by one. The subhalf and superhalf of any integer sum to that integer: 3+3=6, and 2+3=5.

Now the first proof. If n is even, take the top half of the triangle and fold it over onto the bottom half. Each row has the same length, because the base increases by one going up, and the flipped top increases by one going down. That length is the width of the original base, plus one from the tip. Since there are n/2 rows, the triangle has the area of a rectangle that is n/2 high and n+1 wide.

For odd n, take the top subhalf of the triangle and fold it onto the bottom superhalf, extending each row except the bottom. The new rectangle is (n+1)/2 high (the superhalf), but only n wide. Multiply these out, and out the same as the first case.

A proof that doesn’t require two cases is to use two triangles. Consider the two triangles, which collectively have the area n×(n + 1):

This is the same, in algebraic terms, of taking the sum [1+n]+[2+(n-1)]+…+[(n-1)+2]+[n+1]=n×(n+1).

Next week: grounded fractions.

Addendum

Hans Martin Kern suggested calling this “Visualizing Basic Algebra.” That’s a much better name, and I’ve changed the title.

Mickey Kaus writes:

It’s worth noting that, in the event, not only did successor Arnold Schwarzenegger get more votes (3,744,132) than Davis (3,562,487), he also got more votes than Davis got in November, 2002 (3,469,025) when Davis won reelection.

But comparing these yes-Schwarzenegger votes to the no-recall votes ignores those who voted not to recall Davis, but also voted for Schwarzenneger as their choice for governer if Davis were recalled (since they couldn’t vote for Davis). That is, the straight-up Schwarzenneger versus Davis comparison counts everyone whose first choice was Davis and whose second choice was Schwarzenegger as a yes-Schwarzenegger vote (as well as a no-recall vote), artifically inflating the Schwarzenegger count. And it counts everyone who preferred a third candidate (say, Bustamante) to Davis and Davis to Schwarzenegger as a vote for neither Davis nor Schwarzenegger, artificially deflating the Davis-versus-Schwarzenegger count.

The appropriate comparison is between voters who voted not to recall Davis, and voters who voted to recall Davis and for Schwarzenegger as the replacement candidate. Presumably this is knowable (if the ballots haven’t been destroyed), but it’s not on the Secretary of State’s summary page, at least.

How could you estimate this? One (crude) estimate is that everyone who voted for Bustamante would have voted for Davis if Bustamante hadn’t been on the ballot. This overcounts (it counts voters who preferred Bustamante to Schwarzenegger and Schwarzenegger to Davis as voting for Davis), and it undercounts too (it fails to count voters who preferred some fourth candidate to Davis and Davis to Schwarzenegger as voting for Davis over Schwarzenegger). It’s not obviously worse than the yes-recall to yes-Schwarzenegger comparison, though. It gives 3,744,132 votes to Schwarzenegger and 6,172,557 votes to Davis.

Even if Davis would have only split the Democratic vote with Bustamante (that is, if Davis and Bustamente were equally popular, and if none of the Schwarzenegger votes were from crossover Democrats), Davis would have got 4,920,316 votes to Schwarzenegger’s 3,744,132 votes.

And as for the rest of the comparison:

Almost a million more people (4,416, 280) voted to recall Davis than voted to reelect him last year.

8,203,005 people voted in 2003. 7,318,618 people voted in 2002. (These figures are from dividing the subtotals by the percentages; the web sites don’t list the totals directly.) If 8,203,005 people had voted in 2002 with the same distribution, 4,314,780 would have voted against Davis, so he actually picked up about 100,000 votes.

Just something to think about.

Dot numbers are a new notation for numbers, that make integer addition look like rational multiplication. They may be useful in primary school math education. The idea is that once you understand integers and addition, you can learn another way to look at it that sets you up to understand fractions and multiplication.

I made up dot numbers a few years ago to try to explain negative numbers to my then-four-year-old son.

Basics

A dot number is a way of writing a number. A dot number is represented as a number of dots above a line. This is the number 3, as a dot number:

A negative dot number is a number of dots below the line. This is the dot number -3:
.

Addition

To add two dot numbers, combine the dots above the line, and the dots below the line. This is 3 plus 2:

This is -3 plus -2:

And this is 3 plus -2:

Cancelling

A dot number is in normal form if all its dots (if any) are on the same side of the line. A dot number that isn’t in normal form can be “normalizing”, or transformed into another dot number that represents the same integer and is in normal form. As long as there’s a dot above the line and a dot below the line, cross the dots out. The pairs of dots “cancel” each other.

The preceding number (3 plus -2) can be normalized.

To subtract a number, flip it upside down and add that. This is 3 minus 2:

Dots and Factors

Dot numbers are interesting because they’re isomorphic to fractions. Dot numbers are to addition (and subtraction, and the unit) as fractions are to multiplication (and division, and factors).

Just as the multiplicative inverse (the reciprocal) of a fraction can be obtained by turning it upside down, the additive inverse (the negative) of a dot number is obtained by flipping it upside down. (The inverse in both cases is the “vertical inverse”).

Just as fractions are multiplied by multiplying the tops and bottoms (numerators and denominators) separately, dot numbers are added by adding their tops and bottoms.

And just as any number can be represented by multiple fractions (1/2, 2/4, 4/8) which can be normalized (”reduced”) by dividing the top and bottom by integral factors (4/8 = 4×1/4×2 = 4×1/4×2 = 1/2), so an integer (3) can be represented by multiple dot numbers (3-0, 4-1, 5-2), each of which can be reduced by subtracting units from its top and bottom (5-2 = (1+1+1+1+1)-(1+1) = (1+1+1+1+1)-(1+1+1+1+1) = (1+1+1+1+1)-(1+1+1+1+1) = 3-0).

Seymour Papert used to tell a story contrasting the practices of medicine and education, in order to illustrate how little the latter has improved. Place a physician from the previous century in a modern operating room and he¹ won’t have a clue about what to do. Transport a teacher forward in time and they’ll fit right in. The moral is that the practice of medicine has made great strides during the last century; the practice of education hasn’t progressed at all.

I used to believe this story, and maybe it was true in the sixties. But in 1998, when I was looking for school for my rising kindergartner, I sat in on a number of elementary school curriculum nights. Among them was a presentation by the math teacher Bob Lawler² at Shady Hill School. This was the first time I’d set foot in an elementary school in 25 years, and things had changed. Math today, at least in the better schools, is taught nothing the way it was when I was a child.

Since then, I’ve had four years of indirect experience with the math curriculum at the Milton Academy Lower School). At these schools, math facts (addition, multiplication tables) are taught in second and third grade, but prior to that and continuing through it there are open-ended group projects, grounded both in other subject areas and in fun problems — the types of problems that mathematicians I know like to attack.

Grade Two for Gauss

One question from my son’s second grade was how many candles are needed for all the nights of Hanukkah. This is the same question Gauss answered when he was seven. Given the question in a context for creativity and with group collaboration, several of the second-graders came up with similar closed-form solutions.

Fibs for Small Fries

Another question was how many ways there are to roof a row of houses. The houses are connected, like brownstones in the city. There’s two styles of roof: a narrow roof covers one house; a wide roof covers two. There’s two ways to roof a row of houses.

How many ways are there to roof a row of five houses?

I believe this question was for fifth graders.

Getting Over Mr. Right

Sarah Allen writes about a story from John Holt’s book How Children Fail. The story itself is fascinating. (Read Sarah’s blog entry for more.) The larger context is the point that children are taught to play the “right answer game” instead of to learn how to learn.

Although I’m sure this is true in many classrooms, it’s no longer the state of the art in teaching methodologies. (It was never the state of the art among individual excellent teachers.) I think many parents, like myself five years ago, are limited to what they know from decades-old books and experiences or exposure to mediocre schools, and don’t have any idea of how far educational best practices have come.

Footnotes

¹ “He” is a safe, although not universal, bet for a nineteenth century physician.

² Not to be confused with Marvin Minsky’s student Bob Lawler, who also studies the epistemology of math.

These questions came up on a family drive last weekend:

• How many posts does a hundred-yard fence with one-yard beams have?

• What if the fence is circular?

• What if it’s a cross?

• What if it’s a figure eight?

The first question illustrates fencepost error. The second relates to the discovery of the benzene ring. And the last leads to Euler’s Formula. These three questions are from three different fields (computer science, chemistry, and math), but they’re all variants of the same question. (Of course that question is mathematical. That’s the point of math.)