2019 IMO Shortlist C8

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

爱丽丝有一张仙境地图，这是一个由 $n \geq 2$ 城镇组成的国家。对于每对城镇，从一个城镇到另一个城镇都有一条狭窄的道路。有一天，所有的道路都被宣布为“单向”。爱丽丝不知道道路的方向，但红心国王愿意帮助她。她被允许问他一些问题。对于每个问题，爱丽丝依次选择一对城镇，红心国王告诉她连接这两个城镇的道路的方向。爱丽丝想知道仙境中是否至少有一个城镇最多有一条外出路。通过提出最多 4 美元的问题来证明她总能找到答案。评论。这个问题可以通过明确的声明来提出，即以 IMO 2014 年问题 6 的风格，对某些 $c>4$ 的较弱边界 $c n$ 授予分数。(泰国)