Wednesday, March 9, 2011

Balanced Mancala Problem

We rarely ask pure math problems but here is one with a "very little" touch of geometry. This does not need to be defined as a mancala game, but here it goes:

We have stones coming in batches. Each stone has a color and a weight. If the color of a stone is:

Yellow: It must be placed every other pit (every 2 pits) Batch size is always: 6 Total batches: y Total number = 6y

Red: Must be placed every 3 pits Batch size: 4 Total batches: r Total number = 4r

Green: Must be placed every 4 pits Batch size: 3 Total batches: g Total numbers = 3g

Blue: Must be placed every 6 pits Batch size: 2 Total batches: b Total number = 2b

Purple: Must be placed only once in 12 pits Batch size: 1 Total batches: p Total numbers = p

So there are N=6y+4r+3g+2b+p many stones. The stones in the same batch have the same weight. Different batches may have different weights. WLOG, assume that all weights are integers. We have a proof that ending up with the best well-balanced mancala is very difficult (NP-Hard). Here "well-balanced" means that the pit with the maximum weight is minimized when all stones are distributed. Let's call this maximum pit weight as W.

Consider the following heuristic process:

Step 1. Sort the batches with respect to their weights (batches with the high-weight stones go first) Step 2. Insert the first batch starting from pit number 1. Step 3. Insert the next batch in a way that the total maximum weight throughout 12 pits remains minimum. Step 4. Repeat Step 3 until all batches are placed in the mancala. Let H be the maximum weight throughout 12 pits.

A simple Example: Suppose we have only 4 batches: Yellow (6 stones, each 45 grams) Blue (2 stones, each 40 grams) Yellow (6 stones, each 30 grams) Green (3 stones, each 20 grams) First batch (Yellow) goes to pits: 1, 3, 5, 7, 9, and 11. H=45. Second batch (Blue) goes to pits: 2 and 8. H=45. Third batch (Yellow) goes to pits: 2, 4, 6, 8, 10, and 12. H=70. Fourth batch (Green) goes to pits: 3, 7, and 11. H=70.

In this exercise, heuristic actually finds the optimum, i.e., H=W=70 grams, observed in pits 2 and 8.

And the question: Prove that the worst-case of the heuristic solution, H, is always less than 2W. In other words, W ≤ H ≤ 2W always holds. If you disagree, then try to generate a counter-example.

Good luck!

1 comment:

  1. Let's make several definitions and some analysis:
    w_i: weight of the i-th batch.
    f_i: frequency (or periodicity?) of the i-th batch. (for yellow batches f_i=2, for red f_i=3, and so on...)
    Suppose that B-th batch is the last one placed in the mancala that determined the heuristic value, H. (weigth=w_B and frequency=f_B). NOTE: this may be different than the last batch placed!

    w_1 >= w_2 >= ... >= w_B is always true due to sorting. (Step 1)

    Now, suppose that the the first stone of the last batch is inserted in pit j. (j is an integer between 1 and f_B). Because it must be placed in one of the first f_B pits.

    Then, the following pits will receive the last batch: j, j+f_B, j+2f_B, ..., j+12-f_B.

    Total: 12/f_B pits will receive the last batch.

    One more definition: Let T_j be the total weight of stones "before" the last batch is placed.

    T_k = max{T_j, T_(j+f_B), T_(j+2f_B), ..., T_(j+12-f_B)}

    Now the heuristic value H = T_k + w_B.

    When the last batch is placed, there must be at least f_B many T_k's in the mancala. <-- this is important to see!

    Then here is a lower-bound for the optimum (W):
    (f_B*T_k / 12) + (w_B/f_B) <= W
    => T_k + (w_B/f_B)*(12/f_B) <= W*(12/f_B)
    => T_k + w_B <= W*(12/f_B)-(12*w_B/(f_B)^2)+w_B
    left-hand side is the heuristic value:
    => H <= (12/f_B)W + w_B *((f_B)^2 - 12)/(f_B)^2

    Another lower-boud on the optimum: W>=w_B, So:
    => H <= (12/f_B)W + W *((f_B)^2 - 12)/(f_B)^2
    => H <= [(12/f_B) + ((f_B)^2 - 12)/(f_B)^2]*W
    => H <= [1 + (12*(f_B-1)/(f_B)^2)]*W

    Now if f_B=12 (last batch is purple),
    then H <= (2 - 1/12)*W

    So W <= H <= 2W holds. But this is true only if the last batch (that determines the heuristic value) is purple. There is no guarantee that "that last batch" will be purple.

    So the proof is not complete! But this may be a starting point. Now what?

    -Polar Fox