Stage: 5 Challenge Level: 
A miraculous machine tosses a coin an infinite number of times in one second and the result is recorded as an infinite sequence of zeros and ones (one for a head and zero for a tail). Suppose the machine is reset and the tosses of the coin for the next second are recorded in the same way. Further suppose that the machine goes on doing this for ever. The record of the results is an infinite set of infinite binary sequences.
Show that there is some sequence of tosses that is never recorded by the machine.
Show that the infinite set of finite (or terminating) binary sequences can be written as an ordered list whereas the infinite set of all infinite binary sequences cannot.
Number bases. Counting. Manipulating algebraic expressions/formulae. Inequality/inequalities. Patterned numbers. Number theory. Stage 5 - Reviewed 2012. Generalising. Sets. Mathematical reasoning & proof.
Published March 2005,April 2005.
Copyright © 2007. University of Cambridge. All rights reserved.
NRICH is part of the family of activities in the Millennium Mathematics Project, which also includes the Plus and Motivate sites.
email: nrich@damtp.cam.ac.uk