Happy Halloween! It’s that time of year in which we celebrate ghosts, pumpkins, and fear itself. So, what better time to discuss a very common fear among adults these days: Mathematics!

If you’re reading this blog, I’m guessing you’re probably already not too afraid of mathematics. But I hope you share this post with people who are somewhat spooked by it but like to face their fears now and then. And let’s face it, even for math lovers, every difficult-sounding math problem is always a little scary at first… until you work it out and realize that there’s only beauty behind the mask.

I recently made up the following problem for a friend teaching a discrete mathematics class:

Five kids, dressed as a Ghost, a Witch, a Monster, a Skeleton, and a Black Cat, knock at your door. You open it and welcome them in, but you realize you only have $3$ Snickers bars and $3$ Kit Kats left in your candy stash!

Since you have $6$ pieces of candy and there are only $5$ kids, you decide to give both a Kit Kat and a Snickers bar to the scariest costume, and then give the remaining four kids one piece each. How many different ways can you choose who to give what candy to?

Eeek! Ghosts and witches! And combinatorics!

Well, let’s consider. There are $5$ ways you can decide on the scariest costume, since there are $5$ kids to choose from. But for each of those choices, you also have to pick which two of the remaining four get the Kit Kat and which two get the Snickers.

To make this a little easier, suppose we picked the Ghost as the scariest, and so we have to choose which two of the Witch, Monster, Skeleton, and Cat get the Snickers bars (and then the other two will get the Kit Kat). Well, we could pick one of the following options:
1. Witch and Monster
2. Witch and Skeleton
3. Witch and Cat
4. Monster and Skeleton
5. Monster and Cat
6. Skeleton and Cat.
(Notice that I ordered these by first choosing all those that can pair with the Witch, and then all those without the Witch, to make sure I didn’t miss any.)

So there are $6$ ways to choose who gets the Snickers and who gets the Kit Kats, assuming we chose Ghost as Scariest. But this is the same computation no matter who of the $5$ we chose as Scariest. If we chose the Witch as scariest there would still be $6$ possibilities, and same for the other three. Therefore, there are $5\cdot 6=30$ total possibilities.

The nice thing here is that there’s a known formula for computing the $6$ possibilities for the Kit Kats and Snickers – the number of ways of choosing $2$ things out of $4$ things is written $\binom{4}{2}$, pronounced “four choose two”. The formula for $\binom{a}{b}$, the number of ways to choose $b$ things from $a$ things, is known to be $\frac{a!}{b!\cdot (a-b)!}$ where $n!$ means the product of all the numbers from $1$ to $n$. So to compute $\binom{4}{2}$, we just compute $$\frac{4!}{2!\cdot 2!}=\frac{1\cdot 2 \cdot 3 \cdot 4}{1\cdot 2 \cdot 1\cdot 2}=6.$$ This is a shortcut for counting the possibilities without listing them all out.

Can you see why the formula for computing $\binom{a}{b}$ is true?

Education is a difficult task, it really is. Teaching takes a few tries to get the hang of. Writing textbooks is even harder. And math is one of those technical fields in which human error is hard to avoid. So usually, when I see a mistake in a math text, it doesn’t bother me much.

But some things just hurt my soul.

No correspondence between the integers and rationals? Yes there is, Example 2! Yes there is!

This horrifying falsehood was stated in the supplementary “Study Guide and Intervention” worksheet for the Glencoe/McGraw-Hill Algebra 2 textbook, and recently pointed out on Reddit. Or at least it was stated in some version of this worksheet. The original file can be found online at various websites, including one download link from Glencoe’s website that shows up on a Google search. There are other versions of the document that don’t contain this example, but this version was almost certainly used in some high schools, as the Reddit thread claims.

Luckily, mathematicians are here to set the record straight. The Wolfram blog published a fantastic post about this error already, with several proofs of the countability of the rationals. There are also several excellent older expositions on this topic, including on the Math Less Traveled and the Division by Zero blogs. I’ll discuss two of my favorites here as well.

But first, let’s talk about what is wrong with the argument in Example 2. The author is correct in stating that listing all the rationals in order would make a one-to-one and onto correspondence between the rationals and integers, and so they try to do so in a random way and failed. At that point, instead of trying a different ordering, they gave up and figured it couldn’t be done! That’s not a proof, or even logically sound (as my students at this year’s Prove it! Math Academy would certainly recognize.)

If one were going to try to prove that a certain set couldn’t be organized into a list, a common tactic would be to use proof by contradiction: assume there was a way to list them, and then show that something goes wrong and you get a contradiction. Of course, this wouldn’t work either in the case of the rationals, because they can be listed.

So let’s discuss a correct solution.

Getting our definitions straight

First, let’s state the precise meaning of a one-to-one and onto correspondence. A function $f$ from a set $A$ to a set $B$, written $f:A\to B$, is an assignment of each element of $a\in A$ to an element $f(a)\in B$. To clear up another misuse of notation in the Glencoe Algebra textbook, the set $A$ is called the domain and $B$ is called the codomain (not the range, as Glencoe would have you think – the range refers to the set of elements of $B$ that are assigned to by the function.) A function is:

• One-to-one, or injective, if no two elements of $A$ are assigned to the same element of $B$, i.e., if $f(x)=f(y)$ then $x=y$.
• Onto, or surjective, if every element of $B$ is mapped to, i.e., for all $b\in B$, there exists $a\in A$ such that $f(a)=b$.

For instance, if $\mathbb{Z}$ denotes the set of integers, the function $f:\mathbb{Z}\to \mathbb{Z}$ defined by $f(x)=2x$ is injective, since if $2x=2y$ then $x=y$. However, it is not surjective, since an odd number like $3$ is not equal to $2x$ for any integer $x$.

A function which is both injective and surjective is said to be bijective, and is called a bijection. This is just a shorter way of saying “one-to-one and onto correspondence,” which is wordy and cumbersome.

So, we want to find a bijection $f:\mathbb{Z}\to \mathbb{Q}$, where $\mathbb{Z}$ denotes the integers and $\mathbb{Q}$ the rationals. Notice that we can list all the integers in order: $$0,1,-1,2,-2,3,-3,\ldots$$
and so if we list all the rationals in order, $r_0,r_1,r_2,\ldots$, we can define the function $f$ accordingly by $f(0)=r_0$, $f(1)=r_1$, $f(-1)=r_2$, and so on. The function will be bijective if and only if every rational number appears in the list exactly once.

Next, let’s be precise about the rationals. Recall that the rational numbers are those numbers which can be written as fractions $a/b$ where $a$ and $b$ are integers with $b\neq 0$. In order to assign every rational number a unique representation, let us restrict to the case where $b>0$ and $a$ is any integer such that $\mathrm{gcd}(a,b)=1$. This condition makes $a/b$ into a reduced fraction. So the number $2/-4$ should be written as $-1/2$ in this convention. It follows that we can think of the set of rational numbers as the set $$\mathbb{Q}=\{(a,b) | b>0\text{ and }\mathrm{gcd}(a,b)=1\text{ and }a,b\in \mathbb{Z}\}.$$

Listing the rationals, naively

One way to construct this list is to think of the rationals as ordered pairs $(a,b)$ of integers with $b>0$ and $\mathrm{gcd}(a,b)=1$ as described above. There is an easy way of ordering all pairs of integers – plot them on a coordinate plane, and use a spiral!

Now, to list the rationals, follow the spiral from $(0,0)$ outwards. Each time we reach an ordered pair of integers, say $(a,b)$, write it down if $b>0$ and $\mathrm{gcd}(a,b)=1$, and otherwise skip it and move on. (These are the green dots above.) This process guarantees that we list all the rationals exactly once.

More elegant methods

There are many other elegant enumerations of the rationals, and one particularly nice one is due to Calkin and Wilf. They construct a binary tree in which each rational number appears exactly once, as shown below.

The tree is constructed as follows: start with $1/1$ at the top, and for each node $a/b$ in the tree, assign it the left and right children $a/(a+b)$ and $(a+b)/b$ respectively. This tree turns out to contain every positive rational number exactly once. It also has an incredible property: if we read the entries of each row of the tree successively from left to right, the denominator of each entry will match the numerator of the next entry, giving us a sequence of numerators/denominators:
$$1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,\ldots$$ such that the consecutive quotients give us a list of the positive rationals.

This makes me wonder is whether there is a way of listing the integers such that (a) every integer occurs exactly once in the sequence, and (b) the consecutive quotients give all rationals exactly once (allowing the consecutive integers to have common factors greater than one). Thoughts?

In the first week of teaching my Calculus 1 discussion section this term, I decided to give the students a Precalc Review Worksheet. Its purpose was to refresh their memories of the basics of arithmetic, algebra, and trigonometry, and see what they had remembered from high school.

Surprisingly, it was the arithmetic part that they had the most trouble with. Not things like multiplication and long division of large numbers – those things are taught well in our grade schools – but when they encountered a complicated multi-step arithmetic problem such as the first problem on the worksheet, they were stumped:

Simplify: $1+2-3\cdot 4/5+4/3\cdot 2-1$

Gradually, some of the groups began to solve the problem. But some claimed it was $-16/15$, others guessed that it was $34/15$, and yet others insisted that it was $-46/15$. Who was correct? And why were they all getting different answers despite carefully checking over their work?

The answer is that the arithmetic simplification procedure that one learns in grade school is ambiguous and sometimes incorrect. In American public schools, students are taught the acronym “PEMDAS”, which stands for Parentheses, Exponents, Multiplication, Division, Addition, Subtraction. This is called the order of operations, which tells you which arithmetic operations to perform first by convention, so that we all agree on what the expression above should mean.

But PEMDAS doesn’t work properly in all cases. (This has already been wonderfully demonstrated in several YouTube videos such as this one, but I feel it is good to re-iterate the explanation in as many places as possible.) To illustrate the problem, consider the computation $6-2+3$. Here we’re starting with $6$, taking away $2$, and adding back $3$, so we should end up with $7$. This is what any modern calculator will tell you as well (try typing it into Google!) But if you follow PEMDAS to the letter, it tells you that addition comes before subtraction, and so we would add $2+3$ first to get $5$, and then end up with $6-5=1$.

Even worse, what happens if we try to do $6-3-2$? We should end up with $1$ since we are taking away $2$ and $3$ from $6$, and yet if we choose another order in which to do a subtraction first, say $6-(3-2)=6-1$, we get $5$. So, subtraction can’t even properly be done before itself, and the PEMDAS rule does not deal with that ambiguity.

Mathematicians have a better convention that fixes all of this. What we’re really doing when we’re subtracting is adding a negative number: $6-2+3$ is just $6+(-2)+3$. This eliminates the ambiguity; addition is commutative and associative, meaning no matter what order we choose to add several things together, the answer will always be the same. In this case, we could either do $6+(-2)=4$ and $4+3=7$ to get the answer of $7$, or we could do $(-2)+3$ first to get $1$ and then add that to $6$ to get $7$. We could even add the $6$ and the $3$ first to get $9$, and then add $-2$, and we’d once again end up with $7$. So now we always get the same answer!

There’s a similar problem with division. Is $4/3/2$ equal to $4/(3/2)=8/3$, or is it equal to $(4/3)/2=2/3$? PEMDAS doesn’t give us a definite answer here, and has the further problem of making $4/3\cdot 2$ come out to $4/(3\cdot 2)=2/3$, which again disagrees with Google Calculator. As in the case of subtraction, the fix is to turn all division problems into multiplication problems: we should think of division as multiplying by a reciprocal. So in the exercise I gave my students, we’d have $4/3\cdot 2=4\cdot \frac{1}{3}\cdot 2=\frac{8}{3}$, and all the confusion is removed.

To finish the problem, then, we would write
$$\begin{eqnarray*}
1+2-3\cdot 4/5+4/3\cdot 2-1&=&1+2+(-\frac{12}{5})+\frac{8}{3}+(-1) \\
&=&2+\frac{-36+40}{15} \\
&=&\frac{34}{15}.
\end{eqnarray*}
$$

The only thing we need to do now is come up with a new acronym. We still follow the convention that Parentheses, Exponents, Multiplication, and Addition come in that order, but we no longer have division and subtraction since we replaced them with better operators. So that would be simply PEMA. But that’s not quite as catchy, so perhaps we could add in the “reciprocal” and “negation” rules to call it PERMNA instead. If you have something even more catchy, post it in the comments below!

“I hardly ever use all the math I’ve learned these days – I’m thrilled if I ever get to compute so much as a derivative. Trigonometry is about the extent of what I need. I wish I encountered more math in what I do.”

I heard this while running with the Berkeley Running Club this week, jogging alongside one of the runners who works as an engineer. As a mathematician, I was quite struck by his statement.

It reminded me that the American educational system naturally leads one to conclude that math is some sort of linear process: first you have to learn your arithmetic and memorize your multiplication tables, then you learn algebra and how to recite the quadratic formula off the top of your head, and later you memorize a bunch of trig identities and learn triangle rules like Side Angle Side. Finally you’re put in precalculus to prepare you for the Holy Grail – Calculus – which only the really smart high school kids and the science-y college kids learn.

And there’s nothing beyond Calculus, right? Unless you’re some kind of crazy math genius.

But as every mathematician knows, nothing can be further from the truth. There are so many simple concepts in mathematics that just about anyone can learn, that are far more useful in everyday life than algebra or trigonometry, and that, sadly, are not taught as part of this linear march towards Calculus. One such concept is modular arithmetic!

Days of the week and remainders

Suppose you want to know what day of the week it will be 100 days from today. How would you figure this out? You could look at your calendar and count the days one by one, but that would take a while. A slightly better approach is to use the number of days in each month (“30 days has September…”) to figure out what the date will be 100 days from today, and then look at your calendar to find that date. But this is also rather cumbersome.

As a better approach, we know that every 7 days, we will be back to the same day of the week. So if you start on a Thursday, after 7 days it will also be Thursday, and after 14 days it will still be Thursday, and so on. The smallest multiple of 7 less than 100 is 98, so 98 days from today, it will be a Thursday. (Yes, I am writing this post on a Thursday.) Therefore, 100 days from today it will be a Saturday.

What we’re really doing here is computing the remainder when 100 is divided by 7. The quotient is 14, and 7 times 14 is 98, so the remainder is 2. So the day of the week it will be 100 days from today is the same as the day of the week it will be 2 days from today, namely Saturday. This is the basic concept of modular arithmetic, the art of computing remainders.

The basics

Let’s set up some convenient notation. We’ll write “$a\bmod b$” to denote the remainder when $a$ is divided by $b$. Some examples:
$$100\bmod 7=2$$ $$26\bmod 5=1$$ $$4\bmod 9=4$$ And so on.

We’ll also call $b$ the modulus – in the days of the week problem the modulus was $7$ – and when we’re taking something mod $b$, we sometimes say we’re “working mod $b$” or “modulo $b$”. Furthermore, when working mod $b$, it sometimes becomes cumbersome to keep writing “$\bmod b$” in our computations, so we’ll also just write “$a\equiv c$” when $a$ and $c$ have the same remainder mod $b$. For instance, if we are working mod $7$, we have $100\equiv 2$ and $12\equiv 19\equiv 5$.

Now, there are three main “modular arithmetic rules” that help us compute remainders quickly:

1. Subtracting or adding multiples of $b$ to a number doesn’t change the remainder when dividing by $b$.
2. When computing sums mod $b$, we can reduce each of the summands mod $b$ first before adding and taking the remainder. Formally, when working mod $b$, $$a+c\equiv a\bmod b + c\bmod b$$
3. When computing products mod $b$, we can also take the factors mod $b$ before multiplying: $$a\cdot c \equiv (a \bmod b) \cdot (c\bmod b)$$

The first fact makes sense: for instance, if we’re working mod $7$, the numbers $9$ and $16$ have the same remainder because they differ by a multiple of $7$. Can you see why the other two are true? (See page 2 for proofs.)

Using modular arithmetic: Factor first!

Let’s try applying the third rule above to our days of the week problem. We can factor $100$ as $10\cdot 10$, and the third rule says that we can reduce the $10$’s mod $7$ without changing the remainder of the product. So, working mod $7$, $$10\cdot 10\equiv 3\cdot 3=9,$$ and $9\bmod 7=2$. See how easy? No long division or 98’s involved.

Okay, you might say, but it’s not that hard to divide $100$ by $7$. Well, what if I asked you what day of the week it will be $1000$ days from now? Now you can instantly figure out that it will be a Wednesday, because, working mod $7$, we have
$$\begin{eqnarray*}
1000&=&10\cdot 10\cdot 10\\
&\equiv& 3\cdot 3\cdot 3 \\
&\equiv& 9\cdot 3 \\
&\equiv& 2\cdot 3 \\
&\equiv& 6
\end{eqnarray*}$$ and so it’s the same as going $6$ days forward from Thursday, which lands you at Wednesday. Voila!

Breaking into sums

That’s all fine and dandy for powers of $10$, but what if the number doesn’t factor so nicely? For instance, there are $365$ days in a (non-leap) year. What if we wanted to know what day of the week it will be exactly one year from today?

Rather than trying to factor $365$ in some nice way, let’s break it up as a sum first, and simplify everything modulo $7$ as we go.
$$\begin{eqnarray*}
365&=&300+60+5 \\
&\equiv& 3\cdot 10\cdot 10 + 6\cdot 10 + 5 \\
&\equiv& 3\cdot 3\cdot 3 + 6\cdot 3 + 5 \\
&\equiv& 6+18+5 \\
&\equiv& 29 \\
&\equiv& 1
\end{eqnarray*}$$ Therefore, exactly one year from today, it will be a Friday.

Summing up…

Notice that modular arithmetic comes up in other natural scenarios too. For instance, clocks work on a 12-hour cycle. If we want to know what hour it will be $400$ hours from now, we can work mod $12$ and find out and find that $400$ has a remainder of $4$, so we can simply add $4$ hours to the current hour instead.

As another application, modular arithmetic can be used as a quick check for catching your arithmetic mistakes. Looking at numbers mod $10$ is very useful. Notice that any number mod $10$ is just its units digit. So, if you’re multiplying $172$ by $288$, you know that the answer will end in a $6$, because the product of the units digits of the two numbers is $$2\cdot 8=16\equiv 6$$ mod $10$. So if your answer didn’t end in a $6$, you know you must have hit the wrong button on your calculator when entering the numbers.

As you can see, modular arithmetic is an incredibly useful tool. I find myself doing quick mental calculations over some modulus all the time, and not just when I’m working on abstract mathematics. Hopefully you will find it useful as well. For now, I’ll leave you with this fun modular arithmetic problem: What day of the week will it be $2^{100}$ days from today?

(For proofs of rules 2 and 3 above, see the next page.)

It’s Tax Day here in the United States, and I spent a larger portion of the past weekend than I would have liked filling out the appropriate forms. But even among tax forms and legal documents you can find a mathematical gemstone or two!

The instructions for filling out, say, IRS form 1040, are rather peculiar in that they try give the reader very simple mathematical operations to carry out, one at a time, to end up with a complicated function of many variables. As far as I could tell, the valid operations are:

• Entering a value for a variable (e.g. income, standard deduction, etc.)
• $+$: Addition of two entries
• $\times$: Multiplication
• $\min$: Taking the minimum of two entries
• $\overset{\cdot}{-}$: A modified version of subtraction, where $a \overset{\cdot}{-} b$ is defined to be $a-b$ if $a\ge b$ and $0$ otherwise.

I found it interesting that every complicated tax computing formula can be broken down into steps of this form. In fact, it says something about the tax formulae: they can all be written as a composition of addition, multiplication, scalar multiplication, min, and $\overset{\cdot}{-}$.

The most interesting of the operations is $\overset{\cdot}{-}$, which is pronounced “monus”. According to the Wikipedia article on monus, the monus operation can in fact be defined on any commutative monoid $C$ in which the relation $\le$ (defined by $a\le b$ if and only if there exists $c\in C$ for which $a+c=b$) is a partial order. This is certainly true for the nonnegative real numbers, which seems to be the domain of operation of the IRS.

The nicest fact about monus in this context, however, is that we can express $\min$ in terms of it:

$$\min(a,b)=a\overset{\cdot}{-} (a\overset{\cdot}{-} b)$$

This means that every tax formula can be written as a polynomial in several variables in which we replace minus by monus! Let’s call such polynomials “Monus polynomials”. So one example of a monus polynomial would be:

$$2xy+x^2yz\overset{\cdot}{-} 3z^3$$

This opens up a plethora of interesting questions. What are the properties of monus polynomials? Are there nice analogues of theorems such as the fundamental theorem of algebra from the classical case? Can we define monus-algebraic field extensions?

This may indeed be an interesting field of study, because tropical polynomials are a special case of monus polynomials, written using only $+$ and $\min$. Who knew that tropical geometry would arise so naturally in the study of IRS Form 1040?

I spent most of Spring Break hiking in Death Valley National Park with Bryan Gillespie. It was stunningly beautiful and rather otherworldly in some ways, especially in the way that so much hardy desert life keeps on surviving on 1.5 inches of rainfall per year.

One such hardy desert plant that we encountered a number of times, especially near the Ubehebe Crater, was the creosote bush. It looked like this:

Bryan’s first reaction was, “Wow, look at the way it grows! I’d love to know what its fractal structure is.” He walked around the plant and took several more photos:

It appeared that whatever angle you viewed the bush from, there was (approximately) a single layer of leaves visible with no leaf covering another and no big gaps between the leaves. This, we realized, is an optimal use of its resources: no matter the angle of the sun, it is using every leaf to absorb its energies while not wasting water keeping other buried leaves alive.

This phenomenon is known for leaf growth around a single straight stem, for instance, and results in leaves budding from a stem at angles forming a Fibonacci spiral. (See, for instance, the bottom of this page.) However, the branches of this creosote bush seemed gnarled and tangled and it was unclear what mathematical rules governed how they distributed themselves so as to optimize their leaf placement.

I’ve stared at the photos for a while now, and I believe that each of the “main” branches that stem from the roots has a fractal (self-similar) structure with leaves on the tips, and these main branches are tangled together in such a way as to make leaf distribution optimal independent of the angle of the sun. But how do we model that? Even more curiously, on inspecting close-up shots like this one, they seem to have “nodes” along their branches and a branching pattern different from the standard Fibonnacci pattern described here.

I would venture to guess that the new branches split at each new node, but only some of the split-off portions are kept, resulting in a long gnarled branch that is slightly bent at each node, with leaves only on the ends. This is purely speculation, though. If anyone out there knows more about the mathematics of creosote growth (or has more data), please share!

I volunteered at the Julia Robinson Math Festival held at a nearby school last Saturday. It was a great event for kids in 4th to 9th grade in the area, featuring a room full of mathematical activity tables and raffle tickets to be given out as rewards for a good idea or explanation.

The table I was working at featured a number of problems about a “mad veterinarian”. He had a machine that you can feed two cats to and get a dog out. You can also feed it two dogs to get one dog out, and if you feed it a cat and a dog, you get out a cat. The veterinarian wants to end up with only one cat, and no other animals. Can he do this starting with three cats and one dog? How about four cats and two dogs?

After playing around with this a bit, one realizes that a simple parity argument shows which starting positions he can get just one cat from. But here’s a harder question:

He built a new machine that now can only accept two different types of animals, and returns either a dog, a cat, or a mouse, as follows. If you feed it a cat and a dog, you get out a mouse. If you feed it a dog and a mouse, you get out a cat. If you feed it a mouse and a cat, you get out a dog. Now, for which starting numbers of cats, dogs, and mice can he end up with exactly one cat in the end (and no other animals)?

Needless to say, it was a fun morning of mathematics. 🙂

It’s not springtime just yet, but I found myself nerd sniped this week by an easter egg in my favorite LaTeX editor, TeXStudio.

I had to reinstall it recently, and my customized advanced configurations were set back to the defaults. So I opened the Options -> Configure TeXStudio menu, and tried to click on the “Show advanced options” checkbox. This is what popped up:

That’s right, a “Riddle” window popped up with the following problem:

You come to a magic island where you meet three strange and wise friends.
One of them is always telling the truth, another one is always lying, and the third is deaf, so he answers randomly and cannot lie(!).
You ask the first: “Are you lying?” and he answers: “No”.
You ask the second: “Is the first one lying?” and he answers: “No”.
You ask the third: “Is the second one lying?” and he answers: “No”.

Which one of the three wise [friends] will always tell the truth?

I thought it was a great idea — giving the user a riddle to solve as a way of saying, “Think carefully before you mess around with the advanced options!” If you type in the correct answer (1, 2, or 3) then it will let you edit the advanced options, and otherwise it will send you back to the basic options screen.

Of course I had to solve the problem rather than just guessing 1, 2, or 3 until it let me through. And I won’t spoil it with an answer here… have fun!