Some relationships are transitive, such as `if A>B and B>C
then it follows that A>C', but some are not. In a voting system,
if A beats B and B beats C should we expect A to beat C?
Stage: 5 Challenge Level:
Bill from Reading School sent in this solution and other good
solutions came in from Jax from Pate's School and Curt from Reigate
This problem can easily be solved through use of Georg Cantor's
method for proving that the set of irrational numbers is
uncountable. Suppose we tabulate the results of the coin-flipping
so that one set of infinite tosses is one row. We might have
something like this:
1) 0 1 0 1 1 1 0 0 0 0 1...
2) 10 0 1 1 0 1 0 1 0 1...
3) 1 1 1 0 0 1 0 1 0 0 0...
and so on down and across the infinite list.
Now, we take a diagonal line, starting from the top left and going
right and down. The first three digits in this sequence would be 0
0 1. Suppose that this diagonal line gives us a sequence A:
0 0 1 0 1 1 0 0 0 1 1...
Take the complements (remember that we are working in binary). The
1 1 0 1 0 0 1 1 1 0 0...
This sequence B cannot appear anywhere in the table of coin tosses.
Why is this true?
Try matching it up against the first row. Since the first digit of
B is the first digit of line 1, but swapped, the sequence B clearly
does not match the first row.
Try line 2: the second digit of B is again, taken from line 2 but
swapped. Thus the sequence B does not correspond to line 2.
To generalise, the sequence B could almost correspond to some line
n, but it would be incorrect at the nth place.
Thus the sequence B we have constructed cannot appear in the table.
This shows that the infinite set of all infinite sequences cannot
be written in an ordered list because if we try to make an ordered
list as above another sequence can be found which has not been
In contrast the infinite set of finite or terminating binary
sequences can form an ordered list by defining an order in the
following way. Take each binary sequence and treat it as the binary
expansion of some integer. Thus the sequence 0 1 1 0 1 0 1
corresponds to 53 (since the initial 0 does not contribute). This
mapping associates a non-negative integer with each member of the
(infinite) set and therefore arranging the integers in order
defines an ordered list.
The NRICH Project aims to enrich the mathematical experiences of all learners. To support this aim, members of the
NRICH team work in a wide range of capacities, including providing professional development for teachers wishing to
embed rich mathematical tasks into everyday classroom practice. More information on many of our other activities
can be found here.