I was working on a unsolved problem (how to clean up my room) when the phone rang. For once, I rushed to pick up the receiver gladly. It was Mavuna again.
``I have a problem.'' he said. I wondered that didn't surprise me.
``Trish asked me to write down for her all the possibilities of picking seven numbers from twenty. I've tried but there seem to be too many. What do I do?''
For a start, start paying me for all this consultancy, I thought. I didn't say so however, since I was brought up to be polite.
``So you have the numbers 1, 2, 3, ..., 20 and you need to pick seven of them. Do they have to be in order? For instance, is picking 4, 5, 6, 7, 8, 9, 10 the same as picking 10, 9, 8, 7, 6, 5, 4?''
``Yes, order is important. So those two possibilities should both be counted.''
``That's easy then. But you won't succeed in writing them down. There are well over ten million possibilities.''
There was a long silence at the other end of the line. I wondered if the PTC was dead again. Eventually I heard a very meek voice ask me how the calculation had been performed.
Look, you have seven places to fill, right? The order of the places is important, so we can deal with each place in a step-by-step fashion. There are 20 possible numbers I can pick for the first place. Suppose I pick say, 13. Then I have 19 possible numbers - 1, 2, ..., 12, 14, ..., 20 - available for the second place. Oh wait a minute, can I pick 13 again?''
``No,'' he replied, ``once you use a number, you cannot pick it again.''
``Fine. So you have 20×19 possibilities for the first two places. Suppose I pick 4 for the second place. Then there are 18 numbers - 1, 2, 3, 5, 6, ..., 11, 12, 14, ..., 20 - available for the third place. There are thus 20×19×18 possibilities for the first three places. By extending this argument we see that there are 20×19×18×17×16×15×14 possibilities for all the seven places. Each of the numbers mentioned is greater than 10, so the product of all of them must be greater than 10 000 000, which is the answer I gave you.''
``What's the exact answer?''
I grabbed a calculator and began to punch it. Then I really punched it, for its batteries were dead. I found another one, and then the answer: 390 700 800.
``Mavuna, why do you want to write out 400 million numbers for Trish?''
I suspected he would be willing to write 400 billion numbers for her, but didn't add this. This politeness business was getting to my head.
``Well,'' he replied sheepishly, ``She wants to know the number of cards she must get from the OK in order to win the Grand Challenge.''
He thanked me hastily and put the phone down before I could say anything. But I was too busy cursing myself for not guessing such an obvious reason to worry about that. The OK, a large shopping chain in Zimbabwe, held an annual promotion every year where they sponsored a horse race called the Grand Challenge. The promotion would run in May/June and every OK shopper in this period received a number of cards (depending on the amount of purchases made). There are different types of cards, but 99% of them are 'Prediction cards' which can be used by the shopper to predict the first seven (out of twenty) horses in the race. Anyone who succeeded would get a LOT of money. The promotion is quite popular in Zimbabwe, much to the dismay of other shopping chains.
Once I had managed to stop my self-maledictions, my mind pondered related questions:
And finally: