IMO 2019 Shortlist C8
Alice has a map of Wonderland, a country consisting of n ě 2 towns. For every pair of towns, there is a narrow road goin...
Category: Combinatorics
Problem
Alice has a map of Wonderland, a country consisting of n ě 2 towns. For every pair of towns, there is a narrow road going from one town to the other. One day, all the roads are declared to be “one way” only. Alice has no information on the direction of the roads, but the King of Hearts has offered to help her. She is allowed to ask him a number of questions. For each question in turn, Alice chooses a pair of towns and the King of Hearts tells her the direction of the road connecting those two towns. Alice wants to know whether there is at least one town in Wonderland with at most one outgoing road. Prove that she can always find out by asking at most 4n questions. Comment. This problem could be posed with an explicit statement about points being awarded for weaker bounds cn for some c ą 4, in the style of IMO 2014 Problem 6. (Thailand)