Mentor: Here is one more game to play and study. Players roll 3 four-sided dice. Player 1 wins if the
sum of the dice numbers is 3, 4, 5, 6 or 12; Player 2 wins if the sum is 7, 8, 9, 10 or 11. Is
the game fair?
Student: Now I know that there are many possible ways to get the same sum. We used tables to count the
possibilities for two dice. We can't use the table anymore, because it only has two... what do
you call them?
Mentor: Dimensions. We can make a table with three dimensions or more, but it will be hard to use by
hand. By the way, computers can deal with tables of hundreds of dimensions. What else can we
do? Let me write the first quarter of the list of all the combinations, the part where the
first die shows 1. It will be a boring task....
Student: Could we somehow get rid of all the repetitions? I mean, can we write one big fat "1" instead
of sixteen little 1's?
Mentor: Why not? If we do that, we will obtain a structure called
a tree. Can you guess why even before we make the pictures? Here is the picture that shows how this
part of the tree for our problem is constructed. There will be 3 more parts for the rest of
the possible numbers on the first die. You can build them yourself.
Mentor: Do you see why it is called a tree?
Student: Because it looks like a tree lying on its side. We can add some "leaves" and write stuff on
them. I will write the sum of the dice numbers:
Mentor: Do you see how the tree can help us count outcomes?
Student: Well, it is useful for counting the total number of outcomes. There are four "trunks" (for
the possible numbers on the first die), and each has four "branches" (for the possible numbers
on the second die), and each has four "twigs" (for the possible numbers on the third die). An
outcome is formed as we go from a trunk to a brunch to a twig. There are as many outcomes as
there are twigs: 4*4*4=64. Wow! It sounds like an old puzzle!
Mentor: Now look at all the "leaves" and find out if the game is fair. What is the probability of
each player winning?
Student: Player 1 only has a winning probability of 21/64, whereas Player 2 has a winning probability
of 43/64. This game is not fair.
Mentor: How many possible outcomes are there if you have three coins? (2*2*2=8) If you have a coin
and two six-sided dice? (2*6*6=72) How many outcomes are there if you have four
coins?(2*2*2*2=16) Five six-sided dice(6*6*6*6*6)? By the way, if I do not feel like writing
the numbers so many times, can I write the same thing much shorter: 6*6*6*6*6=6
5 It reads: "Six to the power of five." Computer folks type it as 6^5, because it is faster
than switching to the superscript.
Student: I do not want to actually draw all these huge trees!
Mentor: A tree for the four coin problem would not be all that bad. Can you draw it? Observe that at
each time the tree "branches," there are exactly two branches (for heads and tails on the next
coin). Trees of that sort are called
binary trees. They are very common in computational science, and even in nature:
Mathematician on a binary tree. Photograph by Dmitri Droujkov.
Mentor: Here is a riddle for you. If we have a full binary tree (no branches are cut off) that has 8
smallest branches, how many "levels of branching in two" are there? In other words, if we were
playing with coins, how many coins would you need to produce 8 outcomes?
Student: Let us see. The last branching happens when 4 branches became 8:
The branching before that happens when 2 branches become 4:
and the very first one is when a single branch becomes 2:
So we have three levels of branching.
Mentor: When you find out the number of branchings from the number of the last branches, it is called
a computing logarithm, and the number of branchings is called a
logarithm. There is a special sign for it:
Student: In the original example with 3 four-sided dice, there were 64 "smallest branches," but each
branching was splitting in four. That means:
Mentor: Exactly, and
4^3=64. By the way, where else have you seen trees like that?
Student: In NCAA tournaments!
Mentor: Now you can easily translate the following question into mathematical language: "If there are
64 teams in a tournament, how many rounds do they need to play to determine a winner?"
Student 1: The question is so much shorter in math language!