BALKAN-SL 2020 C4

A strategical video game consists of a map of finitely many towns. In each town there are $k$ directions, labelled from $1$ through $k$ . One of the towns is designated as initial, and one - as terminal. Starting from the initial town the hero of the game makes a finite sequence of moves. At each move the hero selects a direction from the current town. This determines the next town he visits and a certain positive amount of points he receives. Two strategical video games are equivalent if for every sequence of directions the hero can reach the terminal town from the initial in one game, he can do so in the other game, and, in addition, he accumulates the same amount of points in both games. For his birthday John receives two strategical video games - one with $N$ towns and one with $M$ towns. He claims they are equivalent. Marry is convinced they are not. Marry is right. Prove that she can provide a sequence of at most $N +M$ directions that shows the two games are indeed not equivalent.

Stefan Gerdjikov, Bulgaria