Cities and Induction. Trying to find a dead end.

Question

There are ($n$ > 1) cities and every pair of cities is connected by exactly one road. The road can go only from A to B, only from B to A, or in both directions.

The goal is to find a dead-end city, if it exists, i.e., a city x to which there is a direct one-way road from every other city, but there is no direct road going from X to any other city. You are allowed to make only one type of question – “Is there a direct road going from city A to city B?” The answer to this question will be a “Yes” or a “No”. Use mathematical induction to show that if there are cities then one can find a dead-end city, if there is one, using at most 2(−1) questions.

My thoughts:

Base C: = 2

2(2−1)=2 questions. Ask if there is a road from A to B. And ask if there is a road from B to A.

Induction H: Assume that the claim is true when = , for some k > 1.

2(−1)

IS: We want to prove that the claim is true when n = k + 1

I also noted that there can only be a maximum of one dead-end city. But I'm unsure of where to proceed.

I'd use $n=1$ as base case - no questions needed, the one city is vacuously dead end — Hagen von Eitzen, Sep 29 '19 at 17:51
it wouldn't make sense to have 1 city. nevertheless, I edited this question to make it more clear — Harold Smith, Sep 29 '19 at 17:54
To clarify, our task is "to find a dead end if there is one". The task is not "to determine whether there is a dead end and if so find one". — Hagen von Eitzen, Sep 29 '19 at 18:11

score 1 · Answer 1 · answered Sep 29 '19 at 18:08

If $n=1$, ask zero questions and know that the one city $A$ is vacuously a dead end (i.e., vacuously "every other" city has a one-way road to $A$, and vacuously there is no road from $A$ to any other city).

Assume $n>1$. Pick two cities $A,B$ and ask whether there is a direct road $A\to B$.

If "yes", $A$ cannot be the dead-end, but perhaps $B$. Use at most $2((n-1)-1)$ questions to find a dead end $X$ in the graph obtained by removing $A$. Now in the original graph, the only possible dead ends are $X$ and $B$ (and it may happen that $X=B$, in which case we are already done). Ask about the existence $B\to X$ (thereby using up the $2(n-1)$ question budget). If "yes", the dead end must be $X$; if "no" the dead end must be $B$.
If "no", $B$ cannot be the dead end, but $A$ can. Proceed as above, with $A,B$ swapped.

score 0 · Answer 2 · answered Sep 29 '19 at 18:16

Lemma: Given this city structure with $n$ cities, you can determine exactly one candidate to be the dead end city with $n-1$ questions.

Pf: By induction. Easily done with $2$ cities and one question. For $k+1$ cities, choose two called $A$ and $B$. Ask if there is a road from $A$ to $B$. If there is, $A$ cannot be the dead-end city, otherwise $B$ cannot be the dead-end city. By the induction hypothesis, you can whittle the remaining $k$ candidates down to 1 with another $k-1$ questions.

Proof of proposition: Given $n$ cities, we can determine a candidate city $X$ to be the dead end city in $n-1$ questions. Ask whether there is a road from $X$ to each of the remaining $n-1$ cities. If none of them are, then $X$ is a dead end, otherwise there is no dead end city. This requires a maximum of $2(n-1)$ questions.

Cities and Induction. Trying to find a dead end.

2 Answers2