The grasshopper problem

• Published in 2017
• Added on 2018-01-24

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}$.

Links

• http://arxiv.org/abs/1705.07621v3
• http://arxiv.org/pdf/1705.07621v3

Other information

BibTeX entry

@article{Thegrasshopperproblem,
	key = {Thegrasshopperproblem},
	type = {article},
	title = {The grasshopper problem},
	author = {Olga Goulko and Adrian Kent},
	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{\}}{\$}.},
	comment = {},
	date_added = {2018-01-24},
	date_published = {2017-04-10},
	urls = {http://arxiv.org/abs/1705.07621v3,http://arxiv.org/pdf/1705.07621v3},
	collections = {Animals,Probability and statistics,Puzzles,Geometry},
	url = {http://arxiv.org/abs/1705.07621v3 http://arxiv.org/pdf/1705.07621v3},
	year = 2017,
	urldate = {2018-01-24},
	archivePrefix = {arXiv},
	eprint = {1705.07621},
	primaryClass = {cond-mat.stat-mech}
}