Q7 Matemática  (IMO Shortlist 2015)

Em Lineland existem $n\ge 1$ cidades, dispostas ao longo de uma estrada que vai da esquerda para a direita. Cada cidade tem uma escavadeira esquerda (colocada à esquerda da cidade e virada para a esquerda) e uma escavadora direita (colocada à direita da cidade e virada para a direita). Os tamanhos dos bulldozers de $2n$ são distintos. Toda vez que uma escavadeira esquerda e direita se confrontam, a escavadeira maior empurra a menor para fora da estrada. Por outro lado, os bulldozers estão bastante desprotegidos na retaguarda; assim, se um trator atinge a traseira de outro, o primeiro empurra o segundo para fora da estrada, independentemente de seus tamanhos. Sejam $A$ e $B$ duas cidades, com $B$ à direita de $A$. Dizemos que a cidade $A$ pode varrer a cidade $B$ se a escavadeira certa de $A$ puder passar para $B$ empurrando todas as escavadeiras que encontrar. Da mesma forma, a cidade $B$ pode varrer a cidade $A$ para longe se a escavadeira esquerda de $B$ puder passar para $A$ empurrando todas as escavadeiras de todas as cidades em seu caminho. Prove que existe exatamente uma cidade que não pode ser varrida por nenhuma outra.