20 students participated on a field trip. They all wanted to climb on top of a lighthouse, but only one person was allowed to the lighthouse at once. The order of climbing was determined by a lottery such that in the beginning every student is randomly assigned a number of 1 through 20 (such that no number is repeated). The one who gets the smallest number is the first one to climb the lighthouse. In the next round all the rest of the students are randomly assigned numbers 1 through 19 and the one who gets the smallest number gets to be the next one to climb the lighthouse. This process is repeated until all the students have climbed the lighthouse. Due to a strange occurrence no one student was assigned the same number more than once. Miku was assigned the number 14 in the first round. Find all possibilities what number could have been assigned to Miku in the 9th round.
Solution
Let the number of students be . The last student to climb the lighthouse has got all the numbers 1 through with the lottery. As number is only available in the first round, that student had to get in the first round. As number is only available in 1st and 2nd round and in the 1st round that student did not get it, the student got in the 2nd round. Analogously, since is only available in the first three rounds and that student did not get it in the first two rounds, the student got in the 3rd round. Continuing the same way shows that the last one to climb the lighthouse got numbers through 1 in decreasing order, or got the largest available number in every round.
The rest of the students who only participated in rounds 1 through have to share in the first round numbers 1 through , in the second one 1 through , in third one 1 through and so on. Therefore for them this process is as if the person last to climb the tower did not participate at all and would be smaller by 1. For this holds for any , all students get the numbers in decreasing order with every next one being smaller by 1, that includes Miku. This allows us to find that in the 9th round Miku got number 6.