Personal tools
User menu

Puzzle 1

From Thalesians

Jump to: navigation, search

Masses and Buckets

You have M masses,  m_1, m_2, \ldots, m_M which you want to distribute across N buckets "as uniformly as possible". By this I mean that you are trying to minimise  \sum_{i=1}^N \sum_{j=i}^N (b_i - b_j)^2 , where bk 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 b1 and b2 are unequal. Since all weights are integers, the difference must be at least 1, i.e.  (b_1 - b_2)^2 \geq 1 . Now take b3. In the best case, it can be equal to b1 or b2, but not both, so the total of the two differences will be at least 2, i.e.  (b_3 - b_1)^2 + (b_3 - b_2)^2 \geq 3 . Finally, summing up all the inequalities we get

 O = \sum_{i < j} (b_i - b_j)^2 \geq 3 .

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:

  1. Sort mi so that m1 is the largest and mM is the smallest.
  2. For  i = 1, \ldots, M :
    1. Find the "lightest" bucket;
    2. Put mi in that bucket.
  3. 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!

  • This page was last modified on 25 June 2009, at 09:19.
  • This page has been accessed 9,156 times.