Google Answers Logo
View Question
 
Q: Partitioning marbles into boxes ( Answered 5 out of 5 stars,   2 Comments )
Question  
Subject: Partitioning marbles into boxes
Category: Science > Math
Asked by: gw-ga
List Price: $10.00
Posted: 26 Nov 2005 22:27 PST
Expires: 26 Dec 2005 22:27 PST
Question ID: 597988
This question is not a homework question.  It is part of a real
problem that I abstracted to communicate more simply.

Suppose we have eight sealed opaque boxes arranged in a cube.

We are told that the boxes contain 100 marbles such that:

The four boxes comprising the top half contain a total of 70 marbles.
The four boxes comprising the left half contain a total of 65 marbles.
The four boxes comprising the front half contain a total of 40 marbles.

(Obviously the bottom half must contain 30, the right half 35, the back half 60)

Is it possible to easily determine how many marbles are in each of the eight boxes?

I believe the unique solution is

     TOP HALF       BOTTOM HALF
    +----+----+     +----+----+
    | 29 | 13 |     | 10 |  8 |
    +----+----+     +----+----+
    | 20 |  8 |     |  6 |  6 |
    +----+----+     +----+----+

What I'm really looking for is a general solution, given three
arbitrary partitionings X, Y, and Z instead of 70, 65, and 60.
Answer  
Subject: Re: Partitioning marbles into boxes
Answered By: efn-ga on 27 Nov 2005 10:55 PST
Rated:5 out of 5 stars
 
Hi gw,

In most cases, there will be more than one solution.

For example, consider just two dimensions, top/bottom and left/right. 
With the constraints in your example, there are 31 solutions ranging
from

+----+----+
| 65 |  5 |
+----+----+
|  0 | 30 |
+----+----+

(front view)

to

+----+----+
| 35 | 35 |
+----+----+
| 30 |  0 |
+----+----+

That is, you can start with the top layout and repeat 30 times an
operation where you move one marble from the lower right to the lower
left and move one from the upper left to the upper right.

For each of these 31 layouts, there are many ways to divide the
marbles in the boxes in the two-dimensional layout between front and
back so that there are 40 marbles in the front.

Here's a general way to find a solution.

Let X be the number required in the top half, Y the number required in
the left half, and Z the number required in the front half.  Let N be
the total number of marbles.

As in the analysis above, we can find a solution by conceptually
putting marbles in boxes and then moving them around to satisfy the
constraints.

Start with N marbles in the bottom right back box.  I'm maintaining
your assumption that the front is at the bottom of the diagram.

TOP HALF        BOTTOM HALF
+----+----+     +----+----+
|  0 |  0 |     |  0 |  N |
+----+----+     +----+----+
|  0 |  0 |     |  0 |  0 |
+----+----+     +----+----+

At this point no constraint is satisfied.  To satisfy the first
constraint, move X marbles upstairs.

TOP HALF        BOTTOM HALF
+----+----+     +----+-----+
|  0 |  X |     |  0 | N-X |
+----+----+     +----+-----+
|  0 |  0 |     |  0 |  0  |
+----+----+     +----+-----+

Now as long as we don't move any marbles in the vertical direction,
the first constraint will always be satisfied.

Now to satisfy the second constraint, move Y marbles from the back
right column to the back left column.  Unfortunately, I can't show a
general diagram of the result any more, because depending on the
relative sizes of X and Y, it may be possible or necessary to move
marbles from the top or the bottom or both.  But because there are N
marbles in the back right column, it must be possible to move Y of
them to the left.

After this operation, the first two constraints are satisfied.  There
are still X marbles on the top and N-X on the bottom, because the
second move did not move any up or down, and there are Y marbles on
the left because we just put them there.

Similarly, select any Z marbles and move them to the front.  This
satisfies the third constraint without violating either of the first
two.

This procedure will always find a solution, usually one of many
possible, but if there is only one (say X = Y = Z = 0), it will find
it.

I applied this procedure to your problem with a preference rule of
moving marbles from the box with the most marbles and got this
solution:

TOP HALF        BOTTOM HALF
+----+----+     +----+----+
| 25 |  5 |     |  0 | 30 |
+----+----+     +----+----+
| 40 |  0 |     |  0 |  0 |
+----+----+     +----+----+


I hope this explanation is helpful.  If it is not clear enough, please
ask for a clarification and I will try to improve it.

--efn
gw-ga rated this answer:5 out of 5 stars

Comments  
Subject: Re: Partitioning marbles into boxes
From: deeknow-ga on 27 Nov 2005 02:18 PST
 
If you ignore the boxes and their relative positions in 3
dimensions... what you have here is a system of simultaneous linear
equations.

     TOP HALF       BOTTOM HALF
    +----+----+     +----+----+
    | X1 | X2 |     | X5 | X6 |
    +----+----+     +----+----+
    | X3 | X4 |     | X7 | X8 |
    +----+----+     +----+----+

So we have 8 variables (unknowns)... X1 to X8
and we have 6 equations (defined relationships between these unknowns)

I could write these down as...

X1 + X2 + X3 + X4 = 70 (the top layer)
X5 + X6 + X7 + X8 = 30
X1 + X3 + X5 + X7 = 65 (the left half)
X2 + X4 + X6 + X8 = 35
X3 + X4 + X7 + X8 = 40 (the front half)
X1 + X2 + X5 + X6 = 60

what you end up with is 6 simultaneous equations in 8 variables

mathematically, you cannot have a unique solution for this system
(I believe you will need to provide 8 equations if you are looking for
a unique solution to 8 variables, but I could be wrong on that)

for example, the following 2 trivial solutions also fit the bill...

Solution 1

     TOP HALF       BOTTOM HALF
    +----+----+     +----+----+
    | 25 |  5 |     |  0 | 30 |
    +----+----+     +----+----+
    | 40 |  0 |     |  0 |  0 |
    +----+----+     +----+----+

Solution 2

     TOP HALF       BOTTOM HALF
    +----+----+     +----+----+
    |  0 | 30 |     | 30 |  0 |
    +----+----+     +----+----+
    | 35 |  5 |     |  0 |  0 |
    +----+----+     +----+----+

there should be many more ...

There are many resources on the web if you want to read up on this subject.
Google for Simultaneous Linear Equations, and a flood of sites opens up.

There are even solvers available online... try the following: it will
let you solve upto 10 equations in variables

http://home.ubalt.edu/ntsbarsh/Business-stat/otherapplets/SysEq.htm

Hope this helps
Subject: Re: Partitioning marbles into boxes
From: manuka-ga on 27 Nov 2005 21:43 PST
 
Just a quick note on deeknow's comment... in fact you only have *four*
(independent) equations. This should be obvious, since the second,
fourth and sixth equations deeknow gives are all derived by combining
the preceding equation with the one that say the total is 100.

One does generally require 8 independent linear equations to solve for
8 unknowns, but where there are restrictions (such as requiring
integer values, i.e. Diophantine equations) fewer equations may be
required for particular cases. Fewer equations can also (sometimes)
work if the equations are non-linear.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy