|
|
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. |
|
Subject:
Re: Partitioning marbles into boxes
Answered By: efn-ga on 27 Nov 2005 10:55 PST Rated: |
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: |
|
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. |
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 Home - Answers FAQ - Terms of Service - Privacy Policy |