### pigeonhole principle

OK, so as many know, the common pattern for the three problems from the last post is called the “Pigeonhole principle”, and it’s deceptively simple: it says that if you have pigeons and you are trying to fit them into pigeonholes, then there exists at least one pigeonhole with 2 pigeons in it. Sounds simple enough, but then how do you apply this? The trick is to identify and properly define the pigeons, and also define the pigeonholes. In this case, the buckets are the different possible remainder values modulo 11: there are of course 11 pigeonholes.

The 12 distinct integers are the pigeons. And so there exists a pigeonhole with two pigeons in it: since they are distinct integers, their difference is a multiple of 11 (of course, had they been the same number, that would also be true, since 0 is divisible by 11).

What about the problem with the trees? You could have 600,000 pigeonholes, one pigeonhole for each possible value of (number of pine cones in a tree); there are only 600K, because 600K is the max value for the number of pine cones, according to the problem (as my friend Bernard pointed out, this is a wild over-estimate). The pigeons in this problem are the different trees: put a tree in the pigeonhole corresponding to how many pine cones it has. Since there are 1M trees, you have way more than 600K, and so you’ve got many pigeons crammed in the same holes (at least 400K repeats, as Susan’s daughter Evelyn pointed out – great job, Evelyn!).

What about the last problem? This is a slightly tricky one. For now, I’ll give a hint: Let Timer 1 be the timer that goes off every seconds, where is irrational. If I knew that there was an integers and so that the -th and -th firings of Timer 1 happened within seconds of each other, then this means that every firings are exactly seconds apart.

If we’re clever, we can get , and so you could imagine traversing the face of a clock seconds at a time (basically ignoring all firings of Timer 1 except the ones that occur at , , , etc, seconds). How could this help us solve the problem?

Some things to focus on in your solution:

- what are the pigeonholes?
- what are the pigeons?
- why do we insist that is irrational?

* *

Filed under: Patterns | Leave a Comment

### Math Craft

One of my favorite essays on math is an essay by Bill Thurston, entitled On proof and progress in mathematics. In that essay, he refers to the difficulty of even defining what mathematics actually is; as an aside, he offers a proposed definition of mathematics (that he himself is not 100% satisfied with): “the theory of formal patterns.” In a later post, I’ll talk more about Thurston’s article, but for now I want to mainly use that definition as a jump-off point for this post.

I love this definition because I think it goes a long way both towards identifying what mathematics is, as well as de-mystifying the process of doing mathematics. What do I mean by this? Well, for example, for people who are unfamiliar with math, the concept of proving a theorem sounds abstract and intangible; in contrast, identifying a pattern, and then clearly articulating what that pattern is, sounds like something you remember doing with relative ease in elementary school.

The other reason that I like that definition is that it dovetails with my math-as-craft metaphor. Folks in the software industry use the term pattern to describe and identify recurring software problems along with their solutions; their terminology was in turn inspired by the architect Christopher Alexander, who wrote “Each pattern describes a problem which occurs over and over again in our environment, and then describes the core of the solution to that problem, in such a way that you can use this solution a million times over, without ever doing it the same way twice”.

Christopher Alexander’s goal was to propose a sort of aesthetic philosophy of architecture that evoked the crafts of an earlier age: a great carpenter knew, for example, a variety of different joins, and each of these joins was a pattern that could be used in myriad contexts to solve a variety of individual problems. A master carpenter was first and foremost a problem-solver who identified possible solutions, and was able to weigh the trade-offs to each solution, and pick an appropriate solution based on the intended function of the object being made (a wheel barrel? a cask? a table?)

Much of mathematics can be described in exactly this way: in solving a math problem, it’s important to recognize an underlying principle (or pattern) that give that problem its structure.

But this is too abstract, let me give an example. Here are three problems, that on the surface, are dramatically different; I will illustrate how a common principle is key to the solution of the problem:

1) Show that, if you have a set of 12 distinct integers, then this set contains a pair of integers whose difference is divisible by 11.

2) Show that if you have 1,000,000 pine trees in a forest, and no single tree has more than 600,000 pine cones on it, then there must be two trees in the forest that have the exact same number of pine cones.

3) Suppose that I have a timer that goes off every x seconds, where x is an irrational number. Suppose that I have another timer that goes off at exactly y seconds after the beginning of each minute. Show that, if I wait long enough, I can guarantee that both timers go off within half a second of each other (in fact, you can ensure that there is a time when the timers go off within seconds of each other, for arbitrarily small .

I encourage you to try and solve each of these problems. In my next post, I’ll present a pattern that provides a solution to each of these problems. Basically what I’m saying is: when a mathematician is faced with solving one of the above three problems, she pulls out the same tool from her tool-belt as she does for the other two problems.

Now, why did I mention all this? If you are willing to suspend disbelief, and take me on my word (for now, I’ll provide a full justification later) that there *is* a common pattern here, and so my analogy with carpenters has some validity, then you could begin to see how *practicing* using these tools is the way to gain facility, and eventual mastery.

This is a theme that I hope to come to again and again in these posts.

Filed under: Patterns | 3 Comments