# Puzzle 1

## Masses and Buckets

You have *M* masses, which you want to distribute across *N* buckets "as uniformly as possible". By this I mean that you are trying to minimise , where *b*_{k} is the sum of the masses in the *k*-th bucket. How would you achieve this?

To make this a little bit more concrete, suppose that I give you 20 masses, e.g. 23, 43, 12, 54, 7, 3, 5, 10, 54, 55, 26, 9, 9, 43, 54, 1, 8, 6, 38, 33. There are 4 buckets. How would you distribute the masses?

Please send your answers to `paul`, who happens to be at `bilokon.co.uk`.

### Solution

**2009-06-05.** We are pleased to let you know that **the problem remains essentially open** (and we will explain why in a moment). However, the Thalesians have made a lot of progress!

First, the special case with the masses 23, 43, 12, 54, 7, 3, 5, 10, 54, 55, 26, 9, 9, 43, 54, 1, 8, 6, 38, 33 has been solved by **Adrian Zymolka of Axioma (UK) Ltd.**, who is also our next presenter, and **Cody Ebberson**. (Congratulations!)

An optimal solution is:

- Bucket 1 (total mass = 123): 3, 7, 26, 33, 54
- Bucket 2 (total mass = 123): 5, 9, 12, 43, 54
- Bucket 3 (total mass = 123): 1, 6, 8, 10, 43, 55
- Bucket 4 (total mass = 124): 9, 23, 38, 54

**Adrian Zymolka** has presented a proof of the optimality of this solution.

Sum up all the wrights in the example. The result is 493 or the average of 123.25 per basket. This means that there cannot be a solution where all the baskets have equal mass (and thus no solution with *O* = 0 can exist). So there must be unequal baskets in terms of mass. Without loss of generality, assume *b*_{1} and *b*_{2} are unequal. Since all weights are integers, the difference must be at least 1, i.e. . Now take *b*_{3}. In the best case, it can be equal to *b*_{1} or *b*_{2}, but not both, so the total of the two differences will be at least 2, i.e. . Finally, summing up all the inequalities we get

.

Thus if you find a feasible solution with this objective value, this lower bound proves its optimality. **Q.E.D.**

**Cody Ebberson** has also sent us a Java program that finds the optimal solution:

package org.ebberson.puzzles; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class PuzzleSolver { private final List<Integer> values; private final List<List<Integer>> buckets; /** * Creates the puzzle solver. * * @param values array of initial values * @param bucketCount number of buckets in the games */ public PuzzleSolver(int[] values, int bucketCount) { this.values = new ArrayList<Integer>(values.length); this.buckets = new ArrayList<List<Integer>>(bucketCount); for (int i = 0; i < values.length; i++) { this.values.add(values[i]); } for (int i = 0; i < bucketCount; i++) { this.buckets.add(new ArrayList<Integer>()); } bestGuess(); optimize(); printResults(); } /** * Initializes the buckets with a 'best guess'. * * In descending order, adds a value to the bucket with the lowest sum. */ private void bestGuess() { Collections.sort(values); Collections.reverse(values); for (Integer i : values) { getLowestBucket().add(i); } } /** * Optimizes the distribution by looking at pairs of numbers that * can be swapped to improve the total score. */ private void optimize() { for (List<Integer> bucket : buckets) { Collections.sort(bucket); } for (int i = 0; i < buckets.size() - 1; i++) { for (int j = i + 1; j < buckets.size(); j++) { optimize(buckets.get(i), buckets.get(j)); } } } /** * Optimizes the distribution by looking at pairs of numbers that * can be swapped to improve the total score. * * @param bucket1 * @param bucket2 */ private void optimize(List<Integer> bucket1, List<Integer> bucket2) { long bestScore = score(); for (int i1 = 0; i1 < bucket1.size(); i1++) { for (int i2 = 0; i2 < bucket2.size(); i2++) { swap(bucket1, i1, bucket2, i2); if (score() > bestScore) { swap(bucket1, i1, bucket2, i2); } } } } /** * Swaps values from two different buckets. * * @param bucket1 * @param index1 * @param bucket2 * @param index2 */ private void swap(List<Integer> bucket1, int index1, List<Integer> bucket2, int index2) { int temp = bucket1.get(index1); bucket1.set(index1, bucket2.get(index2)); bucket2.set(index2, temp); } /** * Returns the bucket with the lowest current sum. * * @return */ private List<Integer> getLowestBucket() { List<Integer> lowestBucket = null; int lowestSum = Integer.MAX_VALUE; for (List<Integer> bucket : buckets) { int sum = sum(bucket); if (sum < lowestSum) { lowestBucket = bucket; lowestSum = sum; } } return lowestBucket; } /** * Calculates the sum of a bucket. * * @param bucket * @return */ private int sum(List<Integer> bucket) { int sum = 0; for (Integer i : bucket) { sum += i; } return sum; } /** * Calculates the total score. * * @return */ private long score() { int n = buckets.size(); int[] temp = new int[n]; for (int i = 0; i < n; i++) { temp[i] = sum(buckets.get(i)); } long sum = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int delta = temp[i] - temp[j]; sum += delta * delta; } } return sum; } /** * Prints the results. */ private void printResults() { System.out.println("Final score: " + score()); int i = 1; for (List<Integer> bucket : buckets) { System.out.print("Bucket " + i + " (" + sum(bucket) + "): "); Collections.sort(bucket); print(bucket); System.out.println(); i++; } } /** * Prints list of integers with proper comma usage. * * @param bucket */ private void print(List<Integer> bucket) { boolean first = true; for (Integer i : bucket) { if (!first) { System.out.print(", "); } System.out.print(i); first = false; } } public static void main(String[] args) { int[] values = { 23, 43, 12, 54, 7, 3, 5, 10, 54, 55, 26, 9, 9, 43, 54, 1, 8, 6, 38, 33 }; int bucketCount = 4; new PuzzleSolver(values, bucketCount); } }

Now let us consider the general case. The Thalesians **Cody Ebberson**, **Maziar Motahari of MathWorks** and **Pieter van Zwol** agree that the following procedure should be used to find the optimal solution in the general case:

- Sort
*m*_{i}so that*m*_{1}is the largest and*m*_{M}is the smallest. - For :
- Find the "lightest" bucket;
- Put
*m*_{i}in that bucket.

- Use greedy optimisation to search for opportunities to swap two masses that improve the total score.

(**Cody Ebberson** has produced the complete solution, including the greedy optimisation step; **Maziar Motahari** and **Pieter van Zwol** both gave the sorted initial guess. Congratulations!)

**However, no-one has shown that this procedure is in some sense optimal, nor has anyone demonstrated the optimality of the initial guess — masses sorted in descending order.**

Therefore we look forward to hearing from you!