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.