Ponder This Challenge - July 1998 - Tennis balls in a bucket

Ponder This Challenge:

Wimbledon has just ended, and your job is to store the remaining tennis balls in buckets. The storage area will only hold rows of three buckets, but will hold an undetermined number of rows. You must follow three inviolable rules in storing the tennis balls:

Each bucket must have a different positive number of balls. Each row must have the same total number of balls in its three buckets. The total number of balls in each row is as small as possible.

For example, if you were given only two rows of buckets, the setup:

achieves a row total of 11. This is the best possible arrangement for two rows.
Problem: Can you give a construction that gives an optimal arrangement that works for an arbitrary number k of rows?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  At first glance, this problem seems easy enough to solve. Getting a unique number of balls in each bucket AND making the row totals match can be solved easily enough by rather simple equations. For instance, one proposed solution:

  In row number r, bucket one has r balls, bucket two has k+r balls, and bucket three has 2k+2(k-r)+1 balls.

  However, these approaches fail to meet all three conditions. The real challenge--and the thing that tripped up most of our respondents--is the third "inviolable" condition: that total number of balls in each row must be the smallest possible.

  To do this, we must find a way to utilize all the integers from 1 to 3*k. If k is odd, we can accomplish this. If k is even, we must skip one integer. Therefore two constructions comprise the solution, one for k odd, and a second for k even.

  First, let's consider the case when k is odd. k=2m+1 Then the integers 1 through 3k = 6m + 3 have the sum (6m + 3) * (6m + 4) / 2 , according to Gauss's famous result.

  Click here to find out more about this approach to finding the sum of consecutive integers. Therefore, we should be able to find an arrangement where each of k (or 2m + 1) rows has sum 9m + 6 , because [(6m + 3) * (6m + 4) / 2] / (2m + 1) = 9m + 6 (or the sum of the integers from 1 to 3*k divided by k, the number of rows). We can't do any better, since any other choice of 6m + 3 distinct positive integers has a larger sum. The following construction achieves this optimum:

  1	4 m + 2	5 m + 3
  2	4 m + 0	5 m + 4
  3	4 m - 2	5 m + 5
  	...
  m	2 m + 4	6 m + 2
  m + 1	2 m + 2	6 m + 3

  m + 2	4 m + 1	4 m + 3
  m + 3	4 m - 1	4 m + 4
  m + 4	4 m - 3	4 m + 5
  	...
  2m	2 m + 5	5 m + 1
  2m + 1	2 m + 3	5 m + 2

  As example of the solution for odd k. Suppose k=7 so that m=3.

  1	14	18
  2	12	19
  3	10	20
  4	8	21
  5	13	15
  6	11	16
  7	9	17

  Note that the left hand buckets handle the integers from 1 to k ( or 2m + 1). For the first m + 1 rows, the right hand buckets contain the integers from 5m + 3 to 6m + 3, and the middle buckets contain the even integers from 2m + 2 to 4m + 2. In the last m rows, the right hand buckets contain the integers from 4m + 3 to 5m + 2, while the middle buckets contain the odd integers from 2m + 3 to 4m + 1. So all the integers are covered, and each row has a total of 6m + 3. In case k is even, a new wrinkle arises. Copying the previous construction, we get: k=2m [(6m) * (6m + 3) / 2] / 2m = 9m + (3/2), which is not an integer. So the best we can hope for is the next largest integer, 9m + 2. We use the integers 1,2,3 ..., 5m, 5m + 2, 5m + 3, ... 6m + 1, and omit 5m + 1. An arrangement that achieves the optimum is:

  1	4m - 1	5m + 2
  2	4m - 3	5m + 3
  3	4m - 5	5m + 4
  	...
  m	2m + 1	6m + 1

  m + 1	4m	4m + 1
  m + 2	4m - 2	4m + 2
  m + 3	4m - 4	4m + 3
  	...
  2m	2m + 2	5m

  An example for k even, where k = 8, so that m = 4.

  1	15	22
  2	13	23
  3	11	24
  4	9	25
  5	16	17
  6	14	18
  7	12	19
  8	10	20

  This gives an optimal row sum of 9m + 2 = 38. The first m = 4 rows follow one pattern and the last m = 4 follow another..

  Although it is contended that the solution for finding the sum of consecutive integers has ancient roots, perhaps stretching back to Pythagorus, it is the story of Gauss's school age experience that has become legend.

  As the story goes, Gauss's teacher tried to occupy the class during an unsupervised absence by proposing a simple problem: Find the sum of all integers from 1 to 100.

  As his classmates laboriously -- and quietly, one hopes -- proceeded to work the solution by rote addition, Gauss reasoned the problem as follows:

  He imagined adding, not the consecutive integers, but two series of addition, the integers progressing forward in one series and in reverse in the other.

  1 + 2 + 3 + 4 ........ + 98 + 99 +100

  • 100+ 99 +98+97........ + 3 + 2 + 1
    ______________________________________
    Sum 101 + 101 + 101 + 101 + 101 + 101 + 101 (i.e., 101 + 101...one hundred times)

  He concluded that the sum of the two series was the product of the largest integer in the series and that integer plus 1 : (x) * (x +1)

  The sum of the integers in a consecutive series, then, would be (x) * (x +1)/2

  The reaction of Gauss's classmates -- and his teacher -- to his shortcut remains a mystery. Fortunately, his result has been preserved.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers