Absolute Chaos is Impossible!

(This is a talk I presented for the Classroom Adventures lecture series on January 17, 2014, for high school teachers.)

(Apparently the video of this talk will be made available online. I will link it when it is available.)

The Ramsey Games

Game 1 – Four points

Take four points and put them in a square. By attaching a blue edge or a red edge between each pair of points try to make a configuartion that is “as chaotic as possible”. Whoa! Hold on, I should be careful what I’m saying. You might just try this (Artist: gretzky ). Well, whatever, interpret “chaos” however you want, this first time.

Okay, let me give you a bit more guidance. Draw 4 more points, and this time, by “chaos” I mean: “try to avoid patterns”. Interpret that however you like.

Go ahead, don’t be shy.

Now, go ahead and look at your beautiful art. Does it have any blue “triangles” or red “triangles”? Here by “red triangle” I mean three points where all 3 edges between the three points are red.

If yours has a red triangle or a blue triangle try again! See if you can find a configuration without a red triangle or a blue triangle.

If yours does not have a red triangle or a blue triangle, then you have discovered a very chaotic arrangment! You have found an arrangment that doesn’t have the “triangle” pattern.

Game 2 – Five Points

Now before we go on, I need to simplify the words “blue triangle or red triangle”. Rather than say “blue or red triangle” I will say mono-chromatic triangle (etymology: Greek: mono meaning one, chrome meaning colour).

Ok, now draw 5 points on your sheet and try to avoid monochromatic triangles.

This is definitely a bit trickier, as now there are just way more edges (how many more?) that are trying to foil you. It can be done though! If you can’t get one of the chaotic patterns for this one, don’t sweat it. I’ll show you a chaotic arrangement later. (By the way, the etymology for “Chaos” is neat! )

Game 3 – Six Points

Alright, let’s get to the main point. Try this again with 6 points (“Mike, you’re killing me…”). Try to avoid triangles this time!

Well, this time it’s actually impossible! No matter how you try to put the edges in you will always end up with a monochromatic triangle. You can find a (beautiful) proof here, but the thing to realize is that if we have too many things (edges in this case) then patterns always show up (triangles in this case). This is a way in which absolute chaos is impossible.

If we have too many things then patterns always show up.

Now let’s take this cool fact in a couple of different directions:

What is a “real world” application of this?

In any group of six people you can always find 3 people who have all spoken to each other before (friends), or who have never spoken to each other (strangers).

What are some other questions that are related to this?

  • What happens when we have 7 points? 8 points? A million points?
  • What happens when we add a third colour?
  • What happens if we try to only avoid patterns that are more complicated than triangles? For example what if we try to avoid “cubes” or “tetrahedrons”?

These turn out to get really complicated really quickly! Here are some easier questions:

  • How many edges are there when we completely draw in an arrangement with six points?
  • How many different ways are there to colour the edges red and blue? Would it be feasible to get a computer to check all of these configurations?
  • Can you write a computer program that checks an arrangement for monochromatic triangles?

These are all good questions. A good place to start investigating this is on the Wikipedia article for Ramsey’s Theorem.

Let’s turn this into a game!

This can be turned into a game called Sim. The idea is that one player plays red edges, and the other plays blue edges. If you make a triangle of your colour: You lose!

You can read more about that game on the Wikipedia Article for the Sim Game.

Different kinds of Chaos

Now let’s look at chaos from a similar, related, but different perspective. Here’s the so-called Pigeonhole Principle:

If you try to put 7 pigeons into 6 boxes, then there will be (at least one) box with (at least two) pigeons in it.

An equivalent statement is:

There is no way to place 7 pigeons into 6 boxes so that each box has 0 or 1 pigeon in it.

Of course, 7 and 6 aren’t the important things here, and we get the “real” Pigeonhole Principle here:

If you have more pigeons than boxes, and try to put the pigeons in the boxes, then you will have a box with at least two pigeons in it.

This is a kind of remarkable theorem. It seems completely obvious, but turns out to show up in all sorts of neat applications!

First some “cute” applications!

Fact 1: There are two (non-bald) people in Toronto with the same number of hairs on their head.

Proof. The internet tells me that there are ~ 2.5 million people in Toronto and each person has less than 250 000 hairs on their head (average is about ~100 000).

So what are our pigeons and boxes?

The pigeons will be the people in Toronto, and the boxes will be the number of hairs on a person’s head. Since 250000 < 2.5 million there must be a box with at least two people in it. So those two people must have the same number of hairs on their head. [END]

This raises some interesting questions:

  • Is this a convincing proof? Should I believe it?
  • Is it practical to accomplish? Does that matter in a “good” proof?
  • Is there a proof of this fact that is feasible to actually carry out?

Fact 2: If 27 Canadian teachers show up to workshop, at least 3 of them will be from the same province or territory.

This suggests a more powerful pigeonhole principle. In the above fact we see that since 13 \cdot 2 < 27 , then there must be a province that has at least 3 representatives.

Trying to actually extract the precise statement of this generalized pigeonhole principle is a nice exercise. For reference, here it is:

If we have N pigeonholes and at least N \cdot K+1 pigeons each in a pigeonhole, THEN there is a pigeonhole with at least K+1 pigeons in it.

From these pigeonhole principle statements we start to get a sense of how adding a lot of objects (or pigeons) increases the strength or frequency of the relationships of those objects.

A challenging problem involving the Pigeonhole principle

Problem. Kane solved 45 math problems in November, and he solved at least one a day. Show that there was a streak of days where he solved exactly 14 problems.

SOL. There is a clever idea hidden in here that is also useful for efficient coding. If you have a list of 30 things (like amount of problems solved in a day) and need to keep track of the sum of consecutive things you only need to keep track of sums starting from the beginning.

e.g. d_1, d_1 + d_2, d_1 + d_2 + d_3, \ldots, d_1 + d_2 + \ldots + d_{30}

Now if d_i is the amount of problems solved on day i and s_i = d_1 + \ldots + d_i , then to figure out how many problems solved between day i and day j we only need to look at s_j - s_i = d_{i+1} + \ldots + d_{j} .

Back to our problem, we need to find i,j between 1 and 30 so that s_j - s_i = 14 . Or in other words, s_j = s_i + 14 .

Notice first that since Kane solves at least one problem a day, we have:
\displaystyle  1 \leq s_1 < s_2 < \ldots < s_{30} = 45
and so also,
\displaystyle  15 \leq s_1 +14 < s_2 + 14 < \ldots < s_{30} + 14 = 59

Now, we notice that the 60 numbers s_1, s_2, \ldots, s_{30}, s_1 + 14, s_2 + 14, \ldots, s_{30} + 14 must all be between 1 and 59 . By the pigeonhole principle there must be two that are equal. Our previous inequalities tell us that it must be one of the s_i and one the s_j + 14 . As desired.

Resources

If you’re interested in the problem solving aspects of the pigonhole princple, please see the talk I gave at the Canadian IMO Winter Camp. It contains many other problems of various difficulties and nice pictures!

One thought on “Absolute Chaos is Impossible!”

  1. Hello sir,
    Thank you for your nice posting.Take four points and put them in a square. By attaching a blue edge or a red edge between each pair of points try to make a configuartion that is “as chaotic as possible”. Whoa! Hold on, I should be careful what I’m saying.
    Thanks………….

    Like

Comments are closed.