The scout-number conjecture for effective exploration of integer grids

A scout process consists of cc scouts moving on Zd\mathbb{Z}^d according to a scout protocol P=c,S,x0,q0,Π\mathcal{P}=\langle c,\mathcal{S},x_0,\mathbf{q}_0,\Pi\rangle. The hitting time of xZdx\in\mathbb{Z}^d is inf{n0:i such that Xni=x}\inf\{n\geq 0:\exists i\text{ such that }X_n^i=x\}, and the protocol is effective when every grid point has finite mean hitting time. It is known that d+1d+1 scouts suffice for every d1d\geq 1.

The scout-number conjecture. For d3d\geq 3, any effective scout protocol on Zd\mathbb{Z}^d requires at least d+1d+1 scouts.

The claim extends the paper's theorem for d{1,2}d\in\{1,2\} and, together with the known sufficiency of d+1d+1 scouts, would identify the exact minimum number of scouts needed for effective exploration of Zd\mathbb{Z}^d.

Sources & referencesView supporting material

Primary source

Lihi Cohen, Yuval Emek, Oren Louidor and Jara Uitto, “Exploring an Infinite Space with Finite Memory Scouts”, arXiv:1704.02380 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.