Q15 Matemática  (IMO Shortlist 2019)

Alice tem um mapa do País das Maravilhas, um país que consiste em $n\ge 2$ cidades. Para cada par de cidades, há uma estrada estreita que vai de uma cidade à outra. Um dia, todas as estradas são declaradas como de “mão única”. Alice não tem informações sobre a direção das estradas, mas o Rei de Copas se ofereceu para ajudá-la. Ela tem permissão para fazer-lhe uma série de perguntas. Para cada pergunta, Alice escolhe um par de cidades e o Rei de Copas diz a ela a direção da estrada que liga essas duas cidades. Alice quer saber se há pelo menos uma cidade no País das Maravilhas com no máximo uma estrada de saída. Prove que ela sempre pode descobrir fazendo perguntas de no máximo $4n$.