Problem 1659

We will show Alice needs to ask at most $4 n-7$ questions. Her strategy has the following phases. In what follows, $S$ is the set of towns that Alice, so far, does not know to have more than one outgoing road (so initially $|S|=n$). Phase 1. Alice chooses any two towns, say $A$ and $B$. Without loss of generality, suppose that the King of Hearts' answer is that the road goes from $A$ to $B$. At the end of this phase, Alice has asked 1 question. Phase 2. During this phase there is a single (variable) town $T$ that is known to have at least one incoming road but not yet known to have any outgoing roads. Initially, $T$ is $B$. Alice does the following $n-2$ times: she picks a town $X$ she has not asked about before, and asks the direction of the road between $T$ and $X$. If it is from $X$ to $T, T$ is unchanged; if it is from $T$ to $X, X$ becomes the new choice of town $T$, as the previous $T$ is now known to have an outgoing road. At the end of this phase, Alice has asked a total of $n-1$ questions. The final town $T$ is not yet known to have any outgoing roads, while every other town has exactly one outgoing road known. The undirected graph of roads whose directions are known is a tree. Phase 3. During this phase, Alice asks about the directions of all roads between $T$ and another town she has not previously asked about, stopping if she finds two outgoing roads from $T$. This phase involves at most $n-2$ questions. If she does not find two outgoing roads from $T$, she has answered her original question with at most $2 n-3 \leqslant 4 n-7$ questions, so in what follows we suppose that she does find two outgoing roads, asking a total of $k$ questions in this phase, where $2 \leqslant k \leqslant n-2$ (and thus $n \geqslant 4$ for what follows). For every question where the road goes towards $T$, the town at the other end is removed from $S$ (as it already had one outgoing road known), while the last question resulted in $T$ being removed from $S$. So at the end of this phase, $|S|=n-k+1$, while a total of $n+k-1$ questions have been asked. Furthermore, the undirected graph of roads within $S$ whose directions are known contains no cycles (as $T$ is no longer a member of $S$, all questions asked in this phase involved $T$ and the graph was a tree before this phase started). Every town in $S$ has exactly one outgoing road known (not necessarily to another town in $S$). Phase 4. During this phase, Alice repeatedly picks any pair of towns in $S$ for which she does not know the direction of the road between them. Because every town in $S$ has exactly one outgoing road known, this always results in the removal of one of those two towns from $S$. Because there are no cycles in the graph of roads of known direction within $S$, this can continue until there are at most 2 towns left in $S$. If it ends with $t$ towns left, $n-k+1-t$ questions were asked in this phase, so a total of $2 n-t$ questions have been asked. Phase 5. During this phase, Alice asks about all the roads from the remaining towns in $S$ that she has not previously asked about. She has definitely already asked about any road between those towns (if $t=2$). She must also have asked in one of the first two phases about at least one other road involving one of those towns (as those phases resulted in a tree with $n>2$ vertices). So she asks at most $t(n-t)-1$ questions in this phase. At the end of this phase, Alice knows whether any town has at most one outgoing road. If $t=1$, at most $3 n-3 \leqslant 4 n-7$ questions were needed in total, while if $t=2$, at most $4 n-7$ questions were needed in total. Comment 1. The version of this problem originally submitted asked only for an upper bound of $5 n$, which is much simpler to prove. The Problem Selection Committee preferred a version with an asymptotically optimal constant. In the following comment, we will show that the constant is optimal. Comment 2. We will show that Alice cannot always find out by asking at most $4 n-3\left(\log _{2} n\right)-$ 15 questions, if $n \geqslant 8$. To show this, we suppose the King of Hearts is choosing the directions as he goes along, only picking the direction of a road when Alice asks about it for the first time. We provide a strategy for the King of Hearts that ensures that, after the given number of questions, the map is still consistent both with the existence of a town with at most one outgoing road, and with the nonexistence of such a town. His strategy has the following phases. When describing how the King of Hearts' answer to a question is determined below, we always assume he is being asked about a road for the first time (otherwise, he just repeats his previous answer for that road). This strategy is described throughout in graph-theoretic terms (vertices and edges rather than towns and roads). Phase 1. In this phase, we consider the undirected graph formed by edges whose directions are known. The phase terminates when there are exactly 8 connected components whose undirected graphs are trees. The following invariant is maintained: in a component with $k$ vertices whose undirected graph is a tree, every vertex has at most $\left[\log _{2} k\right\rfloor$ edges into it. - If the King of Hearts is asked about an edge between two vertices in the same component, or about an edge between two components at least one of which is not a tree, he chooses any direction for that edge arbitrarily. - If he is asked about an edge between a vertex in component $A$ that has $a$ vertices and is a tree and a vertex in component $B$ that has $b$ vertices and is a tree, suppose without loss of generality that $a \geqslant b$. He then chooses the edge to go from $A$ to $B$. In this case, the new number of edges into any vertex is at most $\max \left\{\left\lfloor\log _{2} a\right\rfloor,\left\lfloor\log _{2} b\right\rfloor+1\right\} \leqslant\left\lfloor\log _{2}(a+b)\right\rfloor$. In all cases, the invariant is preserved, and the number of tree components either remains unchanged or goes down by 1. Assuming Alice does not repeat questions, the process must eventually terminate with 8 tree components, and at least