You may also like

problem icon

Links and Knots

Some puzzles requiring no knowledge of knot theory, just a careful inspection of the patterns. A glimpse of the classification of knots, prime knots, crossing numbers and knot arithmetic.

problem icon

Ruler

The interval 0 - 1 is marked into halves, quarters, eighths ... etc. Vertical lines are drawn at these points, heights depending on positions. What happens as this process goes on indefinitely?

problem icon

Voting Paradox

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?

Binary Sequences

Stage: 5 Challenge Level: Challenge Level:3 Challenge Level:3 Challenge Level:3

Bill from Reading School sent in this solution and other good solutions came in from Jax from Pate's School and Curt from Reigate College.

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 sequence becomes:

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 included.

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.