# Math Help - Balanced Mancala Problem

1. ## Balanced Mancala Problem

The problem statement is very long. 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.

I will give my work in the first comment, because the above text is already too long.

2. And here is my work (which is NOT complete!)

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 \geq w_2 \geq ... \geq w_B$ is always true due to sorting. (Step 1 of the heuristic)

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, \ldots, 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 in pit $j$ "before" the last batch is placed.

$T_k = \max\{T_j, T_{j+f_B}, T_{j+2f_B}, \ldots, 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) \leq W$
$\implies T_k + (w_B/f_B)(12/f_B) \leq W(12/f_B)$
$\implies T_k + w_B \leq W(12/f_B)-(12w_B/(f_B)^2)+w_B$
left-hand side is the heuristic value:
$\implies H \leq (12/f_B)W + w_B ((f_B)^2 - 12)/(f_B)^2$

Another lower-boud on the optimum: $W \geq w_B$, So:
$\implies H \leq (12/f_B)W + W ((f_B)^2 - 12)/(f_B)^2$
$\implies H \leq [(12/f_B) + ((f_B)^2 - 12)/(f_B)^2] W$
$\implies H \leq [1 + (12(f_B-1)/(f_B)^2)] W$

Now if $f_B=12$ (last batch is purple),
then $H \leq (2 - 1/12) W$

So $W \leq H \leq 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?
Thanks...