\chapter{Logicland}
\section{Probability}
Alice experienced a rather peculiar sensation as she fell
through the mirror. She felt as if she were somehow turning inside out and
then everything was backwards. What she had previously thought of as her
left hand was now her right hand. The Yellow Pig now had nine eyelashes on
the eye that had previously had only eight.
While Alice and the Pig were trying to adjust, two small men introduced
themselves. Alice noticed
that when they shook hands, one used his left hand and the other his right.
``Welcome to Logicland,'' they said in unison. ``The room of games is just
ahead. They pointed Alice and the Pig in the right direction and quickly
disappeared.
``How odd,'' said Alice to the Pig. ``I wonder what that is.''
``I don't know,'' said the Pig. ``We'll have to wait and see. I've never
been here before. I must say, I don't make a habit of leaping through
mirrors as you do.''
``Well,'' said Alice, ``I figured I had come this far.''
``True,'' said the Pig. ``I haven't taught you any probability yet, have
I?''
Alice shook her head. ``No, you haven't.''
``Well then I must,'' said the Pig, as they began walking in the direction
of the game room.
``Probability is the study of percentages, of odds, of chances. How likely
is it that a certain event or series of events will occur? Gambling is
about probability. When you roll a normal pair of dice, each die will have
a number of dots from one to six. The pair will add up to a number
from two to twelve. Dice are one way of generating somewhat random numbers.
An even simpler way is to use coins. A coin can land either heads up or
tails up. That's two ways, and ideally both ways are equally likely to
occur. That means the odds of getting heads when flipping a coin is
$\frac{1}{2}$ or 50 percent.''
``I have some coins with me,'' said Alice. She reached into her pocket and
produced six coins for the Pig.
``Good,'' said the Pig. ``Now, here's my first question: what are the odds of
getting two heads if I toss a coin twice?''
Alice had to admit she had no idea.
The Pig explained, ``I'm asking about two separate events: the first coin
toss and the second coin toss. And I'm asking what are the odds that both
things happen. To find the probability that two independent events occur,
you multiply both of their individual probabilities together. Does that
make sense?''
``I think so,'' said Alice. ``The odds that both things happen is smaller than
the odds of either happening.''
``Right,'' agreed the Pig. ``The odds of getting two heads is
$\frac{1}{2} \cdot \frac{1}{2}$ or $\frac{1}{4}$.''
``Sure,'' she replied. There was a room directly in front of them.
``This must be the way to the room of games.''
``Before we enter,'' the Pig said, ``let's talk some more about probability.''
This was
agreeable to Alice, so he continued. ``What are the odds that if I toss the
coin three times, all three tosses will be heads?''
``I think I can figure that out,'' said Alice, thinking aloud. ``The odds of
the first coin being heads is $\frac{1}{2}$. The odds of the second coin being
heads is $\frac{1}{2}$. The odds of the third coin being heads is also
$\frac{1}{2}$. So the odds of
all of them being heads is just those odds multiplied together.
$\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$.''
``Exactly,'' said the Pig. ``And $\frac{1}{8}$ is $(\frac{1}{2})^{3}$.
The 3 is because there are three coins. The odds of getting seventeen heads
out of seventeen tosses is $(\frac{1}{2})^{17}$.''
``I see,'' said Alice. ``So now I know how do to the odds that all the coins
are heads. What if I want to know the odds that they aren't all heads?''
``That's easy,'' said the Pig. ``Probability ranges on a scale from 0 to 1. If
something has probability 0, in an ideal world, it will never happen. If
something has probability 1, it is certain to happen. The probability of
getting either all heads or not all heads is 1.'' He wrote:
$$\Pr(H)+\Pr(T)=1$$
``You will always either get all heads or not get all heads. To find the
odds that all the coins will not be heads, simply find the odds that they
are all heads, and subtract that from 1.''
``Oh,'' Alice said, ``so the odds that with two coins they aren't all heads is
$1-\frac{1}{4}$ or $\frac{3}{4}$.'' The Pig nodded. ``What are the odds that
with two coin tosses, exactly one of the coins is heads and the other is
tails?'' she asked.
``I'm glad you asked,'' said the Pig. ``Let's look at what all of the possible
outcomes are. That is, all of the combinations that we can obtain
from tossing the coins.''
``We can have two heads,'' said Alice, ``or two tails, or one of each.''
``Yes,'' said the Pig, ``but you are missing something important. On the first
toss we have either heads or tails.'' He wrote H and T at the top of a
piece of paper in his notebook, leaving much room between the two letters.
``Then, on our second toss, we could
have either H or T. From each of these first two scenarios, there are
two other scenarios that can occur.''
\centerline{\epsfbox{images/5-htprob.ps}}
``So there are two times two or four possible outcomes,'' said Alice. ``That
must be where our 4 in $\frac{1}{4}$ came from.''
``It is,'' said the Pig. He drew two lines coming out from the `H' and two
more coming out from the `T'. Below these lines, he wrote `HH', `HT', `TH',
and `TT'. ``I've listed all of the outcomes,'' he said, ``and they all occur
with equal probability. Each of these occurs $\frac{1}{4}$ of the time.''
After a moment, Alice was convinced that this was true. She studied the
Pig's diagram. ``There are two times when heads occurs exactly
once,'' she said. ``One time is heads followed by tails and the other is
tails first and then heads.''
``In two out of our four cases, we get one head and one tail,'' reiterated
the Pig. ``That's a key fact of probability. The odds of something
occurring are the odds of any single event occurring times the number of
combinations that satisfy the specific conditions. Or the number of ways
something can happen divided by the number of different ways things can
happen. In this case there are two ways we can have one head and one tail
divided by four possible outcomes of our two coin toss. That's two divided
by four or $\frac{2}{4}$, which we can reduce to $\frac{1}{2}$. That
means there's a fifty percent chance of getting a head and a tail.''
``That seems pretty simple,'' said Alice.
``Well, I guess it is,'' said the Pig. ``But that's because we were dealing
with such small numbers. I can easily write out all of the combinations of
two coin tosses. But what about seventeen coin tosses? That's an awful lot
of different sequences of heads and tails that can occur. Or even five
coins. With a five coin toss, what are the odds that two coins will be
heads and three will be tails?''
``Well, we just write out all of the combinations,'' said Alice. She took the
notebook from the Pig and began to write a long series of H's and T's. After
a dozen or so she stopped. ``There are a lot of possible outcomes,'' she
said.
``How many?'' asked the Pig.
``There are five coin tosses and two different outcomes for each coin toss.
That's two times two times two times two times two.''
``That's thirty two,'' supplied the Pig. ``You were almost halfway there.''
``Yes,'' said Alice, ``but then I would have to count up all the ones with two
heads and three tails. Surely there must be an easier way to do that.''
``There is,'' said the Pig. ``It involves understanding combinations and
permutations, which are two very important concepts in probability. And
they both depend on factorials.''
``What are factorials?'' asked Alice.
``Remember before when we looked at triangular numbers? Numbers like
$1+2+3+4+5+6+7+8$? Well, factorials are like that. Only instead of adding,
we multiply. For example, 4 factorial is $4 \cdot 3 \cdot 2 \cdot 1$. And
5 factorial is
$5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$. That's the product of the numbers
from 1 to 5. It only makes sense to talk about factorials of natural
numbers. Mathematicians use factorials so often that they have a special
symbol. It's an exclamation point because factorials are that exciting.''
``So 4 factorial is 24,'' said Alice after working out the multiplication.
``Right,'' said the Pig. ``And to get $5!$ you could multiply out all of the
numbers again. Or you could just multiply $4!$ by 5.''
``Neat,'' said Alice. ``So 5 factorial is 24 times 5.'' She wrote this out in
the Pig's notebook. ``That's 120. And 6 factorial is 120 times 6. And 7 factorial
is that times 7. And 8 factorial is \ldots .''
``I think you get the idea,'' the Pig interrupted. ``{\it Permutations} are the
number of ways something can be arranged. Like, if you have five people who
go to the movies. And you want to know how many different seating
arrangements there are. That's $5!$.''
``How?'' asked Alice, looking puzzled.
``Think of it this way,'' explained the Pig. ``First they decide who should
sit in the first seat. There are five choices for people who can sit in the
first seat. Whichever one of them sits there, the remaining four go through
the same process again for the next seat. That's four choices. Then there
are three left to fight over the next seat. Then two, and then finally the
remaining one sits down. Remember what we said about multiplying
probabilities together?'' Alice nodded. ``That still applies only in a
slightly different way. Now we multiply together the number of ways people
can sit in each seat, because the odds of them sitting in one particular
arrangement is simply one divided by however many seating arrangements
there are. So there are 5 times 4 times 3 times 2 times 1 or $5!$ different
ways they could be seated. That's a problem about permutations. In the
coin toss problem we didn't care about the order of heads and tails. That
was a problem of {\it combinations}.''
``So if we want to know about one specific order of the coins, that
involves permutations?'' Alice asked.
``Right,'' said the Pig. ``But `How many pairings of two people are possible out of
the five people at the movies?' is a problem of combinations, not
permutations.''
``That's sort of like our handshakes problem, isn't it? Each handshake
represents a pair of people,'' said Alice.
``Yes,'' said the Pig. ``You'll find a lot of math is like that. Two
seemingly unrelated problems may turn out to have a lot in common.
The results of one branch of mathematics may lead to conclusions in
another branch. Just look at some of the math you've learned so far:
triangular numbers, Fibonacci numbers, and now factorials. They may
seem like different things, but they are all related. And it turns
out that permutations are very closely related to combinations. In
fact, there's a magical formula for calculating combinations. It might
not make much sense, but I assure you it works. And it's full of
factorials. Want me to tell you the formula?''
``Sure,'' said Alice.
``Okay,'' the Pig said, ``it's $\frac{n!}{r!(n-r)!}$. That's the number of
ways of choosing a subset of $r$ things from a set of $n$. The formula
comes from the triangle you were studying earlier with Isabel.''
``I don't think I understand,'' said Alice, frustrated because she had
been following the Pig until his last formula.
``That's okay,'' said the Pig. ``You'll understand it some day. Next time
you see Isabel, you should ask her to explain it.''
``Okay,'' said Alice, remaining somewhat unconvinced that the formula would
work. She decided to just accept it for the time being though this
made her slightly uneasy. ``I guess it's easier than writing out all of the
combinations.''
``It is,'' the Pig said. ``I can now rephrase my question about heads and
tails. A mathematician would say `What is 5 choose 2?' How many ways are
there for the 2 heads to be arranged from 5 coin tosses?''
``We use the formula,'' said Alice. ``And $n$ is the bigger number right? That's
5. And $r$ is the 2 from the 2 heads. So that's $\frac{5!}{2!(5-2)!}$ which
is the same as $\frac{5!}{2!3!}$.''
``You have really gotten the hang of this combinations stuff,'' said the Pig.
``That's absolutely correct. And that number just so happens to be 10.''
Alice checked the arithmetic for herself and agreed. ``So,'' continued the
Pig, ``there are 10 ways to get 2 heads and 3 tails. That's out of 32
possible outcomes from the coin tosses. Now we can calculate our
probability.''
``The probability that something happens is the number of ways it can happen
divided by the number of total possible outcomes,'' recalled Alice.
``Right,'' said the Pig. ``Because the odds of getting
any specific ordering of coins is the same as the odds of getting any other
ordering of coins. It's more precise to say that the probability of a
specified outcome is a sum of the probabilities that it will happen in each
particular way.''
``Okay,'' said Alice. ``So in this case it's 10 ways out of 32 possibilities.
That's $\frac{10}{32}$.''
``Yup,'' said the Pig. ``We can reduce that fraction to $\frac{5}{16}$.
There's a 5 in 16 chance of getting 2 heads and 3 tails from 5 coin
tosses.
There's also a 5 in 16 chance of getting 3 heads and 2 tails from 5 coin
tosses. Those are the most likely things to happen. What are the odds of
getting 0 heads or 1 head?''
``Getting 0 heads means all tails. That means each coin has to be tails, and
there are five coins. It's not like with 2 heads and 3 tails where there
were different arrangements. This time there is only 1 of the 32
arrangements so $\frac{1}{32}$. I think is easier to write out
the possibilities than to use the formula. The only ways to get 1 head are
`HTTTT', `THTTT', `TTHTT', `TTTHT', and `TTTTH'. That's 5 ways or a
probability of $\frac{5}{32}$,'' finished Alice.
``Let's see if it adds up,'' said the Pig. ``In the five coin toss, the only
outcomes are 0 heads, 1 head, 2 heads, 3 heads, 4 heads, and 5 heads. And
the probabilities are symmetrical. The odds of getting 0 heads and hence 5
tails are the same as the odds of getting 5 heads and hence 0 tails. So we
know the probability of each outcome and we just have to make sure that the
whole thing adds up to one. Look at the distribution of probabilities. It
is so much more likely to get about the same number of heads and
tails than it is to get either all heads or all tails. In fact, we would
expect to get about the same number of heads and tails.'' He wrote:
\vbox{
\ssp
\begin{center}
\begin{tabbing}
$\Pr(0H)$ \= + \= $\Pr(1H)$ \= + \= $\Pr(2H)$ \= + \=
$\Pr(3H)$ \= + \= $\Pr(4H)$ \=+ \= $\Pr(5H)$ \= = \\
1/32 \> + \> 5/32 \> + \> 10/32 \> + \> 10/32 \> + \> 5/32 \> + \> 1/32 \> = 1
\end{tabbing}
\end{center}
\dsp
}
``That's what we wanted,'' said the Pig. ``Here's a question that is sort of
about probability that often gets people confused. Suppose I have tossed a
perfectly fair coin 16 times in a row and it has been heads every time.
What is the probability that the 17th toss will come up heads?''
Alice thought about the Pig's question. It seemed really unlikely that 16
coin tosses in a row would be all heads. Why, the odds of that were
$(\frac{1}{2})^{16}$ which is an incredibly small number. The odds of tossing
a 17th head seemed even less likely. ``I don't know,'' said Alice,
``I have a friend who always gets heads when he tosses coins, but it
does seem pretty unlikely.''
``That's where most people, especially gamblers, get tripped up,''
said the Pig. ``Getting
the 17th head isn't a big deal. It's the fact that there were 16 heads
before that. But that has already happened, so we don't have to concern
ourselves with that. Each coin toss is a completely independent event.
Surely when you toss a coin, it doesn't know if 16 heads were tossed before
it or not. So that can't make a difference. The odds of the 17th coin
being heads is precisely the same as the odds of any toss of the coin being
heads: $\frac{1}{2}$.''
``The odds of getting 17 consecutive heads is unlikely, but once we have
gotten 16 heads in a row, it is not at all unlikely to get a 17th
head,'' repeated Alice.
``Right,'' said the Pig. ``I think you understand most of the basic points
of probability. But some probability questions are a lot more complicated
than that.''
``Like what?'' asked Alice.
``Well,'' the Pig said, ``let's go for a random walk and I'll try to explain a
problem. I like random walks.''
``What's a random walk?'' Alice inquired.
``A random walk,'' said the Pig, ``is one in which we stop at regular intervals
and decide at random which way to continue. A one-dimensional random walk
involves walking in a straight line where every few paces we stop and flip a
coin. If it's heads, we go forward, but if it's tails, we turn around and
go the other way. Let's try it.''
Alice and the Pig set off for their random walk. The Pig pointed out the
line that they were to walk. ``We'll toss a coin to decide if we
should go forward three paces or backwards three paces.'' The Pig flipped the
coin. ``Heads.'' They walked three steps forward.
``Let me toss the coin this time,'' begged Alice. The Pig gave her the coin.
She tossed it high up into the air. It landed with heads facing upward
again. They moved three more steps ahead. ``Can I toss it again?'' Alice
asked. The Pig nodded. This time the coin was tails. They walked three
steps back.
``Keep flipping the coin,'' instructed the Pig. Alice did so. The next toss
was heads so they moved three steps forward. Then tails and they moved
back. Then heads again and another heads. Then two tails before the next
heads. Then another heads and three tails in a row. Alice and the Pig
moved forward and backwards accordingly.
``We're not getting anywhere,'' complained Alice. ``We're just walking back
and forth. Every time we move forward some, we end up going back again.''
``This is true,'' said the Pig, ``but isn't that what you would expect? After
all, the odds that you'll get heads are $\frac{1}{2}$, the same as the odds that
you'll get tails. They should more or less balance out.''
``I guess,'' said Alice.
``What's interesting,'' said the Pig, ``is that if you toss the coin an awful
lot of times, we may end up way out in one direction or the other. We
wouldn't be anywhere near the center. But if we continue tossing the coin
indefinitely, we can be sure that we will end up at our
starting point. It might seem to take forever and ever, but it will happen
eventually.''
``If you say so,'' said Alice.
``I do,'' the Pig said. ``And we can have two- and three-dimensional
random walks as well. Though a three dimensional random walk would be
a flight really, and we couldn't expect to get back to where we
started then.''
Alice thought the Pig was making very little sense again. She was about to
tell him so when she noticed an odd-looking creature not too far ahead of
them. ``Who is that?'' asked Alice, pointing at the figure she had detected.
\section{Unbirthdays}
``Why, I have no idea,'' said the Pig. ``Let's find out.'' They abandoned
their random walk and approached the mysterious creature. It appeared to be
a gigantic green pickle wearing a pair of overalls.
It skipped over to Alice and the Pig and greeted them merrily. ``Hello,
hello! Who are you?''
``I'm Alice and this is my friend the Yellow Pig,'' said Alice. The Yellow
Pig blushed at this introduction. Alice continued timidly, ``And what are
you, sir? Are you a pickle?''
``I am,'' said the pickle. ``And is today your unbirthday?''
``My unbirthday?'' asked Alice. ``What's that?''
``It's simple,'' said the pickle. ``Is it your birthday?''
``No,'' said Alice.
``Then it's your unbirthday! You have a lot more unbirthdays than birthdays.
So why not celebrate your unbirthdays?'' asked the pickle.
``I'm afraid they never struck me as very special, I guess,'' replied Alice.
``Why would I celebrate unbirthdays?''
``Because there are so many of them,'' said the pickle. ``I relish the thought
of having frequent holidays to celebrate. Here, I've brought you both
unbirthday presents,'' he said, reaching into one of his pockets. He pulled
out two necklaces. ``I now present these to you for your unbirthdays,'' he
said solemnly.
Alice held back a giggle as the pickle handed her a necklace. The Yellow
Pig had a rather amused smile on his face. ``Thank you for your gifts,'' said
the Yellow Pig. ``Is there anything we can do for you in return?''
``Actually, maybe there is,'' said the pickle. ``A friend of mine asked me a
question the other day and it has been bothering me ever since.''
``What did he ask you?'' the Pig prompted.
``He asked me a question about birthdays. He said he went to a cucumber
convention recently of about two dozen cucumbers, and two of those cucumbers
shared the same birthday. He wanted to know if this was unusual or not. And
I'm supposed to be the one here who knows all about birthdays and unbirthdays,
but I've been thinking about his problem for days, and I have no ideas.''
``I'm sure we can help you,'' said the Pig. ``I'm not bad at mathematics, and
Alice here is actually quite good.'' This time it was Alice's turn to
blush.
``I don't know,'' said Alice. ``That problem sounds awfully hard. Isn't there
an easier problem we can solve?''
``Yes,'' said the Pig. ``There are quite a few easier problems we can solve
that will help us understand how to approach this one. For starters,
suppose I'm in a room with a bunch of people. What are the odds that one of
them shares a birthday with me? This is different from the original
problem, you see, because in this case I am one of the people sharing the
birthday.''
``It seems,'' said Alice, ``that you would be a lot less likely to find your
birthday partner than that anyone could. This problem is a lot more
specific.''
``It is much more specific,'' said the Pig. ``But now I'm going to reword the
problem again. Remember that probabilities add up to one?''
``I think I see where you are going with this,'' said the pickle. ``The odds
that either you share a birthday with someone or that you don't sum to one.
So instead of looking at the probability of a shared birthday, we can look at
the probability that you don't share a birthday with
anyone else in the room. And then we can subtract that result from one.''
``Exactly,'' said the Pig, ``you are one cool cucumber.''
``How many people are in the room?'' asked Alice.
``Well,'' hedged the Pig, ``I'm going to do something that mathematicians like
to do a lot. I'm going to make the problem easier by making it more
complicated.''
``Huh?'' said a confused Alice.
``Sometimes it's actually easier to tackle a more generalized problem. So in
this case, let's say that there are $r$ people in the room. I'm also going to
take some complexity out of the problem. Let's assume all years have 365
days. Leap year won't make much of a difference.''
``Oh, I hadn't even thought about leap years,'' said Alice. ``How
confusing.''
``So let's forget about leap year,'' said the pickle. ``People born on
February 29th are lucky because they have even more unbirthdays than the
rest of us.''
The Pig continued, ``Since 365 is such a big number to deal with, I'm going to generalize
that too. We'll just call it $n$ and let $n=365$. Then it's a problem about
$n$ and $r$.''
``$n$ and $r$?'' said Alice. ``Then where are the numbers? Is this another
one of those numberless math problems?''
``There are a lot of those,'' said the Pig. ``This problem does have some
computation in it, though. Many problems are solved not with actual
computation but with logic. Doing the computation often isn't nearly as
important as knowing how to set up the problem.''
``I agree,'' said the pickle. ``Now I can restate your problem: Suppose
there are $n$ days in a year, each of which are equally likely to be
birthdays, and $r$ people in a room. What are the odds that none of their
birthdays are on the same day as yours?''
``What is your birthday?'' asked Alice.
``It doesn't matter,'' said the pickle. ``In this problem the birthday is just
one day. Whatever day your birthday is, there are 364 days that someone
else can have a birthday so it's not on the same day as your birthday.
That's $n-1$ in our problem.''
``So the probability that one person doesn't share a birthday with you is
$n-1$?'' asked Alice.
``Well, $\frac{n-1}{n}$,'' said the Pig. ``because there are $n$ possible
days for the other person to have a birthday, and on $n-1$ of them, he or she
will have a different birthday.''
``Okay,'' said Alice. ``And there are $r$ people in the room. The probability
that the second person in the room doesn't share your birthday is also
$\frac{n-1}{n}$. And the probability that the third person doesn't share
your birthday is still $\frac{n-1}{n}$. All of the probabilities are the
same.''
``And there are $r$ of them,'' interrupted the pickle. ``So we multiply the
probability $\frac{n-1}{n}$ by itself $r$ times.''
``Multiplying something by itself repeatedly is raising something to a
power,'' said Alice. ``So the probability that none of the people share
your birthday is $(\frac{n-1}{n})^{r}$.''
``And we originally wanted the odds that someone does share a birthday with
you, so that's $1-(\frac{n-1}{n})^{r}$,'' finished the pickle.
``Excilantro,'' said the Pig. ``Now let's plug in some numbers,'' he said
reaching for his calculator. ``Fortunately, my calculator can do extremely
large calculations. Let's try to find when it is about equally likely that I
will and that I won't find a birthday mate.'' He tried a lot of numbers on
his calculator, with Alice and the pickle watching.
``Try a large number,'' suggested Alice. ``The probability that some one
person will have the same birthday as you is pretty low.'' The Pig tried 300
which they saw tipped the odds of finding a birthday match in the Pig's
favor.
``How about 200 cucumbers?'' asked the Pickle. This number was too low. After
many more tries, they agreed upon 253. If there are 253 cucumbers in the
room, the pickle has about a fifty percent chance of finding a birthmate.
``Neat,'' said the pickle. ``Now what about my original problem? Again, we
want to find when the probability is $\frac{1}{2}$, but the problem is
different. Any two people can share the same birthday.''
``Let's try finding when everyone has different birthdays,'' said Alice.
``That seemed to work last time.''
``Good idea,'' said the pickle, ``we can use the $n$ and the $r$ again, too.''
``How many different days are there for people to have birthdays?'' asked the
Pig.
``365 or $n$ each,'' said Alice. ``So for $r$ people, that's $n^{r}$.''
``And how many ways can each person have their birthday so it's not the same
as anyone else's?'' he asked.
``That depends,'' said the pickle. ``If there are only two people, the first
person can have his birthday on any of 365 days. The second person can have
his birthday on any of 364 days. That's like our last problem.''
``Right,'' said Alice, ``but if there are three people, the first can have his
birthday on 365 days, the second on 364 days, and the third on 363 days.
That's $n$, $n-1$, and $n-2$.''
``If there are four people,'' began the pickle, ``that's $n$, $n-1$, $n-2$, and
$n-3$.''
``So for $r$ people, it looks like there are $n$ ways for the first person to
have a birthday, $n-1$ ways for the second person to have a birthday, $n-2$
ways for the third person, and so on all the way to $n-r+1$ ways for the
$r$th person to have a birthday,'' Alice said.
``We can just multiply all of those together to get the number of ways $r$
people could have no birthdays in common,'' said the pickle.
``We can use factorials,'' added the Pig. ``Remember, $n!$ is $n \cdot (n-1)
\cdot (n-2) \cdot \cdots \cdot (n-r+1) \cdot \cdots \cdot 2 \cdot 1$.
We just want to divide out by all of that end stuff. In other words, we want
that product, but we want to remove the last $n-r$ terms from the product.
That's just $\frac{n!}{(n-r)!}$.''
``That's how many ways there are to have different birthdays,'' said Alice.
``Out of a total of $n^{r}$ ways to have birthdays at all.''
``Which means the probability of having no common birthdays is
$\frac{n!}{(n-r)!n^{r}}$,'' said the pickle.
``And the probability of having common birthdays is
$1-\frac{n!}{(n-r)!n^{r}}$. That's our solution!'' exclaimed Alice.
``Now we can answer my friend's question about two dozen cucumbers in a room,''
said the pickle. ``Oh, thank you both so much.''
``So what's the answer?'' asked Alice, curious to see how this would turn out.
The Pig reached for his calculator and computed their formula with $n=365$ and
$r=24$. The result was a little over 0.5 or fifty percent.
``It wasn't unusual at all,'' said the pickle. ``How odd. Can it really be
that with only twenty four cucumbers in a room you should expect that two will
have the same birthday?''
``That doesn't seem like very many,'' said Alice. ``Is that the least number
of cucumbers, err, people, in a room for which that is true?''
The Pig computed some more. ``Close, 23 is. With 22 people, the probability
of any two people sharing a birthday is 0.4757. With 23 people, the
probability is 0.5073.''
``Hmmm \ldots ,'' said Alice, ``that does seem like very few people.
Especially since it took 253 people to have a good chance of finding one
with the same birthday as you.''
``It is more than a bit counter-intuitive,'' agreed the Pig, ``but think about
how many different combinations of couples there are among 23 people. Why,
any two of them could share the same birthday. That means you have to
compare each person to every other person. That's 253 different
comparisons. Surely even though the odds are slim that any specific two will
be the same, they are pretty good that one of those 253 couplings will.''
``I guess so,'' said Alice. ``I hadn't thought of it that way, but you are
right. That's a lot of combinations.''
``Oh, thank you, thank you, thank you,'' gushed the pickle. ``You are both
wonderful. You have saved my reputation as the birthday pickle!'' And with
that he trotted off.
``What an odd fellow,'' the Yellow Pig commented to Alice. ``I've never seen a
birthday pickle before. He was a nice guy, though. I'm glad we could help
him.''
``Me, too,'' said Alice. ``And his problem was fun. Do you have any other
probability riddles like that?''
\section{Riddles}
``I know of many,'' said the Pig. ``Here's one of my favorites. It tends to
get people into quite an uproar, so I don't try to explain it very
often.''
``Oh, please do,'' said Alice.
``Well, okay,'' said the Pig. ``Here it goes: There are three doors. Behind
one of them is an adorable penguin holding a one million pig-pound check.
Behind the others are rather unhappy frogs. You get to pick a door and keep
its contents. Clearly you would rather have the penguin than either frog.
Now here's the catch. I know which door has the million pig-pound check and
which ones have the frogs. And after you pick the first door, instead of
opening it, I show you another door with a frog behind it. Then I give you an
option. You can either open the door that you have already chosen or you
can switch to the other unopened door. What should you do?''
Alice thought about the problem. In the Pig's problem there were two
frogs and a penguin with a check. If she picked a door, her odds were 1 in 3
that she would get a penguin. Once the Pig showed her one frog, her odds were
different. The remaining two doors contained a penguin and a single frog.
She explained this to the Pig. ``So now my odds are much better,'' she said.
``But I don't see how changing doors would help. There are two doors and one
of them has the money and the penguin. So my odds are 1 in 2 of getting the million
pig-pounds and the penguin.''
``That's what many people think,'' said the Pig, ``even a lot of well-respected
mathematicians. But many people, even mathematicians, are sometimes wrong.''
``You mean it does make a difference if I switch doors or not?'' asked Alice.
``It does,'' said the Pig. ``Quite a big difference. But I'm not going to
tell you which way is better. You have to figure that out for yourself so
you can see why one way is better than the other.''
Alice found the Pig's teasing somewhat annoying, but decided she could solve
the problem without the Pig's help if she thought about it enough. ``Okay,''
she said, ``it doesn't matter what door I pick first, right?''
``Correct,'' said the Pig. ``You can name your doors A, B, and C, and you can
always pick A. Picking B or C doesn't give you any advantage over picking
A. Because you don't know what is behind the doors. All of the doors are
the same until you know something about one of them.''
``And there are three possible ways the frogs and penguin can be arranged,''
Alice continued. ``Door A can have the penguin, door B can have the penguin,
or door C can have the penguin.'' The Pig nodded. ``So now all I have to do
is consider those three cases and what happens if I switch and what happens
if I don't.''
``Exactly,'' said the Pig.
``So, if the penguin is behind door A and I don't switch, I get the penguin.
If I do switch, I lose.''
``In that case you are better off not switching,'' the Yellow Pig said.
``That's one out of the three cases. What about the other two?''
``If the penguin is behind door B, I initially pick door A. You show me a
frog behind door C. Then if I don't switch, I'm stuck with the other frog.
But if I do switch, I get the million pounds.'' She continued, ``And for the
last case, I start out with door A as always, and the penguin is on the
other side of door C. You open up door B to show me a frog. If I don't
switch, I get a frog, and if I do switch, I get the million pounds.''
``In those last two cases it looks like it's better to switch,'' said the Pig.
``You're right it does,'' said Alice. ``So if I don't switch I have a 1 in 3
chance of winning, and if I do switch I have a 2 in 3 chance of winning. I
should switch,'' she concluded.
``I think you are right,'' said the Pig. ``Let me just write it down to make
sure.'' He wrote:
\begin{center}
\begin{tabular}{ccc|c|c}
door A & door B & door C & don't switch & switch \\ \hline
penguin & frog & frog & win & lose \\
frog & penguin & frog & lose & win \\
frog & frog & penguin & lose & win \\
\end{tabular} \end{center}
``I'm convinced,'' he said, ``And furthermore, that's one of the clearest
explanations I have heard as to why you should switch. Since you did so
well with that, I'll give you another probability teaser. This one is about
more complicated strategies. It's known as the Prisoner's Dilemma.''
``Does it have to do with prisoners?'' asked Alice.
``It does,'' said the Pig. ``Often when people are waiting for trial, they are
given the chance to cut a deal. Say there are two people who are being held
as accomplices for a crime. But because there is very little evidence, the
prosecution wants one of them to plead guilty and give testimony that the
other is involved. In return, the informant gets off free. The accomplice
who is surely guilty will then get a five year sentence.''
``What happens if neither one confesses?'' asked Alice. ``Or if both do?''
``If neither confess, they will still be convicted, but they will each only
get two years in jail. And if both confess, they will both get four years in
jail. So what should they do?''
Alice thought about this. ``If neither confess, they get two years each
for a total of four years. If both confess, they get four years each for a
total of eight. If either one confesses but not the other, they get a
combined five year sentence. It seems like neither of them should tell on
the other.''
``It does, doesn't it?'' the Yellow Pig agreed. ``But people are more selfish
than that. If you were one of the prisoners, and you were told you could be
let free without sentence, wouldn't you consider it? And what if you were
afraid that your accomplice would tattle on you? Then you would be better
off telling on him because then you would only get a four year sentence
instead of a five year one. No matter what your partner does, it is always
better for you to cooperate with the prosecution than to remain silent.''
``But if you and your partner are really clever,'' said Alice, ``you can both
stay quiet and get the best collective deal.''
``Right,'' said the Pig. ``And that becomes a bit more important in the next
part I'm going to tell you about. Let's make the problem more hypothetical.
What if this happens again and again? Tens of times, hundreds of times,
maybe even thousands. Does the strategy change? Not much. Have you ever
played the game Rock, Paper, Scissors?'' he asked. Alice nodded. ``The game
gets to be complicated because you try to guess what move your opponent will
make next. And your opponent is trying to do the same thing. How do you
guess what he will do?''
``By studying what moves he has already made,'' supplied Alice.
``It's the same thing here. Suppose you know nothing about your opponent
except for his or her previous moves. If you know the other prisoner has
tattled on you the past twenty times, you'll expect him to tattle on you
again. So you are better off telling on him as well to reduce your own
sentence. But if you know your opponent won't turn you in, you should keep
silent as well. Especially since once you turn him in, he probably won't be
so friendly in the future.''
``It gets very complicated, doesn't it?'' said Alice.
``It does,'' said the Pig. ``Now here's something even more complicated. What
if instead of there being just two prisoners in this situation, there are
dozens of them? They are having what you might call a prisoners' tournament
with multiple rounds. The winner of the tournament is the person who
acquires the fewest years. In each round each
prisoner decides which cohorts to turn in. And all of the prisoners know who
has previously turned them in. Then, the strategy of cooperation becomes
much more noticeably important.''
``So you keep track of who has tattled on you and then decided on whom to
tattle based on that?'' asked Alice.
``Exactly,'' said the Pig. ``Let's say that the prisoners only look at
the single previous round in the tournament.''
``Well,'' said Alice. ``There are only two things that a last move could
have been. Either a prisoner told on you or they didn't.''
``If a prisoner told on you,'' said the Pig, ``maybe you should keep your mouth
shut in the hopes that he or she will cooperate as well. Or maybe you should
tell on the prisoner because surely that prisoner will expect you to and will
continue telling on you.''
``And,'' continued Alice, ``if they don't tell on you, maybe you should tell
on them so you'll get fewer years. Or maybe you shouldn't tell on them
because they seem so nice, and if you both continue being nice to each other,
it is to both of your advantages.''
``You can see how complex this problem really is,'' said the Pig. ``In fact,
there really isn't much of a best single strategy. Which strategy is the
best depends on the strategies of the other prisoners in the tournament.
But one strategy stands out as a pretty good bet. It's known as the `tit
for tit; tat for tat' strategy.''
``Tit and tat?'' repeated Alice. ``That sounds silly.''
``Well maybe it is,'' said the Pig, ``but it's pretty simple. It goes like
this: Start out being nice; that is, keep silent for your first turn.
Then, if someone told on you, tell on them for the next turn. If someone
didn't tell on you, don't tell on them the next time around either. Simple,
huh?''
``It is,'' said Alice. ``But does it work?''
``See for yourself,'' said the Pig. ``Find a group of people and try
simulating a tournament like the one I've described. See who ends up with
the least combined number of years after dozens of rounds.''
``You know, I think I will,'' said Alice. ``Let's go find the pickle. And I'm
sure there must be others around here.''
``Good idea,'' said the Pig. ``I need to rest for a moment, but I'll catch
up to you.''
``Wait,'' said Alice. ``You've been such a help to me. There
must be something I can help you with. Isn't there some problem you have
never been able to solve?''
The Yellow Pig let out a sigh. ``My problem is not a math problem. You
don't really want to hear this.''
``No. I mean, yes. I mean, no, I really do want to hear it,'' stammered
Alice. ``Please.''
``When I was a little piglet, before I came here \ldots ,'' began the Pig.
``Before you came here?'' interrupted Alice. Then she apologized for
interrupting because she really did want the Pig to continue.
``When I was a little piglet, I lived in Pigland. That's up there, in the
clouds. It's beautiful there. There are dozens of cloud drifts.''
``That must be wonderful,'' said Alice. ``But you left.''
``I did,'' said the Pig. ``And I don't regret that. Math was my calling, but
I'm not an extremely good mathematician. Nowhere near as good as my friends
Isabel and Gus. I do wish Isabel would attempt more mathematics. She
really hasn't done anything lately.'' He sighed again. ``Anyway, here I get
to teach mathematics which is what I really wanted to do. And I love
meeting new people. Most of all, I love the garden. That's why I came here
in the first place.''
Alice interjected, ``It's the most beautiful garden I have ever seen.''
``My family has visited here every summer for years. My father made some
donations to the gallery one time, and we have been more than welcome here
ever since. I would spend hours in the garden, though it was a lot smaller
then than it is now. When I was in high school the caretaker of the garden
offered me a summer job helping in the garden. And it was wonderful. After
college I came back here. I still help out in the garden, and I get to give
tours whenever anyone visits.''
``Do you have many visitors?'' Alice asked.
``Not that many,'' said the Pig. ``Only those who are willing and ready to
learn ever visit here.''
``As I was?'' asked Alice. The Pig nodded. She blushed and changed the
subject. ``So your family must have been wealthy to donate to the museum.''
``They are, I suppose. My mother is fairly well-respected in the
mathematical community, though she gave up professional math when she had her
first litter. With seventeen little piglets in a few years, she didn't have
much time to spare.''
``I guess not,'' said Alice, who couldn't imagine having that many children,
or even that many brothers and sisters.
``My father is an astrophysicist, one of the leading scientists in Pigland.
Flying is big there.''
``Can you fly?'' asked Alice suddenly. ``I mean, I didn't think pigs could
fly, but you live in the clouds and all.''
A sad look crossed the Pig's face. ``Pigs can fly, yes. Quite a few of
them. And almost all of my brothers and sisters can. But I have never been
able to fly. I've always wanted to. Why, it's practically expected in my
family, but I cannot.''
Alice wanted to help her friend. ``You don't need to fly, do you? You
already have so many talents.''
``I know,'' the Pig said. ``I just wish I knew how to fly. I haven't the
slightest idea how to do it, and everything I try seems wrong.''
``I don't know how to fly,'' said Alice. ``I'll bet no one does. They just
fly. Like birds. They probably aren't trying to fly at all. They probably
want to land, only they are afraid. Or they are trying to land, and failing
completely to do so.'' She was almost convincing herself.
``I suppose,'' said the Pig, in a way that made it clear the
conversation was over. Alice was hesitant to leave the Pig, but
she was eager to meet others. So, assured that her porcine friend would
catch up with her, she continued on in search of Logicland's inhabitants.
Almost immediately she met a small dancing horse. ``Oh please, can you help
me?'' asked the horse. He looked so desperate for help and so happy to see
Alice, that she forgot about the Pig's math problem.
She sat down next to the Horse, for he was significantly shorter than she
was. ``How can I help you?''
``I have these riddles I need to solve. And I must be logical to solve them.
I'm afraid I'm not very logical, but I must solve them. The Queen said I
was not to leave until I had solved the riddles. I'm afraid I have no idea
how to solve them. Please,'' said the Horse, ``you must help me. There's no
one else here except the King, and I dare not wake him.''
``Why not?'' inquired Alice.
``Because if I wake him, I may cease to exist!'' the Horse
exclaimed anxiously.
``What are the riddles?'' asked Alice, hoping it would be easier to solve
the riddles than it was to understand the Horse.
``I have them written on scraps of paper,'' the Horse said. ``Here's the
first.'' Alice looked over at the paper. In a tiny, but rather legible
scrawl was written:
\vbox{
\ssp
\begin{flushleft}
1. \\
Babies are illogical. \\
Nobody is despised who can manage a crocodile. \\
Illogical persons are despised.
\end{flushleft}
\dsp
}
``That's it?'' asked Alice. ``What sort of a riddle is that?''
``I don't know,'' wept the Horse. ``I'm supposed to come to some kind of a
conclusion about babies and crocodiles. And it has to be the right
conclusion.''
``Don't think so hard,'' said Alice, who had no idea how to solve the
Horse's riddle. ``Just relax.'' Alice was certain that the two of them
would be able to solve the problem if they thought about it together. She
had learned not to be afraid of new challenges. A noise startled Alice. It
was the Yellow Pig.
Alice introduced the Pig to the Horse. ``Horse, this is my friend the
Yellow Pig. Yellow Pig, this is the Horse.'' They began to discuss the
Horse's puzzle. Alice was feeling dizzy, but she wanted to help the Horse.
The Yellow Pig took her aside. ``Do not worry about the horse.
I will help him with his problem to make sure he gets to where he needs to
be. Just as I helped you get to be where you are.''
``What do you mean?'' asked Alice. The Pig's words were swirling around her
head.
``It is time for you and your bear to return home. You have been here long
enough, and your family will worry if you are gone any longer. I've enjoyed our
time together, Alice. I will
miss you very much.'' The Yellow Pig extended a hoof and shook Alice's
hand. Alice noticed a tear in his eye, and she hugged him. She realized it
was time for her to return to her family and the more normal world she had
always known.
``Goodbye,'' said Alice. ``I won't forget you, and I won't forget your math
either. Come visit me sometime.''
The Pig smiled wistfully. He engaged in a conversation with the horse that
Alice could not hear. And maybe it was just her imagination, but she swore
she could see the two of them lift off the ground and float away. The Pig
was grinning.
\section{Q. E. D(ream).}
It was dark. The Yellow Pig was nowhere in sight. Neither was the horse.
Alice was sitting in a very familiar chair. It was a chair from her living
room. In fact, she was in her living room! Her stuffed animals were
seated around the fireplace. She reached into her pocket to find
that she still had her teddy bear.
Her cat, Dinah, walked across the room and leaped into her lap. Alice could
hear it purring.
``Kitty, how I've missed you,'' she said, nuzzling her face in Dinah's soft
fur. ``I wish you had gone with me. I went to a most amazing land and met
most entertaining people. Why, there was an unbirthday pickle wearing
overalls. He gave me this necklace,'' she said pointing at her neck. ``And I
spent the whole time with a yellow pig.'' The kitten raised its head and
purred some more. ``Yes, that's right. It was a yellow-colored pig. And he
was so nice. He showed me his magnificent garden with flowers and trees.
And he invited me to his cabin for yummy pies.''
Dinah mewed loudly. ``Oh, I'm sorry,'' said Alice, ``I'll bet no one has fed
you since I left.'' She got out some food for the cat. ``You would have
liked these islands that we went to. We spent hours maybe walking back and
forth along bridges. And the whole time the Pig was playing a joke on me.
Not a mean one really. But you would have been able to catch fish on the
beaches I am quite sure. And that would make you happy, wouldn't it?''
Dinah, engrossed in her food, ignored Alice.
``Although, I'm not sure how I got back here,'' she continued. ``One minute I was
going to help this horse. He was a very small horse, about your size, Dinah.
And then the next thing I knew I was here. Why, it was almost like waking up
from a dream.'' A look of almost horror flashed across Alice's face. ``Oh,
Kitty, you don't suppose it was all a dream, do you? It seemed so real. It was
a kind of bizarre wonderland. It was such an
incredible experience that it has to be real. I think I will believe it is
real, and that is what is important. It just has to be real, because I
still have the necklace,'' she concluded, almost certainly convinced.
``The Yellow Pig. I wonder what will happen to him now.'' Dinah had finished
her food and came back to sit beside Alice. ``I guess he will find somebody
else to tour. Oh, I do wish I could have stayed there longer.
Do you want to know how I got into that world, Kitty?''
asked Alice. ``Not the world with the Pig, but the world inside where I
just came from. Why, I stepped through a mirror. Imagine that. How can I
step through a mirror? I stepped into paintings as well. And walked upside
down. And Kitty, pay attention now, did you know there is a fourth
dimension? I met someone from the fourth dimension. He wasn't nice at all.
Just like our neighbor's dog. But I got him good. I told him there
was a fifth dimension.''
She continued, ``I don't know if that's true, of course, but doesn't it sound
confusing? I was talking about the fifth dimension. I've learned so much
from the Yellow Pig. He is something of a mathematician. That's what they
call people who are really good at math or do math or something. He told me
about magical numbers in plants, and numbers that never end, and introduced
me to his friends. There are different kinds of infinities. Prisoners
should cooperate. There were hundreds of rabbits. And pigs in holes. I
have so much to teach you.''
The kitten yawned. It was ready for its afternoon nap. It smiled a knowing
grin. ``Kitty, please tell me. Was I dreaming or not? Was I? Do you
dream? Did you dream about it, too? Were you the one dreaming and not I?
And if that was a dream, can I dream it again?'' But the kitten,
ignoring Alice's plea for answers, replied only with another yawn.