The grasshopper problem

Abstract

We introduce and physically motivate the following problem in geometric combinatorics, originally inspired by analysing Bell inequalities. A grasshopper lands at a random point on a planar lawn of area one. It then jumps once, a fixed distance $d$, in a random direction. What shape should the lawn be to maximise the chance that the grasshopper remains on the lawn after jumping? We show that, perhaps surprisingly, a disc shaped lawn is not optimal for any $d>0$. We investigate further by introducing a spin model whose ground state corresponds to the solution of a discrete version of the grasshopper problem. Simulated annealing and parallel tempering searches are consistent with the hypothesis that for $d<{\pi }^{-1/2}$ the optimal lawn resembles a cogwheel with $n$ cogs, where the integer $n$ is close to $\pi (\arcsin (\sqrt{\pi }d/2){)}^{-1}$. We find transitions to other shapes for $d\gtrsim {\pi }^{-1/2}$.

Comments and references added. Ancillary files with simulation data included

References in corpus (1)

• The Communication Cost of Simulating Bell Correlations