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 areN=6y+4r+3g+2b+pmany 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 asW.

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. LetHbe 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 than2W.

In other words,W ≤ H ≤ 2Walways 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.