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

Let's make several definitions and some analysis:

: weight of the i-th batch.

: frequency (or periodicity?) of the i-th batch. (for yellow batches , for red , and so on...)

Suppose that B-th batch is the last one placed in the mancala that determined the heuristic value, . (weigth= and frequency= ). NOTE: this may be different than the last batch placed!

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 . ( is an integer between 1 and ). Because it must be placed in one of the first f_B pits.

Then, the following pits will receive the last batch:

Total: pits will receive the last batch.

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

Now the heuristic value

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

Then here is a lower-bound for the optimum ( ):

left-hand side is the heuristic value:

Another lower-boud on the optimum: , So:

Now if (last batch is purple),

then

So 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...