2.1 How many ways can these people be seated at the table, if Alice too can sit anywhere?
After the cake, the crowd wants to dance (boys with girls, remember, this is a conservative European party). How many possible pairs can be formed?
OK, this is easy: there are 3 girls, and each can choose one of 4 guys, this makes
3·4 = 12 possible pairs.
After about ten days, they really need some new ideas to keep the party going. Frank
has one:
“Let’s pool our resources and win a lot on the lottery! All we have to do is to buy
enough tickets so that no matter what they draw, we should have a ticket with the right
numbers. How many tickets do we need for this?”
(In the lottery they are talking about, 5 numbers are selected from 90.)
“This is like the seating” says George, “Suppose we fill out the tickets so that Alice
marks a number, then she passes the ticket to Bob, who marks a number and passes it to
Carl, ... Alice has 90 choices, no matter what she chooses, Bob has 89 choices, so there are
790 · 89 choices for the first two numbers, and going on similarly, we get 90 · 89 · 88 · 87 · 86
possible choices for the five numbers.”
“Actually, I think this is more like the handshake question” says Alice. “If we fill out
the tickets the way you suggested, we get the same ticket more then once. For example,
there will be a ticket where I mark 7 and Bob marks 23, and another one where I mark 23
and Bob marks 7.”