Q8 Matemática (Baltic Way 2018)
Um grafo tem vértices. Uma lebre invisível senta-se em um dos vértices. Um grupo de caçadores tenta matar a lebre. Em cada movimento todos eles atiram simultaneamente: cada caçador atira em um único vértice, eles escolhem os vértices alvo de forma cooperativa. Se a lebre estava em um dos vértices alvo durante um tiro, a caçada está terminada. Caso contrário, a lebre pode ficar em seu vértice ou pular para um dos vértices vizinhos. Os caçadores conhecem um algoritmo que lhes permite matar a lebre em no máximo movimentos. Prove que então existe um algoritmo que permite matar a lebre em no máximo movimentos.