Polynomial-move conjecture for enlarging regular polygons in the grasshopper game
Polynomial-move conjecture for enlarging regular polygons in the grasshopper game
Let and consider a configuration of grasshoppers at the vertices of a regular -gon, with legal moves given by the grasshopper-jumping game described in the paper. Polynomial-move conjecture. Every regular -gon can be transformed to a similar but larger configuration in polynomially many moves in . The main theorem establishes that a finite sequence of moves always exists, while the conjecture asks for a polynomial bound; the explicit bound obtained from the proof is unreasonably large and may be exponential.
Sources & referencesView supporting material
Primary source
János Pach and Gábor Tardos, “Where have all the grasshoppers gone?”, arXiv:2211.03870 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.