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!

Counting Binary Ops

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

Another superb solution from Andrei, School: 205, Bucharest, Romania.

For four terms, I found the following possible combinations:
(a (b (c d)))
(a (b (c d)))
(a ((b c) d))
((a b) (c d))
((a (b c))d)
and (((a b) c) d) i.e. five.

For five terms, there are 14 combinations:
(a(b(c(de)))) (a(b((cd)e)))
(a (b (c (d e)))) (a (b ((c d) e)))
(a ((b c) (d e))) (a ((b (c d)) e))
(a (((b c) d) e)) ((a b) (c (d e)))
((a b) ((c d) e)) ((a (b c)) (d e))
((a (b (c d))) e) ((a ((b c) d)) e)
((a b) c) (d e)) (((a b) (c d)) e)
(((a (b c)) d) e) ((((a b) c) d) e)

For six terms, there are 42 combinations.

I found that these are Catalan numbers, that appear from a great variety of mathematical problems, as the number of ways a regular polygon with n sides could be divided into (n-2) triangles, the number of paths of length 2n through an n by n grid that do not rise above the main diagonal, and, of course the number of ways numbers in a sequence could be grouped using binary operations, as is the case of this problem.

The first terms of the sequence of Catalan numbers are:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

They could be computed using the formula: $$Cat_n={^{2n}C_n \over (n+1)}= {(2n)!\over (n+1)!n!}$$

The correspondence with the problem is that n here must be the number of binary operations, i.e. the number of terms minus one.