You may also like

problem icon

Doodles

A 'doodle' is a closed intersecting curve drawn without taking pencil from paper. Only two lines cross at each intersection or vertex (never 3), that is the vertex points must be 'double points' not 'triple points'. Number the vertex points in any order. Starting at any point on the doodle, trace it until you get back to where you started. Write down the numbers of the vertices as you pass through them. So you have a [not necessarily unique] list of numbers for each doodle. Prove that 1)each vertex number in a list occurs twice. [easy!] 2)between each pair of vertex numbers in a list there are an even number of other numbers [hard!]

problem icon

Russian Cubes

How many different cubes can be painted with three blue faces and three red faces? A boy (using blue) and a girl (using red) paint the faces of a cube in turn so that the six faces are painted in order 'blue then red then blue then red then blue then red'. Having finished one cube, they begin to paint the next one. Prove that the girl can choose the faces she paints so as to make the second cube the same as the first.

problem icon

Snooker

A player has probability 0.4 of winning a single game. What is his probability of winning a 'best of 15 games' tournament?

One Basket or Group Photo

Stage: 2, 3, 4 and 5 Challenge Level: Challenge Level:3 Challenge Level:3 Challenge Level:3

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
2
1
4 2
2 4
1 3
3 4
1 2
6 5
2 4 6
1 3 5
3 4 6
1 2 5
2 5 6
1 3 4
3 5 6
1 2 4
4 5 6
1 2 3
8 14
2 4 6 8
1 3 5 7
3 4 6 8
1 2 5 7
2 5 6 8
1 3 4 7
3 5 6 8
1 2 4 7
4 5 6 8
1 2 3 7
2 4 7 8
1 3 5 6
3 4 7 8
1 2 5 6
2 5 7 8
1 3 4 6
3 5 7 8
1 2 4 6
4 5 7 8
1 2 3 6
2 6 7 8
1 3 4 5
3 6 7 8
1 2 4 5
4 6 7 8
1 2 3 5
5 6 7 8
1 2 3 4

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}$$
I have found that Richard P. Stanley has shown that the number of distinct standard Young tableaux of shape (n; n) form the sequence of Catalan Numbers. But the arrangements in the photo are Young tableaux with reversed lines.

To complete the solution, it is necessary either to show the correspondence between this problem and a classical problem involving Catalan Numbers (e.g. Euler's polygon division problem), or to find the recursive (or explicit) formula for the number of possibilities of arranging people in the photo.