Problem A. 859. (September 2023)

A. 859. Path graph \(\displaystyle U\) is given, and a blindfolded player is standing on one of its vertices. The vertices of \(\displaystyle U\) are labeled with positive integers between \(\displaystyle 1\) and \(\displaystyle 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 \(\displaystyle k\) steps are the \(\displaystyle 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?

Proposed by Márton Németh, Budapest

(7 pont)

Deadline expired on October 10, 2023.

Such a strategy does exist.

An algorithm will decide in each step whether to choose the adjacent vertex with the smaller or the bigger label, and will predict whether we will arrive in a vertex with degree 1. We say that the algorithm made a mistake when it predicts a vertex with degree 1 and we actually step in a vertex with degree 2, or we arrive at a vertex with degree 1 without the algorithm predicting it.

Lemma: for every possible labeling of a path with \(\displaystyle n\) vertices there exists an algorithm which makes no mistake in this path, but it will make a mistake in all other paths that are longer than \(\displaystyle n\).

Based on this lemma it is easy to prove our claim. For every \(\displaystyle k\) there exists finitely many labelings of a path with \(\displaystyle k\) vertices. We will apply our algorithm for all possible labelings of the path for \(\displaystyle k=1\), then \(\displaystyle k=2\) and so on. If the path has length \(\displaystyle n\), we will see a mistake in all paths of length \(\displaystyle k<n\), so we know that the path has length at least \(\displaystyle n\). Now we try the algorithm for all possible labelings of the path with \(\displaystyle n\) vertices. The algorithm won't make a mistake when the assumed labeling coincides with the actual labeling. This will show that the path has length at most \(\displaystyle n\). Thus we found out that the length of the path is \(\displaystyle n\). So this strategy will find the length of the path in finitely many steps.

Proof of the lemma:

Let us consider a path with \(\displaystyle n\) vertices and a corresponding labeling and call it \(\displaystyle U\). We will create an algorithm correspondng to \(\displaystyle U\). We assume that we are at the vertex with label 1. We will perform a sequence of steps that takes us to an endpoint of the path. If we end up in an endpoint sooner, or we don't end up in an endpoint, we know that we haven't started from the vertex with label 1. Now we assume that we start at vertex 2, and follow a sequence of steps taking to an endpoint. If the result is not consistent with our assumption, we know that we haven't started at 2. Now we assume we start at 3, and follow the same algorithm, and so on. This is a finite algorithm (it cannot perform more than \(\displaystyle n^2\) steps), and if the actual path is \(\displaystyle U\), we will eventually find an endpoint.

We can forget about the walk we have done so far, and now our aim is to create a finite algorithm that starts from an endpoint and can be performed in \(\displaystyle U\), but will lead to a mistake in every path that is longer than \(\displaystyle U\).

Without loss of generality we can assume that we started from the left endpoint. In the first step we will surely land on the second vertex from the left.

For \(\displaystyle k\le \frac{n+1}{2}\) we know that we stand on the \(\displaystyle k^{th}\) vertex from the left. After this we will perform the sequence of steps that would take us from the \(\displaystyle k^{th}\) vertex from the left to the left endpoint in \(\displaystyle U\), and the algorithm predicts that we are in a vertex with degree 1. This works in \(\displaystyle U\), however, in a path that is longer than \(\displaystyle U\) this will lead to a mistake, or we went straight back to the left endpoint, since \(\displaystyle k\le \frac{n+1}{2}\) guarantees that we cannot end up in the right endpoint in \(\displaystyle k-1\) steps. Now we perform those steps that took us to the \(\displaystyle k^{th}\) vertex from the left endpoint. This will take us there again. Now we check whether at the beginning of this step we moved to the smaller or the bigger neighbour from the \(\displaystyle k^{th}\) vertex. We know that this leads in the direction of the left endpoint, so we will make a move in the opposite direction. This guarantees that we are at the \(\displaystyle (k+1)^{th}\) vertex after this step.

We iterate this until \(\displaystyle k\le \frac{n+1}{2}\).

If \(\displaystyle n\) is even, we know that we will ultimately arrive at the \(\displaystyle \left(\frac{n}{2}+1\right)^{st}\) vertex from the left, and if \(\displaystyle n\) is odd, at the \(\displaystyle \left(\frac{n+3}{2}\right)^{nd}\) vertex. Now we perform the sequence of steps that would take us to the right endpoint from here in \(\displaystyle U\), and predict that we will arrive in a vertex with degree 1. This is correct in \(\displaystyle U\), however in path that is longer than \(\displaystyle U\) we don't perform enough steps to end up in an endpoint, so we will encounter a mistake.

Thus this algorithm that works correctly in \(\displaystyle U\), however, it will make a mistake in longer paths, thus finishing our proof.

Statistics:

19 students sent a solution.
7 points:	Czanik Pál, Duchon Márton, Tarján Bernát, Varga Boldizsár, Wiener Anna.
6 points:	Farkas 005 Bendegúz, Holló Martin, Vigh 279 Zalán.
3 points:	3 students.
2 points:	3 students.
1 point:	3 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, September 2023