I was looking at some practice tests and I came upon this tricky question. I'm not sure I would have got it on an exam! Consider the set, S, of all infinite sequences whose entries are either 1 or 2. However, if the nth term is 2 then the n+1th term is 1. I.e every 2 is followed by a one. Theorem: S is uncountable That it is infinite is simple to show. Consider the set of all sequences described as above except with only a single 2. Then this subset is equivalent to the natural numbers. Consider the subset of S where every even term is a one, then list these. Now to show there is a sequence in the subset that is not listed create a new one by switching the odd terms diagonally. That is 2,1,2,1,2,1...(1st term is 2) 1,1,1,1,1,1...(3rd term is 1) 1,1,2,1,1,1...(5th term is 1) so the new sequence begins with 1,1,2,1,2,1.... Another way to see how this works is to consider 2,1 = 1 and 1,1 =0, then each of these sequences can be written as sequences of zeros and ones which we know is uncountable by using a similar method of proof. Since this subset of S is uncountable, and S is infinite, S must be uncountable.