We continued talking about voting methods, with an in-depth look at IRV (instant runoff voting) and the ranked pairs method. I’ll review with an example on Friday and then we’ll be moving on.

We also discussed why the plurality method does satisfy later-no-harm, but why in practice it fails in this general area very, very badly … as our example last Friday suggested.

Since we had looked at some things such as the binomial theorem, Pascal’s triangle, choice functions, and so on, I decided to briefly expand on that a bit as there was 5 minutes or so left at the end of class. I discussed this.

We continued to look at voting systems, with a botched attempt at explaining the Instant Runoff Method. (The example will work now. It’s relatively straightforward once figured out … no thanks to the Wikipedia article.)

See the chart of this page for a detailed matrix of which voting systems satisfy a multitude of criteria.

Why Plurality Satisfies Later-No-Harm

I found this a bit interesting. Namely, our analysis in class of the plurality method (and in fact, how we see it function in society) noted that it’s entirely possible to have three candidates in an election as follows.

  • Blue (40% of votes)
  • Red (30% of votes)
  • Green (30% of votes)

In such a situation, let’s say that the Red and Green parties are very similar but that both are very different from the Blue party. What happens if the Green party candidate is removed? Well, technically speaking, we’d have to have a new election if we were counting based on Plurality, since it isn’t a preference system. So, technically speaking, plurality can’t fail the later-no-harm criterion since the preference doesn’t change while tabulating the votes. Arguably, holding a new election with the Green party candidate removed DOES ESSENTIALLY THE SAME THING, but it’s technically a new election. That’s interesting, since we can see this at work, for instance, when smaller parties gain power in U.S. elections. Those smaller parties are often blamed for skimming off votes from one of the larger parties, leading to that larger party failing to gain enough votes overall.

Instant Runoff Voting Example

After some searching, I found this example on YouTube:

We’ll reconsider our example of votes in Tennessee on Wednesday. I’ll assign another homework then related to voting systems.

On Friday, we discussed voting systems. We’ll continue this on Monday. First, we discussed the voting system in the United States, hitting on some topics such as the electoral college system and drawing district lines. Then, we developed the following axioms for voting fairness. These are essentially the building blocks that any fair voting system must satisfy.

  1. (Majority Criterion) If one candidate is preferred by an absolute majority, then that candidate should win.
  2. (Mutual Majority Criterion) If an absolute majority prefer every member in one group over every member in another group, then a member of the preferred group should win.
  3. (Later-No-Harm Criterion) If every voter’s preference of $X$ or $Y$ remains unchanged, then the overall group’s preference of $X$ or $Y$ remains unchanged.
  4. (Condorcet Criterion) If a candidate would win a head-to-head battle against every other candidate, then that candidate should win.

There are other things we could add to this, such as a “dictator criterion,” i.e., that no person has any more power than any other person.

Voting Systems

We discussed a few voting systems. The details can be found on Wikipedia, and so for each of the ones we considered I am simply going to post a link. We’ll discuss these more on Monday.

The first system we discussed was plurality (first-past-the-post). Plurality fails to satisfy the mutual majority or Condorcet criteria.

The second system we discussed was the Borda count method. We considered an example where this method fails the later-no-harm criterion. Actually, interestingly, one can come up with examples to show that it fails all 4 of our fairness criteria.

We then considered the method known as instant runoff. This method has been shown to satisfy all of our criteria except the Condorcet criterion.

We’ve been talking about axiom systems and formal proofs in mathematics. On Wednesday, we covered some things from axiomatic Euclidean geometry. This is formal and a bit abstract. The idea is that we’ll talk about axioms of fair voting systems on Friday and show that certain voting systems fail to satisfy those axioms.

Undefined Terms

We have to start somewhere, and so we’re going to agree on what the following terms mean without defining them.

  • point
  • line
  • lies on (as in, a point lies on a line)
  • between (as in, a point is between two other points on a line)
  • circle
  • congruent

The last one there is a bit of a mathematical term. Congruence is a bit weaker than equality, just as equality is a bit weaker than identity. I explained this in class with some examples. Shoot me an email if you have questions or would like more examples.


We’re going to be using the following axioms for Euclidean geometry.

  1. We may draw a (unique) line connecting any two points.
  2. We may extend lines indefinitely in either direction once they are created.
  3. Given a point and a length, we may create a circle centered at the point with radius equal to the length.
  4. All right angles are congruent.
  5. Given a line and a point not on the line, there is a unique line going through the point that is parallel to the given line.

Defining a Right Angle

We didn’t include “right angle” in the list of undefined terms. Should we? Well, if we can construct the definition using what we have so far, then no. Can we describe what a right angle is using only what we have? The answer is yes. But, it isn’t easy. We need to define some things along the way. First, we need to know what a “ray” is.

Definition: Given two points $A$ and $B$, the ray $AB\rightarrow$ is the line starting at $A$, containing $B$, and then continuing indefinitely past $B$.

Once we have the definition of a ray, we can then define an angle.

Definition: Given three points $A$, $B$, and $C$, the angle $\angle BAC$ is the ray $AB\rightarrow$ together with the ray $AC\rightarrow$. That is, both rays start at $A$, one containing $B$ and one containing $C$.

Definition: Two rays are called opposite if they start at the same point, lie on the same line, but point in opposite directions.

Definition: Two angles are called supplementary if two of the rays forming them are opposite.

In the diagram, angles 1 and 2 are supplementary, and the rays from $B$ to $A$ and $C$ are opposite. Now, we can define right angles.

Definition: An angle is a right angle if there exists a supplementary opposite angle to it.


Sometimes, we can prove things directly from the axioms, and other times we can’t. When we can’t, we use formal logic to guide us through other strategies. One possible approach is what we’ll can RAA (reductio ad absurdum). The idea is that we want to show that a collection of known facts, axioms, definitions and so on can be used to prove a claim. So, what we do is assume that the claim is false … and then show that doing this results in running up against a logical brick wall. I explained this in detail in class, and you should feel free to ask me questions about it. It isn’t easy, so don’t think that I’m expecting you to get it immediately. The example we used in class was to prove that $\sqrt{2}$ is irrational. We assumed that is was in fact rational, and we ended up getting something that was nonsensical… meaning that one of our assumptions didn’t make sense.

Mathematical Proof

Today, we started looking at Chapter 11 in the text. The main idea is that logical proofs can be broken down step by step, sometimes at a level so specific that many of the steps seem obvious (but aren’t).  I added the topic of Euclidean geometry, which we discussed in class (and isn’t in the book). The main axioms we have there are the following.

  1. Given two points, we may draw a line between those points.
  2. Given a line between two points, that line may be extended indefinitely in either direction.
  3. Given a point and a radius (some distance), we can create the circle having the point as the center and containing all points at the radius’ distance from the center.
  4. All right angles are congruent.
  5. Given a point and a line, there exists precisely one line through the point that is parallel to the given line.

I’ll be expending on these in class on Wednesday and Friday. I’ll provide some more detail on the website at that point.

Class Project

We discussed the class project briefly. You will work individually on a topic of your choice, either expanding on something that has been covered in class or following a topic of your own interest related to the spirit of the course. An additional stipulation is that no two students may work on projects that are too closely related. I prefer presentations (10-15 minutes) to the class, but am open to videos that you may produce, and other options. As a last resort, you can write a paper (4-5 pages, with correct citations, etc.). Remember that this is worth 25% of your grade, and you should therefore be trying to impress and interest me. Beyond that, you’re being given a pretty good amount of independence with this project, and my hope is that you take advantage of that and be creative. I’ll give you an example in class on Wednesday (tomorrow).

We reviewed today. I gave the solution to the problem in the homework that asked how many more pairs of people may interact in a city when the population doubles. I also reviewed equivalence relations and the binomial theorem.

We continued to provide some extra material for chapters 16 and 17 and finished looking at Fibonacci numbers. I gave some examples of where these occur in nature and then we talked about the “golden ratio.” I said I’d put the calculation behind deriving the golden ratio online. Here it is.

Computing the Golding Ratio

We take a line of length 1 and we place an $x$ somewhere along that line. The idea is that this $x$ partitions the line. On one side, you have a length of $x$ and on the other you have a length of $1-x$. What we want to do is something a bit weird. We want to make sure that the ratio of the entire line’s length to $x$ is the same as the ratio of $x$ to $1-x$. In other words, we’re trying to find the specific $x$ satisfying the equality


To solve for $x$ here, we cross-multiply (clear denominators), and we get


So, this is equivalent to $x^2+x-1=0$ if we place everything on one side (equating it to zero). We can solve this quadratic in a number of ways. The way I decided to do it in class was with completing the square.

\[\begin{align}x^2+x-1&=0\cr x^2+x+\frac{1}{4}-\frac{1}{4}-0 &=0\cr \left(x^2+x+\frac{1}{4}\right)-\frac{1}{4}-1&=0\cr \left(x+\frac{1}{2}\right)^2-\frac{5}{4}&=0\cr \left(x+\frac{1}{2}\right)^2 &=\frac{5}{4}\cr x+\frac{1}{2}&=\frac{\sqrt{5}}{2}\cr x&=\frac{\sqrt{5}-1}{2}.\end{align}\]

Now, when we take $1/x$, we get the ratio that we’re looking for, which is somewhere around

\[\phi\approx 1.61803398875\]

We also looked at several examples of where this number pops up. There are quite a few surprising examples, both in nature and in the constructed world around us.

We discussed relations and functions, with a bit of review from things that should have been somewhat familiar from algebra. We then discussed equivalence relations and gave some examples and some non-examples.

I introduced the notation

\[nCr = \left({n\atop r}\right).\]

We then used this and showed how it appears in various counting problems. Namely, we have the binomial theorem:

\[(x+y)^n=\left({n\atop 0}\right)x^ny^0+\left({n\atop 1}\right)x^{n-1}y^1+\left({n\atop 2}\right)x^{n-2}y^2+\cdots+\left({n\atop {n-1}}\right)x^1y^{n-1}+\left({n\atop n}\right)x^0y^n.\]

We also considered Pascal’s triangle and Fibonacci numbers, which I will cover in more detail on Monday.

We have already discussed much of Chapter 16 (permutations, combinations, general counting, etc.) and so we continued by formally entering that chapter today.

The Population of the United States

Congratulations! You are one of the few courses, perhaps the only, I have taught where a full half of the students know the population of the United States to within 10%. I asked you to write the population of the United States on a paper and pass it in. We had responses anywhere between 5 million and 1.5 billion. The correct answer, as of July, 2012, is roughly 313,914,000.

What happens when someone doesn’t know the population of their own country? A possible answer, for those that think the United States is big enough to have 1.5 billion people, is that one could potentially feel very distanced from their government.

We performed the same experiment with the population of Colorado, which is roughly 5,187,000. Again, your answers were mostly correct. Good job.

Social Security Numbers

We discussed social security numbers, how they are assigned, how repetitive (or not) they are, and so on. Much of the information I presented in class, beyond the text, can be found in the Wikipedia article. I also discussed telephone numbers in the United States and the difference between how they used to be assigned (for rotary dial, and based on distance) and how they are currently assigned and used.

An oddity with the U.S. system for assigning such numbers: We generally don’t allow them to start in zero.

Today, we finished our hybrid discussion and watched the following video.

We also reviewed logarithms, and the homework for Wednesday will have some problems where you’ll need to use those. For an online review, covering a bit more than we did, see here.