Results 1 to 2 of 2

Thread: Balanced Mancala Problem

  1. #1
    Jan 2009

    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:
    It must be placed every other pit (every 2 pits)
    Batch size is always: 6
    Total batches: y
    Total number = 6y

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

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

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

    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.
    Follow Math Help Forum on Facebook and Google+

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

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

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

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

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

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

    $\displaystyle T_k = \max\{T_j, T_{j+f_B}, T_{j+2f_B}, \ldots, T_{j+12-f_B}\}$

    Now the heuristic value $\displaystyle H = T_k + w_B.$

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

    Then here is a lower-bound for the optimum ($\displaystyle W$):
    $\displaystyle (f_B T_k / 12) + (w_B/f_B) \leq W$
    $\displaystyle \implies T_k + (w_B/f_B)(12/f_B) \leq W(12/f_B)$
    $\displaystyle \implies T_k + w_B \leq W(12/f_B)-(12w_B/(f_B)^2)+w_B$
    left-hand side is the heuristic value:
    $\displaystyle \implies H \leq (12/f_B)W + w_B ((f_B)^2 - 12)/(f_B)^2$

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

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

    So $\displaystyle 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?
    Last edited by oswaldo; Mar 17th 2011 at 10:04 PM. Reason: Latex corrections
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Balanced Strings
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Aug 20th 2011, 06:31 PM
  2. [SOLVED] Two balanced fair coins
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Mar 15th 2011, 08:40 AM
  3. Balanced and absorbant sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Mar 10th 2011, 12:06 AM
  4. balanced incomplete block designs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2010, 01:48 PM
  5. Repeated Tossing of Balanced Die
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Nov 8th 2009, 04:39 AM

Search Tags

/mathhelpforum @mathhelpforum