Q18 Matemática  (Balkan MO Shortlist 2020)

Um videogame estratégico consiste em um mapa de um número finito de cidades. Em cada cidade existem $k$ direções, rotuladas de $1$ até $k$. Uma das cidades é designada como inicial e outra – como terminal. A partir da cidade inicial, o herói do jogo faz uma sequência finita de movimentos. A cada movimento o herói seleciona uma direção da cidade atual. Isso determina a próxima cidade que ele visita e uma certa quantidade positiva de pontos que ele recebe. Dois videogames estratégicos são equivalentes se para cada sequência de direções o herói pode chegar à cidade terminal a partir da inicial em um jogo, ele pode fazê-lo no outro jogo e, além disso, ele acumula a mesma quantidade de pontos em ambos os jogos. . No seu aniversário, John recebe dois videogames estratégicos – um com cidades de $N$ e outro com cidades de $M$. Ele afirma que eles são equivalentes. Marry está convencido de que não. Casar está certo. Prove que ela pode fornecer uma sequência de no máximo $N+M$ direções que mostre que os dois jogos não são de fato equivalentes. $Stefan$ $Gerdjikov,Bulg\acute{a}ria$