MathDB

Path graph

U

is given, and a blindfolded player is standing on one of its vertices. The vertices of

U

are labeled with positive integers between 1 and

n

, not necessarily in the natural order. In each step of the game, the game master tells the player whether he is in a vertex with degree 1 or with degree 2. If he is in a vertex with degree 1, he has to move to its only neighbour, if he is in a vertex with degree 2, he can decide whether he wants to move to the adjacent vertex with the lower or with the higher number. All the information the player has during the game after

k

steps are the

k

degrees of the vertices he visited and his choice for each step. Is there a strategy for the player with which he can decide in finitely many steps how many vertices the path has?

Problem Statement