One basket or group photo
Problem
Image
|
A school photographer is taking a photograph of the two basketball teams. She has to arrange ten people, all of different heights, in two rows of five, one behind the other. Each person at the back must be taller than the person directly in front of them. Along the rows the heights must increase from left to right.
In how many ways can two, four or six people to be arranged in this way for a photo, or eight people? In how many ways can the ten team members be arranged like this for the photo to be taken?
You may even like to generalise the problem to twelve people or to any specified even number.
Now try the problems Walkabout and Counting Binary Ops
Getting Started
Student Solutions
Dorothy of Madras College, St Andrews and Maren & Corinna of Camden School for Girls used the same notation denoting the people by the numbers 1, 2, 3,...? in ascending order of height. As each person at the back must be taller than the person directly in front of them and, along the rows, the heights must increase from left to right the 1 must be in front on the left and the tallest must be at the back on the right. Dorothy gave the results for 2, 4, 6, and 8 people in the following table.
| Number of people | Number of arrangements | Diagrams | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 1 |
|
||||||||||||||
| 4 | 2 |
|
||||||||||||||
| 6 | 5 |
|
||||||||||||||
| 8 | 14 |
|
Many people think that because the sequence 1, 2, 5, 14 ? goes up in powers of 3 (with differences 1, 3 and 9) the next difference will be 3 cubed to give the next number 14 + 27 = 41. Maths is full of patterns but, when you think you spot a pattern you have to prove it always works. If you count the arrangements for 10 people the answer is 42 and not 41. Can you find them all?
The solution for 10 people was sent in by Andrei from Tudor Vianu National College, Bucharest, Romania.
For 10 people I shall describe the arrangements briefly without writing all the numbers. I see that 1 and 10 are fixed.
- I start with 1 2 3 4 in the first line, and there are 5 possibilities for the last position: 5, 6, 7, 8 and 9.
- If 4 goes on the second line, than in the first there will be 1 2 3 5, and there are 4 possibilities for the last place: 6, 7, 8 and 9.
- If 5 goes besides 4 on the second line, than in the first there will be 1 2 3 6 and there are 3 possibilities for the last place: 7, 8 and 9.
- If 6 goes also on the second, there will be 1 2 3 7 8 or 1 2 3 7 9 in the first. So, for the sequence 1 2 3 in the first line, there are (5 + 4 + 3 + 2) possibilities.
I change 3 on the second line.
- If on the first line there is the sequence 1 2 4 5, there are 4 possibilities for the last place: 6, 7, 8 and 9.
- If 4 goes on the second line, than on the first there will be 1 2 5 6 followed by 7, 8 or 9 '?? 3 possibilities
- If 5 goes too on the second line, than 1 2 6 7 will be followed by 8 or 9 '?? 2 possibilities.
So, for the group 3 x x x 10 1 2 x x x , there are (4 + 3 + 2) possibilities. Studying all the possibilities further, I arrived at the conclusion that for 10 people, I find the following number of possibilities:
(5 + 4 + 3 + 2) + (4 + 3 + 2) + (3 + 2) +(4 + 3 + 2) + (3 + 2) = 14 +9 +5 + 9 + 5 = 42
Summarising, up to now I found the following table:
| No. of people | 2 | 4 | 6 | 8 | 10 |
| No of possibilities | 1 | 2 | 5 | 14 | 42 |
For 12 people, I see that there are 132 possibilities, which could be counted as:
(6 + 5 + 4 + 3 + 2) + (5 + 4 + 3 + 2) + (4 + 3 + 2) + ( 3 + 2)
+ (5 + 4 + 3 + 2) + (4 + 3 + 2) + ( 3 + 2)
+ (4 + 3 + 2) + ( 3 + 2)
+ (5 + 4 + 3 + 2) + (4 + 3 + 2) + ( 3 + 2)
+ (4 + 3 + 2) + ( 3 + 2) = 48 + 28 +14 + 28 + 14 = 132
At this point, I had the chance to look back on the NRICH site, and to discover the link to the problem Counting Binary Ops. I recognized the numbers I found (1, 2, 5, 14, 42, 132) as being the first terms of the sequence of Catalan numbers. Looking more for Catalan numbers, e.g. at http://mathworld.wolfram.com/CatalanNumber.html I found both the recurrence relation and the explicit formula.
If $C_n$ is the $n$-th Catalan number ($n$ being for our problem the number of places in one line, i.e. half the number of people), $$C_n ={1\over n+1}{2n\choose n}$$ and $${C_{n+1}\over C_n} = {2(2n+1)\over n+2}$$ or, if $C_0 = 1$ (there is exactly one way of arranging zero people: don't put them in any way), then: $$\begin{eqnarray} C_1&=&C_0C_0= 1 \\ C_2&=&C_1C_0 + C_0C_1 = 2 \\ C_3&=&C_2C_0 + C_1C_1 + C_0C_2 = 5 \\ C_4&=&C_3C_0 + C_2C_1 + C_1C_2 + C_0C_3 = 14 \\ C_5&=&C_4C_0 + C_3C_1 + C_2C_2 + C_1C_3 + C_0C_4 = 42 ... \\ C_n &=& C_{n-1}C_0 + C_{n-2}C_1 + ...C_1C_{n-2}+ C_0C_{n-1} \end{eqnarray}$$Teachers' Resources
One Basket or Group Photo
Image
|
A school photographer is taking a photograph of the two basketball teams. She has to arrange ten people, all of different heights, in two rows of five, one behind the other. Each person at the back must be taller than the person directly in front of them. Along the rows the heights must increase from left to right.
In how many ways can two, four or six people to be arranged in this way for a photo, or eight people? In how many ways can the ten team members be arranged like this for the photo to be taken?
You may even like to generalise the problem to twelve people or to any specified even number.
Now try the problems Walkabout and Counting Binary Ops
Libby Jared chose this problem for the NRICH Tenth Anniversary celebration and this is what she had to say about it: "I chose this problem for many more reasons than I could write in one sentence on the summary page.
Firstly I saw it being made up by Toni (Beardon) as she sat at a computer at Szechenyi Istvan Primary School, in Tiszaujvaros, a town in Hungary. We were there (in May 2000) as part of EuroMaths, a small EU project which linked schools in Denmark, England and Hungary. The schools used nine NRICH problems over three years, during which time the teachers involved discussed with one another their thoughts and different practices in using such problems in their classrooms. Several friendships were forged between us.
But pleasant memories would be insufficient if Group Photo was not the good mathematics problem that it undoubtedly is. To begin with, it can it be simplified by reducing the number of people to be in the photograph. This makes it accessible to primary school pupils and I know that some classes have had great fun in working it out using real people. Also, I like the investigative nature that the problem presents and it does eventually (I believe) require a systematic approach.
Our Hungarian colleagues provided two different tree diagrams to show the possibilities, whilst others in England worked with numbers set out in two lines. However, some people jump to conclusions a little too early, for just when it looks as if a pattern of results is emerging, something happens to contradict the spotted, but wrongly predicted, result.
I have been reliably informed that Professor Alan Beardon has used it with his post graduate students in his Problem Solving course in South Africa. I too present the problem each year to my post graduate trainee mathematics teachers who work enthusiastically to solve it - well at least to their satisfaction. Hopefully many of them will take Group Photo into their classrooms and introduce another generation to the problem.
If you would like to read how one primary school worked on the problem then you will find an article in the Mathematics Teaching number 188 (published by the Association of Teachers of Mathematics).The title of the article - for a reason which you may need to investigate for yourselves - is 'The answer is 42'."
More Notes:
Why do this problem?
This 'people' problem gets small groups physically involved in learning by action (kinaesthetic learning) and it is very suitable for upper primary as well as for older students.Possible approach
Get four people of different heights to arrange themselves for the photo. How many ways can they do it?What about two people? Then the class can try the problem in groups of six people. There will be a lot of discussion about the ways of recording the different arrangements and checking that they have found them all.
Having found the number of arrangements for 2, 4, 6 and 8 people there is an 'obvious' pattern that suggests the number of arrangments for 10 people, but then counting the possibilities leads to a surprise.
Key questions
Possible extension
This problem only asks you to find the number of arrangements for taking a photo of ten people and that is usually where it stops with younger students.There is an obvious generalisation to taking a photo of 12, 14, .... and then of any even number of people. To identify and find a formula for the sequence that arises is challenging for students in the last couple of years of schooling.