Question 2
Let $k\le n$ be positive integers. IMO-nation has $n$ villages, some pairs joined by roads. The distance between two villages is the smallest number of roads in a route from one to the other; if no route exists, their distance is infinite.
A newly arrived traveler, called Alice in the English source and Xiaoxun in the Chinese source, is quarantined and cannot see the road network, but knows $n,k$. She wants to decide whether the greatest distance between villages is finite. In each telephone call to the IMO office, she names two villages and asks whether their distance is greater than, equal to, or less than $k$. The office answers truthfully, with infinite distance counted as greater than $k$. Prove that she can decide this in at most $2n^2/k$ calls.
A newly arrived traveler, called Alice in the English source and Xiaoxun in the Chinese source, is quarantined and cannot see the road network, but knows $n,k$. She wants to decide whether the greatest distance between villages is finite. In each telephone call to the IMO office, she names two villages and asks whether their distance is greater than, equal to, or less than $k$. The office answers truthfully, with infinite distance counted as greater than $k$. Prove that she can decide this in at most $2n^2/k$ calls.