Ping-Pong and the Traveling Salesman Problem
Emmanuel Tsukerman · Experimental Mathematics · 2015
Racquetball, tennis, and table tennis players know well the tedious task of retrieving the ball. We consider in this article the question whether one can reduce the amount of effort spent retrieving the ball by playing with more balls than one, and if so, by how much. We model the problem as a question about the traveling salesman problem in 2-dimensional Euclidean space with a stochastic aspect. We show that two balls are better than one in the sense that on average, one travels a smaller distance to retrieve the two balls. Continuing this line of thought, we conjecture that having n + 1 balls is better than n balls. In the direction of this conjecture, to be referred to as the “ping-pong conjecture,” we show that n′ balls are better than n balls, for n∣n′, that the ping-pong conjecture holds when the balls are not likely to land far from one another, and that it holds in the 1-dimensional case with the balls landing on one side of the origin almost surely.