Maths Olympiad Prep

Library / /65 of 68

Combinatorics Difficulty 6.8 National Olympiad Prove it Estonia

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 nn. The last student to climb the lighthouse has got all the numbers 1 through nn with the lottery. As number nn is only available in the first round, that student had to get nn in the first round. As number n1n-1 is only available in 1st and 2nd round and in the 1st round that student did not get it, the student got n1n-1 in the 2nd round. Analogously, since n2n-2 is only available in the first three rounds and that student did not get it in the first two rounds, the student got n2n-2 in the 3rd round. Continuing the same way shows that the last one to climb the lighthouse got numbers nn 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 n1n-1 have to share in the first round numbers 1 through n1n-1, in the second one 1 through n2n-2, in third one 1 through n3n-3 and so on. Therefore for them this process is as if the person last to climb the tower did not participate at all and nn would be smaller by 1. For this holds for any nn, 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.