BMO Short List

Without loss of generality we may assume that the set of directions is $D=\{1,2,\dots ,k\}$. Let us enumerate the towns in the first game from 1 through $N$ and the towns in the second game from $N+1$ through $N+M$. Without loss of generality we may assume that the initial and terminal towns in the first game are 1 and $N$, whereas in the second game these are $N+1$ and $N+M$, respectively.

Next we consider a directed labelled graph $G=(V,\lambda )$ where $V=\{1,2,\dots ,N+M\}$ and $\lambda :V\times D\to V\times \mathbb{N}$ maps a current town $u$ and direction $d$ to $\lambda (v,d)=(u,p)$, where $u$ is the next town and $p$ is the amount of points awarded for this move. In particular if $v\le N$ if and only if $u\le N$. For each vertex $v\in V$, we denote with $L_n(v)=L_{n,G}(v)$ the set of all pairs $(s,p)$, where $s$ is a sequence of directions of length less than or equal to $n$ that leads from $v$ to a terminal town and $p$ is total amount of points awarded for this sequence. $L(v)$ is the union of all sets $L_n(v)$ for $n\in \mathbb{N}\cup \{0\}$. With this notion we want to prove that: $$L(1)=L(N+1)\text{if and only if}{L}_n(1)=L_n(N+1)\text{for all }n\le N+M.$$ To this end, we first slightly modify the games by awarding the hero points he deserves as soon as possible. Formally, let: $$c(v)=\min \{p:(s,p)\in L_{M+N}(v)\text{ for some }s\}.$$ Since the points are always positive, every cycle in $G$ brings a positive amount of points. Therefore, $p^{\prime }\ge c(v)$ for every $n$ and every pair $(s^{\prime },p^{\prime })\in L_n(v)$. In particular, if $\lambda (v,d)=(u,p)$ then since the hero can win $p+c(u)$ points starting from $v$, we obtain $p+c(u)\ge c(v)$. Note that if $c(1)\ne c(N+1)$, then $L_{N+M}(1)=L_{N+M}(N)$ are vacuously distinct and we are done. Thus, we may assume that $c(1)=c(N+1)$.

Let $G^{\prime }=(V,{\lambda }^{\prime })$ be defined by ${\lambda }^{\prime }(v,d)=(u,p+c(u)-c(v))$ whenever $\lambda (v,d)=(u,p)$. By the above argument every move in $G^{\prime }$ is awarded with non-negative amount of points. Furthermore, an easy inductive argument shows that $(s,p)\in L_n(v)$ if and only if $(s,p-c(v))\in L_n^{\prime }(v)$, where $L_n^{\prime }(v)=L_{n,G^{\prime }}(v)$. Hence $L_n(1)=L_n(N+1)$ if and only if $L_n^{\prime }(1)=L_n^{\prime }(N+1)$.

Assume that $L^{\prime }(u)=L^{\prime }(v)$ and consider an arbitrary direction $d$. If $(u^{\prime },p^{\prime })=\lambda (u,d)$ and $(v^{\prime },q^{\prime })=\lambda (v,d)$, we claim that $L^{\prime }(u^{\prime })=L^{\prime }(v^{\prime })$ and $p^{\prime }=q^{\prime }$. Indeed, let $s$ be such a sequence of moves that $(s,c(u^{\prime }))\in L(u^{\prime })$. Hence $((d,s),p^{\prime })\in L^{\prime }(u)$. Since $L^{\prime }(u)=L^{\prime }(v)$ and there are no negative points along the arcs, we get $q^{\prime }\le p^{\prime }$. Similarly, $p^{\prime }\le q^{\prime }$ and therefore $p^{\prime }=q^{\prime }$. Now, it is easy to see that if $(s,p)\in L^{\prime }(u^{\prime })$ then $((d,s),p+p^{\prime })\in L^{\prime }(u)=L^{\prime }(v)$ and therefore $(s,p)\in S(v)$ where we used that $p^{\prime }=q^{\prime }$. To reverse inclusion proceed similarly.

Finally, consider the equivalence relations ${\equiv }^{(n)}$ recursively defined below: $$\begin{array}{rl}u{\equiv }^{(0)}v& \text{ if and only if either }u,v\in \{N,M+N\}\text{ or }u,v\notin \{N,M+N\},\\ u{\equiv }^{(n+1)}v& \text{ if and only if }u{\equiv }^{(n)}v,\text{ and }{u}^{\prime }{\equiv }^{(n)}{v}^{\prime }\text{ and }{p}^{\prime }=q^{\prime }\text{ for all }d\le D,\end{array}$$ where $(u^{\prime },p^{\prime })={\lambda }^{\prime }(u,d)$ and $(v^{\prime },q^{\prime })={\lambda }^{\prime }(v,d)$. Since ${\equiv }^{(n+1)}$ is contained in ${\equiv }^{(n)}$, and each equivalence relation has no more than $N+M$ classes, it follows that ${\equiv }^{(n)}$ and ${\equiv }^{(n+1)}$ coincide for some $n<N+M$. Therefore, for this particular $n$, an easy inductive argument shows that ${\equiv }^{(m)}$ and ${\equiv }^{(n)}$ are the same for all $m\ge n$. Hence if $u{\equiv }^{(n)}v$ an induction on the length of the sequence of moves reveals that $(s,p)\in L^{\prime }(u)$ if and only if $(s,p)\in L^{\prime }(v)$. Consequently, $L^{\prime }(u)=L^{\prime }(v)$.

For every direction $d$ let $A_d$ be the $(N+M)\times (N+M)$ matrix whose entries $a_d(i,j)$ are defined by $$a_d(i,j)=\{\begin{array}{ll}{2}^p,& \text{if starting from town }i\text{ and following direction }d\\ 0,& \text{otherwise.}\end{array}$$ With this notion, for any sequence of directions $\mathbf{d}=(d_1,d_2,\dots ,d_n)$ the $(i,j)$ entry of the product matrix $A_{d_1}{A}_{d_2}\dots A_{d_n}$ is $2^p$ if the hero, following the sequence $\mathbf{d}$ and starting from town $i$, arrives in town $j$ and wins $p$ points.

Since there are no connections between towns in the two games, we have to prove that $s^{T}Af=0$ for all $A=A_{d_1}\cdots A_{d_n}$ if and only if $s^{T}Af=0$ for all $A=A_{d_1}\cdots A_{d_n}$ with $n\le N+M$.

To prove this, let $V_0=\{s\}$ and let $V_{n+1}=V_n\cup \{v^T{A}_d:v\in V_n\text{ and }d\le k\}$. Clearly, each $V_n$ spans a linear space of dimension at most $N+M$. Hence, $\dim \mathrm{span}{V}_n=\dim \mathrm{span}{V}_{n+1}$ for some $n<N+M$, and so every vector from $V_{n+1}$ is a linear combination of vectors from $V_n$. A simple inductive argument then shows that the vectors in $V_m$ are linear combinations of vectors from $V_n$ for all $m\ge n$. In particular, if the vectors in $V_n$ are all orthogonal to $f$, then so are the vectors in $V_m$ for any $m\in \mathbb{N}$.

This proves that if $L^{\prime }(1)\ne L^{\prime }(N+1)$, then $1/{\equiv }^{(n)}N+1$. Finally, we show that if $u/{\equiv }^{(n)}v$, then $L_n(u)\ne L_n(v)$. This is obvious for $n=0$ and $n=1$. Assume that the statement holds for some $n$ and all $u,v\in V$ and consider some $u/{\equiv }^{(n+1)}v$. We need to prove that $L_{n+1}(u)\ne L_{n+1}(v)$. By the inductive hypothesis we may assume that $u{\equiv }^{(n)}v$. In particular, $u{\equiv }^{(1)}v$. Therefore, ${\lambda }^{\prime }(u,d)=(u^{\prime },p)$ for all $d\le k$, and ${\lambda }^{\prime }(v,d)=(v^{\prime },q)$ implies that $p=q$. Therefore, the fact that $u{\equiv }^{(n+1)}v$ is due to some $d\le k$ such that $u^{\prime }/{\equiv }^{(n)}{v}^{\prime }$. By the inductive hypothesis $L_n^{\prime }(u^{\prime })\ne L_n^{\prime }(v^{\prime })$. It should now be clear that $L_{n+1}^{\prime }(v)\ne L_{n+1}^{\prime }(v^{\prime })$.