July 1998
| 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 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: | ||||||||||||||||||||||||
| ||||||||||||||||||||||||
| ||||||||||||||||||||||||
As example of the solution for odd k. Suppose k=7 so that m=3.
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: | ||||||||||||||||||||||||
| ||||||||||||||||||||||||
| ||||||||||||||||||||||||
An example for k even, where k = 8, so that m = 4.
|
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