Copyright © University of Cambridge. All rights reserved.

This
problem provides an interesting backdrop for computations in
combinatorics and conditional probability. The results are very
counter-intuitive to most people: although each sequence of three
H/T combinations is equally likely, for any given sequence you can
always choose another sequence which is likely to come first out
of the Turing machine.

The problem will provide stimulation for wider background
reading for students with an interest in probability and
uncertainty.

You can introduce the concept of the machine through a game
with the interactivity: Students pair up and each choose a sequence
of three heads or tails. Start the machine (with no choices in the
interactivity, so that it doesn't stop) and then keep going until
one of each pair has lost. Then make pairs out of the winners and
repeat until a single champion is left.

Now pose the question for the first part of the problem, in
which there are 6 units of paper left in the machine: "Who do we
think is more likely to win?". Regardless of the answers given, we
need to then ask the question "How do you know?". The only sound
answer to this is through direct computation.

Drawing a tree is a sensible way forward, as is enumerating
all of the $2^6$ possibilities and seeing who will be the winner in
each individual case. However, students should be encouraged to
draw out trees cleverly 'one letter at a time', as when either
Turing or I win there is no point continuing that branch of the
tree. Note that the question does not directly ask for the
probability of a winner, merely which is more likely to win -
students might be able to use this idea cleverly to save time on
the computation. You can ask students who finish this quickly to
work out the probabilities of a win or to consider the extension to
8 addition units of paper.

The second part of the problem flows naturally from the first
part: however, here students will have to guess a string and
compute the probabilities. Clear recording and teamwork might help
here.

For the extension task, a tree diagram approach is a
likely starting point but students will soon realise that it
is impossible to draw out the 'complete tree' as there is the
possibility that the game will go on arbitrarily long without a
winner. This is a good way to introduce ideas of recursive thinking
in conditional probability and should be stimulating thinking for
the most able students.

How many possible strips of 6 letters might emerge from
the machine?

If at any time HH has just emerged from the machine, why is
Turing GUARANTEED not to lose?

How might a tree diagram help?

Is there a sensible way to list all of the possibilities of
H/T combinations?

There are two possible extensions:

1) Construct a table with all of the probabilities of a
victory for me for all choices for me and Turing, given that there
are 8 units in the machine to begin with.

2) There is an interesting article on this and other related
concepts at http://plus.maths.org/issue55/features/nishiyama/.
As an extension, very interested students could work through the
calculations and verify some of the probabilities.

You could simplify matters by suggesting that the machine
initially only holds 4 letters -- this will make drawing the
complete tree diagram much simpler, and the task is then to
determine which branch leads to a win for either Turing or
myself.

You can also make use of this spreadsheet to work out
the wins and losses.