On the Grasshopper Problem with Signed Jumps

DOI10.4169/AMER.MATH.MONTHLY.118.10.877zbMATH Open1268.05032arXiv1008.2936OpenAlexW2963661647MaRDI QIDQ3106506

Publication date: 28 December 2011

Published in: The American Mathematical Monthly (Search for Journal in Brave)

Abstract: The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, was the following. Let

a_{1}, a_{2}, . . ., a_{n}

be distinct positive integers and let

M

be a set of

n - 1

positive integers not containing

s = a_{1} + a_{2} + . . . + a_{n}

. A grasshopper is to jump along the real axis, starting at the point 0 and making

n

jumps to the right with lengths

a_{1}, a_{2}, . . ., a_{n}

in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in

M

. The problem was discussed in many on-line forums, as well by communities of students as by senior mathematicians. Though there have been attempts to solve the problem using Noga Alon's famous Combinatorial Nullstellensatz, up to now all known solutions to the IMO problem are elementary and inductive. In this paper we show that if the condition that the numbers

a_{1}, . . . a_{n}

are positive is omitted, it allows us to apply the polynomial method to solve the modified problem.

Full work available at URL: https://arxiv.org/abs/1008.2936

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorics (educational aspects) (97K20)

This page was built for publication: On the Grasshopper Problem with Signed Jumps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3106506)