Browse · MathNet
PrintDutch Mathematical Olympiad
Netherlands counting and probability
Problem
A maths teacher has cards with the numbers to on them, one number per card. She places these cards in some order in a line next to each other on the table. The students come to the table, one at a time. The student whose turn it is goes once through the line of cards from left to right and removes every card she encounters that is (at that moment) the lowest card on the table. This continues till all cards are removed from the table. For example, if the line is in order , , , , , , , , , from left to right, the first student takes cards and . Then the second student comes who, in our example, takes the cards , , , , and . The third student then takes the cards , , and . Let be the number of sequences of cards that the teacher can choose so that exactly nine students get a turn to pick cards. Let be the number of sequences of cards that the teacher can choose so that exactly two students get a turn to pick cards. Prove that .
Solution
Consider a sequence of cards for which exactly nine students get a turn. Now replace all cards by . We will prove that this gives a sequence for which two students get a turn. We can repeat this process and that gives back the original sequence. Next, consider a sequence for which exactly two students get a turn and again replace all cards by . We will prove that this gives a sequence for which nine students get a turn. Altogether, it will follow that .
Suppose nine students get a turn. Then eight students each picked one card, and one student picks two cards. Therefore there is a number between and such that the following holds. The first student only picks card , the second student only picks card , ..., the -th student picks up cards and , the -th student only picks up card , ... Each pair of consecutive cards has to be in reverse order, except for the cards and . This means that the cards with are in reverse order, the cards and are in the right order, and the cards are in reverse order. (The pair of consecutive cards lies in the right order if lies left of , and in reverse order if lies right of .) We are now going to replace every card with card . If two cards were in the right order first, then they are now in reverse order; and if two cards were in reverse order first, then they are in the right order now. So we find that cards lie in the correct order, cards and lie in reverse order, and cards lie in the correct order. Then students will take cards as follows: The first student picks up cards , The second student picks up cards . So exactly two students will get a turn. This shows that if, in a sequence where exactly nine students get a turn, you replace every number by , then you get a sequence where exactly two students get a turn.
The opposite of this statement also needs a proof, and we proceed in a similar way. Suppose two students get a turn. Then there is a number between and such that the cards lie in the correct order (those get picked by the first student), cards and lie in reverse order, and cards lie in the correct order (those get picked by the second student). Again we are going to replace every card with card . Then we get a sequence where the cards lie in reverse order, cards and lie in the correct order, and cards lie in reverse order. We already saw that for such a sequence, exactly nine students get a turn. This shows that if, in a sequence where exactly two students get a turn, you replace every number by , then you get a sequence where exactly nine students get a turn.
We conclude that for every sequence of cards in which exactly nine students take their turn, there is a sequence in which exactly two students take their turn, and vice versa. It follows that .
Another way to prove this is by reversing the sequence of cards.
Suppose nine students get a turn. Then eight students each picked one card, and one student picks two cards. Therefore there is a number between and such that the following holds. The first student only picks card , the second student only picks card , ..., the -th student picks up cards and , the -th student only picks up card , ... Each pair of consecutive cards has to be in reverse order, except for the cards and . This means that the cards with are in reverse order, the cards and are in the right order, and the cards are in reverse order. (The pair of consecutive cards lies in the right order if lies left of , and in reverse order if lies right of .) We are now going to replace every card with card . If two cards were in the right order first, then they are now in reverse order; and if two cards were in reverse order first, then they are in the right order now. So we find that cards lie in the correct order, cards and lie in reverse order, and cards lie in the correct order. Then students will take cards as follows: The first student picks up cards , The second student picks up cards . So exactly two students will get a turn. This shows that if, in a sequence where exactly nine students get a turn, you replace every number by , then you get a sequence where exactly two students get a turn.
The opposite of this statement also needs a proof, and we proceed in a similar way. Suppose two students get a turn. Then there is a number between and such that the cards lie in the correct order (those get picked by the first student), cards and lie in reverse order, and cards lie in the correct order (those get picked by the second student). Again we are going to replace every card with card . Then we get a sequence where the cards lie in reverse order, cards and lie in the correct order, and cards lie in reverse order. We already saw that for such a sequence, exactly nine students get a turn. This shows that if, in a sequence where exactly two students get a turn, you replace every number by , then you get a sequence where exactly nine students get a turn.
We conclude that for every sequence of cards in which exactly nine students take their turn, there is a sequence in which exactly two students take their turn, and vice versa. It follows that .
Another way to prove this is by reversing the sequence of cards.
Techniques
Recursion, bijectionCounting two ways