Cities and Induction. Trying to find a dead end. 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. 
 A: 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.
A: 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.
