Tag Archives: pigeonhole principle

Planes, manes and pigeonholes

All aboard?

I was recently travelling on a budget flight with a friend, with no assigned seating. Walking up to the queue, we wondered whether we would be able to sit together. As people joined behind us, my friend, who whole-heartedly detests maths in any disguise, pointed out that we certainly could. To be so full-up to mean that we couldn’t, each row of three would need at least two people sitting in it. Since we could see from the queue that we had more than a third of the passengers still left to board after us, then as long as we weren’t trampled in a boarding stampede, we could certainly sit together.

This was actually a subconscious application of the pigeonhole principle, one of the most intuitive theorems that mathematicians use. It states that if you have N+1 objects to put in N boxes then one of those boxes must contain at least two of the objects.

  

Or if you put M pigeons in N pigeonholes (or envelopes in pigeon-holes) then, if M>N, at least one of the holes has at least two pigeons. So far, the type of maths you wouldn’t be shocked to see explained on television by a primary-coloured puppet.

Continue reading

Advertisements

3 Comments

Filed under Accessible, Maths in Life

Tie Fighters

Noughts and crosses (tic-tac-toe) is quite a boring game. The two main reasons for this are:

  1. Most games end in a draw or tie.
  2. The optimal strategy is too obvious (the first player wants to start in the middle).
With an ulterior mathematical motive in mind, I’d like to introduce you to two games that avoid the first complaint. Whether they address the second is up to you: I’d argue that only Game B, called Sim, does.
Game A 
Let’s call the game triangle-tac-toe. Draw a grid in the shape of a right-angled isosceles triangle whose sides are five squares across (giving 15 squares in total). A board-drawing hint: draw five rectangles.
Starting grid
Take turns to add noughts or crosses as in traditional tic-tac-toe. A player wins when three of their marks form the corners of a right-angled isosceles triangle of any size in the same orientation as the board (the corners may be touching or spread out).
Some of the possible ways for Crosses to win.
Game B (Sim)
Draw six points in a hexagonal arrangement. Optionally, lightly join each possible pair of points (a total of 15 lines) with dotted lines—don’t worry whether three cross lines in the middle or not, but double check that each point has five lines coming out of it.
Sim starting layout
Players pick their favourite colours (we’ll use the traditional Red and Blue), and take turns drawing a straight line in their chosen hue between two points (that haven’t already been connected). A player loses if they form a triangle of their colour between any three of the hexagon’s vertices.
End of a sample game—Red loses due to the highlighted triangle
Animation of the sample game above (click if not playing)

2 Comments

Filed under Accessible