Category Archives: puzzles

Skyscrapers

1 Reply

This is a quick post mainly for the benefit of my ‘Developing Mathematical Thinking’ (#math1070) students.

Introducing the puzzle

Skyscrapers are one of my favourite logic puzzles. They are a Japanese creation, introduced at the first World Puzzle Championship1 in 1992.

Skyscraper04

Skyscrapers are a type of Latin Square puzzle. A Latin Square in an n × n grid filled with n different symbols, each occurring exactly once in each row and exactly once in each column. (Sudoku is another type of Latin Square puzzle).

In a Skyscraper puzzle the objective is to place a skyscraper in each square, with heights between 1 and n, so that no two skyscrapers in a row or column have the same height. The numbers (clues) on the outside of the grid tell us how many skyscrapers are visible from that position. (I like to imagine that I’m standing on that number and along the street that is the row/column.) Shorter skyscrapers aren’t visible behind taller ones.

We use logical deductions to solve the puzzle. For example, in the puzzle below, the clue ‘4’ tells us that the skyscrapers must appear in ascending height order in that row/column. Similarly, the clue ‘1’ tells us that the tallest skyscraper must be adjacent to the clue. That leads us to the partially-filled grid below. If you want to solve it yourself, the solution is at the bottom of this post. You can also play them online at Brain Bashers.

Skyscraper04Partial

Hands-on skyscrapers

It is fairly easy to turn a skyscraper puzzle into a hands-on activity — just choose objects of different heights. Teachers often use linking cubes. You can also be more creative; at David Butler‘s One Hundred Factorial gathering at the University of Adelaide in May, we experimented with video cassettes (remember them?) and cups of different sizes.

A while back, I wanted to make several hands-on sets for 5 × 5 grids to use with groups of school students. They needed to be cheap, lightweight, compact and portable. So, I made paper cylinders that nestle inside each other. You can download and print the skyscraper cylinders. The tabs are meant to show where to overlap and tape. You can use them with these puzzles (print A3 size): Puzzle 1, Puzzle 2, Puzzle 3, Puzzle 4, Puzzle 5.

Skyscrapers in the classroom

My plan for MATH 1070 was curtailed by our short week (Week 3). I had planned the activity with these goals:

  • Form visibly random groups with four students so that students could meet a few more classmates.
  • Work collaboratively towards a common goal (and contrast this with the competitive nature of Prime Climb last week.)
  • Practice claims and warrants as part of the focus on Maths Disputes: ‘I think <claim: this number goes here> because <warrant: my reason>.’

There are a variety of reasons to use skyscrapers in the classroom; you might like to read these posts by teachers: Mary Bourassa, Mark Chubb, Sarah Carter. Any activity introduced into the classroom should be intentional. You might like to think about these dot points. Mark has a fuller list in his blog post.

  • If giving these puzzles to individual students is different than to groups of students.
  • If a physical model is different than a pen-and-paper version.
  • If you’ll use it as part of a lesson or as a ‘time filler’.
  • What you’ll do if students give up easily.

If you give them a go, let me know what you think!

[1] Source: www.gmpuzzles.com/blog/skyscrapers-rules-and-info

Skyscraper04Solution

#NoticeWonder and Rational Tangles

1 Reply

Yesterday we held the first of this year’s Maths Experience days. We invite students in Years 10 and 11 from different schools onto campus for an intensive one-day program. Students find out about mathematical research, talk to professionals who use mathematics in their careers in some way, and participate in hands-on mathematics workshops. Importantly, they also meet and connect with other students who enjoy mathematics.

One of the activities I chose for this year was Conway’s Rational Tangles. I’ve previously written detailed notes about running the activity with pre- and in-service teachers.  For the Maths Experience, apart from the inherent fun of ‘playing’ with ropes, I wanted students to have a collaborative and authentic problem-solving experience. I introduced the activity as one that mirrors mathematical research — full of questions, puzzling moments, uncertainty, frustration and hopefully also joy. I emphasised that we might not solve the problem, but that the experience of working mathematically was our goal, which includes making wild conjectures and having out-of-the-box ideas!

In this post I want to highlight one addition I made to the activity described in my earlier blog post — the inclusion of the ‘Notice and Wonder’ prompt1.

I started the session by showing students the short video below, edited from one I found on Youtube by Tom Hildebrand. Specifically, I turned off the sound, cut out the whiteboard, and sped it up significantly. Then I asked the two magic questions: ‘What do you notice? What do you wonder?’ Take 70 seconds to watch the video, and see what you think.

Here is what they noticed.

Group A

  • They are trying to untangle the ropes.
  • One person hangs on to one end of the rope for the whole time.
  • They rotate 90 degrees clockwise.
  • There is a plastic bag.
  • Twist involves exactly two people and occurs in exactly the same position.
  • They untangle using exactly the same types of moves they used to tangle.

Group B

  • Four people holding two ropes.
  • Same person holding the same end for the whole activity.
  • When rotating, one person moves clockwise. (Later refined to each person moves one position clockwise.)
  • The twist movement always involves the two people on the right. The same position goes under each time.
  • There was some pattern they kept repeating.
  • They did some moves to get a knot. Then they did some more moves and there was no knot.
  • There was a bag.
  • There were four rotations before the bag appeared and eight rotations after.
  • Sometimes there is a different number of twists after a rotate.
  • A twist after a rotate goes ‘perpendicular’. (Not sure what that means!)

And here is what they wondered.

Group A

  • What’s the deal with the plastic bag?
  • What’s the deal with the teacher?
  • How did they decide when to stop tangling and start untangling?
  • How tangled was the rope?
  • What did the teacher and the student pass to each other? (Scissors.)
  • How did they work out how to untangle? (I explicitly prompted this question — although I’m sure they were all thinking it.)

Group B

  • How did they know how to untangle the ropes? Was it from memory?
  • What is the point of rotate? It doesn’t seem to change the rope.
  • Does the bag have something to do with the tangling?
  • Is it a proper knot? Or just a tangle?
  • What is the teacher doing?

There was more conversation that I didn’t manage to capture. (Next time I’ll record it!) Group A spent around 10 minutes on Noticing and Wondering. Group B spent 15-20 minutes. We then largely ran the session as I’ve detailed in the earlier blog post.

What effect do I think Notice and Wonder had? I noticed that students were keen to try the problem for themselves. They made sense of the situation, became intrigued and engaged, and then made the problem ‘theirs’. As a group, students saw that others had interesting ideas. They added on to each other’s thinking. I suspect that it also smoothed the way for working together more intensely once we broke into smaller groups where students didn’t necessarily know one another. It also became more natural for them to Notice and Wonder as the session progressed. All in all, it’s a great modification to a thoroughly engaging activity.

[1] I trialled this with teachers at the MASA conference in April.

Tangling and untangling

1 Reply

This is the seventh in a series of posts about my course ‘Developing Mathematical Thinking’, a maths content elective for pre-service teachers training in primary and middle maths. All posts in the series are here. WARNING: It’s a long post.

Edited to fix the confusion between × (multiply) and x (the letter).

I have been itching to try Conway’s Rational Tangles with a group of students. I first read about this problem a couple of years ago in Fawn Nguyen’s excellent post. It looked super interesting, but I was still somewhat confused with how it works (not to mention why it works). So I was excited to be in Fawn’s ‘Conway Tangles’ Math Micro-Session at the NCTM Annual Meeting in San Francisco this year, where it started to make some more sense.

This week I tried the activity with my #math1070 students. I waited until the last week of the course because: (1) now that we know each other better, I thought they’d tolerate me muddling through it, (2) their resilience and problem-solving skills for more challenging and ill-stated problems have increased. (Note that the ‘ill-stated’ part is my fault, not that of the problem!) I was upfront with them about how I was both excited and nervous about the session. It was a bit sketchy with the first group of students, but I was able to make some adjustments with the second group.

Below is a mash up of how I did it this week and how I would improve it in the future. This outline is based on Fawn’s write up, but I also pulled in ideas from Tom Davis’ thorough notes for a Maths Teacher Circle, along with the three-part outline from nrich maths: Twisting and Turning, More Twisting and Turning, All Tangled Up. We spent ~1.5 hours on the activity. Perhaps half of that was outside, with students doing it themselves.

Getting started: the rules

Have four volunteers come to the front. Each person holds the end of a rope so that the two ropes are horizontally parallel. This is the starting position. This state has a value of 0.

IMG_3900.jpg

There are only two moves that can be made: TWIST (T) and ROTATE (R).

A TWIST is when the person at the bottom left moves under the orange rope to the top left, as shown below. This new state has a value of 1. We notate this as 0 \xrightarrow{T} 1. I tell the students that every time a TWIST operation is performed, the value of the ropes increases by 1. So, TWIST is +1.

IMG_3901.jpg

A ROTATE is when every person moves clockwise to the next position, as shown below. (Note that this is from the starting position.) I say that I am not going to tell them the value of this new state. 0 \xrightarrow{R} ?? I’m also not going to tell them what ROTATE does; that’s for them to figure out.

IMG_3900-1.jpg

The ‘aim’

Our aim is to (in my words) ‘tangle the crap out of the ropes’ by performing any number of TWISTS and ROTATES and then work out how to untangle the ropes back to horizontally parallel (with value 0). But, remember that there are only two available moves: TWIST and ROTATE. ‘Untwist’ and ‘Unrotate’ are not possible moves.  (I wrote ‘aim’ because this isn’t the only goal, but it’s the one that students will initially want to work towards.)

At present, we have two questions:
(1) What does ROTATE do?
(2) How to get out of any tangle?

A first go at experimenting with ROTATE

Before I let them loose with some ropes, we try a few more systematic experiments.

We reset the ropes to 0, and try ROTATE followed by ROTATE (RR). We discover that the ropes end up horizontally parallel again. That is, 0 \xrightarrow{R} ?? \xrightarrow{R} 0. We decide not to ever do RR unless we want to waste energy. We test this further by resetting the ropes to 0, and trying TWIST followed by RR. As expected, we end at a state with value of 1. We summarise: 0 \xrightarrow{T} 1 \xrightarrow{R} ?? \xrightarrow{R} 1.

The other possibility after an initial rotate is to try a twist. So we reset the ropes to 0, and try ROTATE followed by TWIST (RT). This action is kind of strange; the ropes stay vertically parallel no matter how many twists we do: 0 \xrightarrow{R} a \xrightarrow{T} a \xrightarrow{T}  \cdots \xrightarrow{T} a.

There are already some interesting conclusions that we could come to as a group, but I decide (based on experience) that it might make more sense if everyone is participating instead of watching.

Trying it for themselves

Students get into groups of at least five: four on the ropes and at least one person recording the steps. I distribute the ropes ($1 each at Kmart; bargain!). We go outside. Maths classes in university are never held outside, so this is novel for all of us.

I suggest that to help answer Question 1 (What does ROTATE do?) we might want to break Question 2 down into further sub-questions.

(1) What does ROTATE do?
(2a) Work out how to get out of one TWIST; two TWISTS; three TWISTS; four TWISTS; any number of TWISTS.
(2b) Work out how to get out of a mixed up sequence, like TTRTTTRT, shown below.

Untitled.jpg

Everyone starts with (2a), and works it out fairly quickly (15 minutes?). Their strategy to untangle is to always start with a ROTATE (otherwise we would be further tangling the rope), then to look at the ropes and ‘see’ what to do next. Eventually they write down how to get out of these positive integer states (T, TT, TTT, TTTT, …) and see a pattern. Try it for yourself! (Or look on page 5 of Tom Davis’ notes.)

In general, my students find it hard to conjecture what ROTATE does. I talk to each individual group in turn. To get them started, I write down something they’ve just done: 0 \xrightarrow{T} 1 \xrightarrow{R} a \xrightarrow{T} 0. We can work backwards from T to realise that a=-1.  We also realise that when we start with just twists, the value of the state keeps increasing from 0. OBSERVATION: To return back to 0, ROTATE must involve a negative somehow.

I suggest perhaps ROTATE is ×(-1). We look at 0 \xrightarrow{T} 1 \xrightarrow{R} -1 \xrightarrow{R} =1. This works!
We test it on one TWIST: 0 \xrightarrow{T} 1 \xrightarrow{R} -1 \xrightarrow{T} 0. This also works.

We predict what should happen with two TWISTS: 0 \xrightarrow{T} 1 \xrightarrow{T} 2 \xrightarrow{R} -2. To get this untangled, we should be able to do TT. We try it with the ropes. Groan as it doesn’t work. (Note that some students have already forgotten that they know how to get out of two twists, from (2a).)

There is more conjecturing about ROTATE. For example, some students try ROTATE is -2. Later in the class discussion we realise that ROTATE can’t involve just adding or subtracting as RR would take us further away from 0 (positive or negative), and we know that 0 \xrightarrow{R} ?? \xrightarrow{R} 0. OBSERVATION: ROTATE must involve multiplication or division (or perhaps some other operation).

Most are still stuck. I ask them if they’ve done (2b) and untangled TTRTTTRT. If so, I tell them that the tangled state has value 3/5. OBSERVATION: ROTATE must involve a negative and fractions somehow. Some more cautious conjecturing eventuates.

If they are still stuck, I tell them that TTRTTR has value -2/3.

After working on it for ~45 minutes, some of them give up and demand the answer. I know there is more problem-solving work to come so I tell those that haven’t worked it out that ROTATE is ×(-1/a), where a is the previous state value.  To summarise:

  • x \xrightarrow{T} x+1
  • x \xrightarrow{R} -\left(\frac{1}{x}\right)

Efficiently getting out of any tangle

I ask them to come up with a scheme to efficiently get out of any tangle. (Later we decide that we aren’t sure that it is the minimum number of moves, but it seems efficient.) It works a bit like this: Get as close to zero with a numerator of 1 and a positive denominator (like 1/m) then ROTATE. This leaves you with a negative integer, –m, and you can TWIST your way m times back to 0.

Wrapping up

Back in the classroom as one group, we summarise what we discovered, and make a few more observations.

  • We go back and think about starting with a single ROTATE. Now that we know what ROTATE does, we see that the state becomes -1/0. This is like infinity. Another ROTATE brings it back to 0. When we start with a single ROTATE, TWIST leaves it exactly the same: \infty + 1 = \infty. So we can have a tangle value of infinity. This is all kind of cool.
  • We wonder if every rational number can be reached through tangles, and then be untangled.
  • We wonder about how to prove the minimum number of moves to get out of each tangle.
  • We talk briefly about function notation: T(x) = x+1 and R(x) = -\left(\frac{1}{x}\right). We confirm that R(R(x)) = x, so two RR leave the state unchanged. We talk about composition of functions, and how RTT is represented by T(T(R(x))).

We talk about how this activity is suitable for a range of students and different areas of focus:

  • problem solving and team work just by trying to untangle a tangle (no investigation into TWIST and ROTATE)
  • practicing fluency with fractions
  • older students can work with function notation and tackle some of the more challenging questions.

I reflect later how there is so much more depth in this activity than I had realised. I also realise that because it has so many different dimensions—physical manipulation, symbolic notation, numerical calculations, pattern recognition, conjecturing, teamwork, leadership—it gave students opportunities to shine in different ways.

How many triangles?

2 Replies

It’s been quiet on the blog, but a lot has been happening. University classes in Adelaide have just resumed after a two week mid-semester break. To warm up, I gave my MATH 1070 students the following problem. I found it via Tanya Khovanova who states that it was an entrance problem for the 2016 MIT PRIMES STEP Program. (Read more on Tanya’s blog.)

I drew several triangles on a piece of paper. First I showed the paper to Lev and asked him how many triangles there were. Lev said 5 and he was right. Then I showed the paper to Sasha and asked him how many triangles there were. Sasha said 3 and he was right. How many triangles are there on the paper? Explain.

Here are some solutions from my students, all considered to be correct. The ones in blue originally appeared in Tanya’s blog post. Additional ideas are shown in red below. The black rectangle shows the piece of paper. Two of the rectangles contain instructions instead of diagrams.

I loved this as an opener to encourage creative problem solving. Thanks Tanya!

How Many Triangles.jpg

 

 

Counting in unexpected ways

2 Replies

It was a delight to recently spend five days working with students and teachers in Alice Springs at the invitation of MTANT, the Mathematics Teachers Association of the Northern Territory. I then spent a week in bed with the flu, which is one reason I’ve recently lost my voice (both physically and online).

The main purpose of the visit was to join the 8th Annual Maths Enrichment Camp at Ti Tree School, in a small remote town 200 km north of Alice Springs. Students travelled from all over Central Australia, some from as far as the Aboriginal community of Hermannsburg, 320 km south (that’s a short distance in the Northern Territory!). The camp runs Friday night to Sunday morning, and is full of fun activities (mathematical and non-mathematical) for kids, and teachers, to engage with. This was my first Maths Camp, and I was thrilled to be invited; thanks @matt_skoss!

IMG_3559

This year the Ti Tree Maths Camp attracted around 35 students from Years 4 to 10. Students were divided into three groups and on Saturday rotated through four activities, called ‘Worlds’. Thus, these activities needed to accommodate a broad range of mathematical expertise. To add extra challenge, I rarely work with students in the lower years, so I relied on a couple of trusted friends to help determine whether my planned modifications would be appropriate.

In this post I briefly describe how younger students responded to two of my favourite activities, which I’ve previously written about: The Game of SET and Domino Circles. I doubt that this is going to be revelationary to most teachers, but I am always learning how students make sense of mathematics (younger students, in particular), so I want to record my observations for the future.

Counting Dominoes

I worked on this problem with a combined group of Years 5 and 6 girls from Bradshaw Primary School and Araluen Christian College in Alice Springs.

Display this image. What do you notice? What do you wonder?

Dominoes

Responses include:

  • I notice: that there different numbers of dots on a domino.
  • I notice: that there are two groups of dots on each domino.
  • I notice: that the dots are different colours.
  • I wonder: what is the highest number of dots on a domino? (A fascinating side discussion commenced as we had to resolve whether we meant in total or on one half of the domino. We decided that in a Double 6 set, the highest number is six. What do you notice and wonder now?)
  • I wonder: what is the lowest number of dots on a domino? (Zero.)
  • I wonder: how many dominoes are there in the set? (My response is usually ‘Good question! I wonder if we can work that out?’ :))
  • I wonder: can a domino have more than one instance of the same number of dots? (Yes — I show a ‘double domino’, like 2|2.)
  • I wonder: is there exactly one of every combination of numbers of dots? (Yes.)

Usually my next question is to ask students to calculate how many dominoes there will be in a set. Some students start by drawing them all out. For this students I might show an image of a Double 18 set—too many to draw, right? This encourages students to find, and then explain, a formula for the number of dominoes in a Double ‘n’ set.

However, for younger students that I hadn’t met before, I was concerned that this question might be too challenging. Instead, I handed out sets of dominoes and asked students to have a look at them. Then I revealed that each set was missing a domino. Could they work out which domino was missing?

As you might expect, students needed to find a way to organise their dominoes so that they could identify the missing one. Several groups made arrangements like this. It’s easy to spot the missing domino now, right? How else could you have arranged the dominoes to make this discovery?

IMG_3719

I gave one large group two sets of dominoes (one paper, one physical) in case they wanted to work in smaller groups. I was delighted to find that they instead used both sets of dominoes in tandem. It looked something like I’ve reproduced in the photo below. Can you spot the missing domino from each set?

IMG_3720

There was an interesting moment in the middle of this activity as we discovered that some sets had more than one domino missing, and some sets had duplicates. (Guess who didn’t double-check the domino sets before starting the activity? <blush>) This could have been a disaster, but I took it as a true problem-solving experience for the group. We sorted out our sets eventually!

The rest of the session was largely spent exploring this question:

Is it possible to arrange an entire set of dominoes in a circle so that touching dominoes have adjacent squares with identical numbers?

Once you’ve experimented with a set of dominoes in which the highest number is six, explore whether it is possible for sets of dominoes where the highest number is different.

You can read more about this problem here.

We finished with a quick ‘Notice and Wonder’ with this short promotional video by Cadbury, in which they set up blocks of chocolate in a suburban street, and knocked them over like dominoes. I wish I could remember all the rich wonderings the students had — they were fabulous!

Counting SET cards

My chosen activity for my ‘World’ at the Ti Tree Maths Camp was The Game of SET. I’ll briefly recap the game, before talking about how students counted their set cards.

SET is a card game. Three of the cards are shown below. What do you notice?

SET Cards 01

Students eventually identify a number of attributes of the cards. Sometimes (but not often) they generate more than we need for the game. I acknowledge them and ask if we can focus on four particular attributes: number, shape, colour and shading. We notice that each attribute has three different values that it can take. For example, shape can be ‘oval’, diamond’ or ‘the squiggly thing’.

I confirm that these are all the possibilities of values of attributes. When I work with students in higher grades, my next question is usually as follows.

If a SET deck contains exactly one card of every possible combination of attributes, how many cards are in a deck?

To adapt this question to lower years, I did something similar to what I did with counting dominoes. But instead of removing a card, I asked them to find a way to be sure that they had exactly one card for every possible combination of attributes in their deck.

Their natural ability to group by features that were the same, and to organise in a systematic way, was not unexpected. But I enjoyed seeing the varied ways they went about this.

For example, these two girls made three rows (shown vertically in the photo). Each row corresponds to a colour. Within each row, they grouped first by shape. For example, all the red diamonds, then all the red squiggles, then all the red ovals. Within each shape they grouped by shading. Within each shading they organised by number. One explanation was that, for a particular colour, they knew that there were nine cards for a particular shape. There were three different shapes. So there were 27 cards in one row. There were three rows of different colours. So there were 27 × 3 = 81 cards.

IMG_3678

Some students started grouping by colour, but in a different way. In this grid, each row corresponds to one particular shape. Each column corresponds to one particular shading. Each ‘entry’ in the grid contains three cards, grouped by number. There were two other grids like this, each for a particular colour. One explanation was that, for a particular colour, we get a 3 × 3 grid where each entry contains 3 cards. So, each grid has 27 cards. There are three different grids, each corresponding to a different colour. So there are 27 × 3 = 81 cards.

IMG_3721

There are four different ways of organising shown in the photo below. In the left bottom half, a student is organising in a way similar to the grid method. Focus on the larger cards in the far right. These girls have nine columns. Each column corresponds to a particular colour and shading combination. For example, the far left column are cards that have purple shapes that are completely filled in. Within each column, they organised the cards in groups of three. The three groups are organised first by shape. Within each group the cards are organised by number. Their explanation is that there are nine columns, each with nine cards. So they have 9 × 9 = 81 cards.

IMG_3677

I loved all these ways — and more not described — that students found to count the number of cards they had in their deck. After students had completed their work, we congregated together and went on a tour of the room. Each smaller group explained to the whole group how they had organised their cards and confirmed that there were 81 cards in the deck.

An unexpected advantage of this approach is that students discovered for themselves how to make a SET, because of the natural ways that they grouped cards. In the game, a SET is a group of three cards where, for each of the four attributes, the features are the same across all three cards or different across all three cards. For example, the three cards below are a SET because shape is all-same, fill is all-same, number is all-different, colour is all-different.

SET Cards 02

Once students understood how to make a SET, we made a new discovery within their work. Consider again the top cards of the 3 × 3 grid shown below. Each row, column and diagonal forms a SET. It’s like a magic square. A magic SET square.

IMG_3721

Meanwhile, the students who organised their cards into a 9 × 9 grid decided to keep their columns the same, but rearrange it so that each row corresponded to a particular number and shading combination. I’ve reproduced it below. With a little bit of prompting from me, they discovered that they had a kind of super magic SET square. Can you see what I mean? So cool!

SET cards

The rest of the session was spent playing the game, and talking over some of our SET-finding and problem-solving strategies. A rough description is here.

What struck me is that these students’ understanding of how to form a SET was much more solid, and developed so much quicker, than many other older students I work with. This is because usually I explain, rather than have them explore. At Maths Camp I was reminded — again — that even in an activity full of moments for discovery, there are still more opportunities to slow down and let students construct knowledge for themselves.

Another party puzzle

3 Replies

More party puzzles! This one is from a thoroughly-recommended book, Puzzle Based Learning1.

Mr and Mrs Smith invited four other couples for a party. When everyone arrived, some of the people in the room shook hands with some of the others. Of course, nobody shook hands with their spouse or themselves, and nobody shook hands with the same person twice.

After that, Mr Smith asked everyone how many times they shook someone’s hand. He received different answers from everybody.

How many times did Mrs Smith shake someone’s hand?

At first glance it seems that there is not enough information to solve the puzzle—which is why I like it! Once we consider each piece of information, we can put the bits together to find a solution.

Warning: mathematical spoilers (but not the solution) ahead. I’ll post the solution in the comments.

Some prompts:

  • How many people are there at the party?
  • What is the minimum number of handshakes possible?
  • What is the maximum number of handshakes possible?
  • Can you draw a diagram to represent the handshakes made by the person who made the most handshakes?
  • What can you conclude from this?
  • What can you add to your diagram?
  • Can you now solve the puzzle?

Good luck!

[1] Michalewicz, Z., Michalewicz, M., Puzzle Based Learning, Hybrid Publishers, 2008. pp 99-102.

Ramsey’s party problem

1 Reply

I love games that require no special equipment because they can be played at a moment’s notice. This is one of my favourite pen-and-paper games. It is played on the complete graph K6. In other words, a board with six dots where each dot is connected to every other dot by a line.

SimBlack

Although the game-board can be drawn up for each game, I like to have pre-printed boards which can be put inside plastic sleeves for use with erasable marker pens.

To play, two players each choose a different colour. They take turns colouring any uncoloured lines between two dots. The first player to complete a triangle made solely of their colour loses.

A natural question to ask when playing games is whether or not there will always be a winner (or loser), or if the game can end in a draw. (We are also often interested in whether there is an advantage in being the first (or second) player.) Play a few times. What do you think?

What I like about this game is that the reasoning required to determine if there will always be a winner is accessible by many children and adults, but it is also the entry point into a rich area of mathematics called Ramsey theory.

Warning: the rest of this post contains mathematical spoilers.

The game described earlier is called Sim, after the mathematician Gustavus Simmons who was the first to propose it. It is also equivalent to a puzzle posed in The American Mathematical Monthly in 1958. ‘Prove that at a gathering of any six people, some three of them are either mutual acquaintances or complete strangers to each other.’ That is, we can represent the six people by six dots. We can colour the lines between two acquaintances in red and the lines between two strangers in blue. The problem now is to prove that no matter how the lines are coloured, we can not avoid producing either a red triangle (between three acquaintances) or a blue triangle (between three strangers).

So, if we can prove that we cannot avoid producing a triangle of either colour, then we have proven that the game can never end in a draw. (In fact, computer search has verified that the second player can win with perfect play.)

Consider the diagram below. There are five edges leaving node A. In a completed game, they will be coloured red or blue. At least three of them must be of the same colour, say red. Now, in triangle ABC, edge BC must be blue (else we have a red triangle). Similarly, in triangle ABD, edge BD must be blue. And, in triangle ACD, edge CD must be blue. But, we have just formed a blue triangle: BCD!

SimProof

We could have posed this question in reverse, that is, what is the minimum number of guests that must be invited to a party so that at least three guests will be acquaintances or at least three guests will be strangers.

The game of Sim shows that it is possible to invite six people to a party and have either at least three guests as acquaintances or at at least three guests as strangers. We can show that this is the minimum number of guests by considering a party with five people and showing that it is possible to have no triangle of the same colour between any three people.

Sim is a demonstration of the Ramsey number R(3,3) = 6. In the language of parties, the Ramsey number R(m,n) = p says that p is the minimum number of guests required at a party so that at least m guests are acquaintances or at least n guests are strangers.

There is a lot written about Ramsey numbers; I’ve barely scratched the surface here. (I first read about them in Martin Gardner’s Colossal Book of Mathematics.) Finding Ramsey numbers is an active area of mathematical research, partly because they are fiendishly hard to calculate. At present, only a handful are known. The last word is for Paul Erdös, the great Hungarian mathematician. (The extract is from The Australian newspaper on Wednesday 21 April 1993 when Australian mathematician Brendan McKay and American colleague Stanislaw Radziszowski found R(4,5)=25).

If an evil demon threatened to destroy the Earth in two years unless we could tell him the value of R(5,5), our correct response, said Erdös, should be to devote all mankind’s resources to the problem — we could probably solve it in two years. But if the demon instead asked us to tell him the value of R(6,6) — then, said Erdös, we should devote all our resources to finding a way to kill the demon.