Competition problem — Combinatorics

Library / /58 of 86

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it United States

Problem:

Mr. Murgatroyd decides to throw his class a pizza party, but he's going to make them hunt for it first. He chooses eleven locations in the school, which we'll call $1,2, \ldots, 11$ . His plan is to tell students to start at location $1$ , and at each location $n$ from $1$ to $10$ , they will find a message directing them to go to location $n+1$ ; at location $11$ , there's pizza!

Mr. Murgatroyd sends his teaching assistant to post the ten messages in locations $1$ to $10$ . Unfortunately, the assistant jumbles up the message cards at random before posting them. If the students begin at location $1$ as planned and follow the directions at each location, show that they will still get to the pizza.

Solution

Solution:

If the students never visit the same room twice, then their hunt lasts a finite number of steps. In that case, they must reach the pizza (since the hunt always continues if they have not yet reached the pizza).

Therefore, the only way for the students to not reach the pizza is for them to visit the same room twice, which gets them stuck in a loop. Such a loop must consist of $n$ rooms containing $n$ messages that collectively point to that set of $n$ rooms. But this means that all the messages pointing into the loop are in rooms that are part of the loop, so there's no way to enter the loop from outside.

Room $1$ can't be part of a loop, since no message points to room $1$ . Thus, the students do not begin in a loop. Since they cannot enter a loop, they eventually get to the pizza. (In fact, they get to the pizza at least as quickly as Mr. Murgatroyd intended, since the worst case is that they have to visit every room once!)

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.