Treasure hunt

Ayoubi, Mans and Narayanan make the problem solvable with two restrictions. In the class VP(\(\xi\)) (their VP(\(\delta\)); their \(\delta\) is \(\xi\) here) every two nodes are adjacent in at least one step of each window of \(\xi\) consecutive steps; the class is non-empty if and only if \(\xi\ge\lceil (n-1)/2\rceil\) (Proposition 1, through Walecki's decomposition of the complete graph into Hamiltonian cycles). With flags, a memoryless agent that moves to an unflagged neighbour whenever it sees one finds the treasure within \(\xi(n-1)\) steps (Theorem 2), and for \(\xi\ge 2n\) every deterministic agent needs \(\xi(n-3)\) steps on some input, even with memory, chirality, a view of the whole snapshot and knowledge of the node labels (Theorem 3); without node labels its competitive ratio is \(\Omega(\xi n)\) (Theorem 4). Without flags and without node labels, no deterministic agent succeeds for \(\xi\ge n\), even with memory, chirality and a view of the whole snapshot (Theorem 5), while a randomized agent that stays put with probability \(1-1/\xi\) finds the treasure in expected \(O(\xi^2)\) steps (Theorem 6), even without knowing \(n\) or \(\xi\) (Remark 1). With \(k\) agents, flags, and access to each port by mutual exclusion, \(\xi\lceil 2n/k\rceil\) steps suffice for \(\xi\ge\lceil (n-1)/2\rceil\) (Theorem 8), and \((\lceil (n-2)/k\rceil-2)\,\xi\) steps are necessary for \(1\le k\le n/2-2\) and \(\xi\ge (k+1)(n-k-2)\) (Theorem 9). If each snapshot is a ring in a uniformly random order (R-VP), an agent that always moves to its clockwise neighbour finds the treasure in expected \(\Theta(n)\) steps when the treasure is placed in advance, and \(\Theta(n\log n)\) when an adversary that knows the sequence of snapshots places it (Theorem 7). These results need flags, the window \(\xi\) or random snapshots, which the axes do not record, so they are described here rather than listed as bounds. Checked against the full text (preprint, v1).