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

N000ughty Thoughts

Factorial one hundred (written 100!) has 24 noughts when written in full and that 1000! has 249 noughts? Convince yourself that the above is true. Perhaps your methodology will help you find the number of noughts in 10 000! and 100 000! or even 1 000 000!

Walkabout

Stage: 4 Challenge Level: Challenge Level:2 Challenge Level:2

Why do this problem

This problem presents an investigation which does eventually require a systematic approach. Although the generalisation is difficult for Stage 4 some of the context's structure is discernible and describable, and comparable to other similar situations. Do the problem in conjunction with Group Photo and ask learners to describe what is the same about the two situations that could explain them resulting in the same sequence of Catalan numbers.An apparent generalisation related to cubes of numbers breaks down and so the problem offers an opportunity to discuss a danger of applying inductive reasoning.

Possible approach

One approach is to do this in conjunction with Group Photo , either following from one to the other, or dividing the class so that groups work on different problems, or why not use two classes working on the different problems. The aim would be to bring the two sets of findings together to discuss why two apparently quite different situations result in the same mathematics.

Focusing on Walkabout :
Allow plenty of time to 'play' with the problem, making sense of what is being counted and how it might be represented.
Encourage ideas that involve systematic approaches, and share them so that all learners have access to a way into the problem.
Use results from separate groups to check working.

Key Questions

  • Can you describe what is the same about the two problems that might explain the similar mathematical structure?
  • What is different about and what is similar to other examples, such as One Step Two Step and Room Doubling that result in a Fibonacci sequence?

Possible support

Group photo can be done with real people and you can start with small numbers. Spend plenty of time trying out, and considering the efficiency of, possible recording methods.

Possible extension

Can students make connections between the structures of the two problems that may in part explain the mathematical connections?


Notes


$ 1$, $ 1$, $ 2$, $ 5$, $ 14$, $ 42$, $ 132$, $ 429$, $ 1430$, $ 4862$ ,...


The Catalan numbers describe things such as:
  • the number of ways a polygon with n+2 sides can be cut into n triangles
  • the number of ways to use n rectangles to tile a stairstep shape (1, 2, ..., n-1, n)
  • the number of ways in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time
  • the number of planar binary trees with n+1 leaves
  • the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal
They can be described by the formula $$\frac{ ^{2n}C_{n} }{(n + 1)}$$

The Catalan numbers are also generated by the recurrence relation:

$ C_0=1, \qquad C_n=\sum_{i=0}^{n-1} C_i C_{n-1-i}.$

For example, $ C_3=1\cdot 2+ 1\cdot 1+2\cdot 1=5$, $ C_4 = 1\cdot 5 + 1\cdot 2 + 2\cdot 1 + 5\cdot 1 = 14$, etc.