olymmath

ISL 2019 C8

Alice has a map of Wonderland, a country consisting of n⩾2n \geqslant 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 4n4 n questions. Comment. This problem could be posed with an explicit statement about points being awarded for weaker bounds cnc n for some c>4c>4, in the style of IMO 2014 Problem 6. (Thailand)

Dataset text NuminaMath olympiads. Quoted with source.

Official text: IMO 2019 Shortlist booklet, page 9.

Solutions

Official solution Solution 1 by the IMO Problem Selection Committee

The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).

Similar problems

These problems have the most words in common with this statement.

Locator isl/2019/c8 · Tag MVZWF9EH61 · Edit this page on GitHub · Keys: j next, k previous