The Grabbing Cubes Problem Mike Beeler March 2016 ----- Contents Abstract Background -- problem statement Background -- interpretation Background -- published answer Background -- auxiliary questions Background -- the challenge Terminology Investigation by random play Box sizes run via Monte Carlo Degenerate box sizes The base diagram and observations Monte Carlo results Equivalence to 3-D torus Variation -- Getting Cubes Other variations on Grabbing Cubes Conclusion References Acknowledgements ----- Abstract A game of emptying a box by removing certain patters of cubes, is examined. A test is found that identifies box sizes whose games have maximal length. The game length for other box sizes is discussed. The discussion includes how the investigation led to development of the test. ----- Background -- problem statement The Mathematical Association of America (MAA) publishes the "Math Horizons" magazine for students, teachers, and enthusiasts. "Playground" is a department in the magazine, edited by Gary Gordon, where interesting problems are presented and answered. The September 2015 issue presented "Problem 327". The following description paraphrases that in Playground. A rectangular, 5 by 13 by 31 box is filled with unit cubes. Each move consists of choosing a cube and removing that cube and any cubes along the three lines through that cube parallel to the box edges. On each move, the choice is restricted to the cube(s) with maximal yield. The game ends when all cubes are removed. Question: How many steps does the game last? ----- Background -- interpretation The largest ambiguity is how to break the tie when more than one cube has maximal yield. Another uncertainty that might occur to a reader is whether all the cubes to be removed must be contiguous. The problem statement is clear that any and all cubes along the three lines, whether or not they are interrupted by vacant cells, are removed. The problem statement suggests a physical box and cubes. In that case, any cube removed below the topmost cubes would cause the cubes above it to fall down by gravity, filling the cell where the cube was removed. If this were intended, the problem would probably say so. We assume cubes stay in place until actively removed. ----- Background -- published answer The answer, game length is 65 moves, was published in the February 2016 issue. ----- Background -- auxiliary questions Besides game length, the problem asked two more questions. The first is that Alice and Bob alternate taking the cubes, Alice first. How many cubes does each player have when the game ends? Responders differed in the answer to this. The answer depends on how ties are broken among maximal-yield cubes. The third problem noted that the box volume is the publication year, 2015, and asked what the next year is that is the product of three distinct odd primes. It is 2035. ----- Background -- the challenge In an email on 3/10/2016, James Propp expressed dissatisfaction with the published answer, challenging whether it proves that EVERY way of playing the game ends in 65 moves. ----- Terminology Following James Propp's initial email, we call this game "Grabbing Cubes". The Math Horizon articles did not give it a name. We use "move", "step", and "pass" interchangeably. We call the shape of removed cubes -- the chosen cube and the cells, filled or vacant, along the 3 lines through it -- a "3Drook". We use p1, p2 and p3 to mean the three distinct odd primes that are the dimensions of the box. p1 < p2 < p3. We use n1, n2 and n3 to mean the three dimensions of a box of cubes on which the game is played, but that are not necessarily distinct, and/or odd, and/or prime. However, n1 <= n2 <= n3. We use x, y and z as the axes of coordinates of cells in the box. p1 and n1 are on the x axis, p2 and n2 on the y axiz, and p3 and n3 on the z axis. We use "shortcut" to mean a way to play a game in less than n1*n2 moves. "Tall" box, "short" box, and "base diagram" are defined in the discussion. ----- Investigation by random play Most steps of the game have several cubes with maximal yield, so a full exploration of all possible games with the 5x13x31 box is impractical. Instead, a Monte Carlo approach is used, in which many games are played, and a random choice is made whenever there are more than one cube with maximal yield. This was done on a variety of box sizes. It was found that some box sizes always had the same game length, while others had two or more game lengths. In most cases, 1000 games were played for each box size, although more were played on a few sizes. When more than one game length was seen, this was quickly apparent; different lengths were seen after only a few games, often just 2 games. Thus, the confidence in classifying a box size as constant or varying game length, is fairly high. The confidence in identifying the full range of possible game lengths decreases as the range grows; boxes with many possible game lengths seem to have distributions with thin tails. Most of the boxes with constant game lengths had games lasting n1*n2 moves -- the product of the two smaller dimensions of the box. All other boxes had constant game lengths less than n1*n2, or varying game lengths that never exceeded n1*n2. It seems that these other box sizes are amenable to a "shortcut" mechanism, by which the game can be shortened below the n1*n2 that many boxes require. ----- Box sizes run via Monte Carlo Computer runs were made on certain ranges of box size, with random choice whenever more than one cube had maximal yield. In these runs, 1000 games were played with each box size. Some smaller runs were performed on specific box sizes, often using more than 1000 games. The main runs were: Computer run A. All non-trivial small box sizes. 2 <= n1 <= n2 <= n3 <= 16 1000 games per box size total of 680 box sizes Computer run B. Boxes that are 2 x N x N, extending the range of n1=2 cases in run A. 2 = n1 <= n2 = n3 <= 100 1000 games per box size total of 99 box sizes Computer run C. Boxes with distinct odd prime dimensions, such as the original problem (5 x 13 x 31). 2 < p1 < p2 < p3 < 32 1000 games per box size total of 120 box sizes Computer run D. Boxes with distinct odd prime dimensions, the least dimension being 3, extending the ramge of p1=3 cases in run C. 3 = p1 < p2 < p3 < 98 total of 253 box sizes ----- Degenerate box sizes Boxes with n1 = 0 are undefined (or have game length 0). Boxes with n1 = 1 have game length n2. ----- The base diagram and observations Allowing possibly duplicated, not necessariy odd, not necessarily prime, dimensions of the box, the two smallest boxes with varying game length are 3x4x4 and 3x4x5. Let's skip 3x4x4 to preserve at least the original rule that all dimensions are distinct. And 3x4x5 is only a little bigger anyhow. Playing 10^6 games with random tie breaking among maximal yield options, about 1/9 of them have length 12, and the rest have length 11. An example of length 11 is given below. The first move is always x,y,z = 0,0,0 because all moves are equivalent in a full box. For 3x4x5: pass 1: take @ 0 0 0, removes 10, alice 10 bob 0, 0 options pass 2: take @ 2 1 2, removes 10, alice 10 bob 10, 24 options pass 3: take @ 1 2 4, removes 10, alice 20 bob 10, 6 options pass 4: take @ 0 3 3, removes 8, alice 20 bob 18, 6 options pass 5: take @ 2 0 1, removes 6, alice 26 bob 18, 6 options pass 6: take @ 1 1 1, removes 5, alice 26 bob 23, 2 options pass 7: take @ 2 3 0, removes 4, alice 30 bob 23, 1 options pass 8: take @ 1 0 2, removes 3, alice 30 bob 26, 1 options pass 9: take @ 0 2 1, removes 2, alice 32 bob 26, 2 options pass 10: take @ 0 1 4, removes 1, alice 32 bob 27, 2 options pass 11: take @ 2 2 3, removes 1, alice 33 bob 27, 1 options Stand the box on one of its smallest sides, here a 3x4 side. Diagram the base, x along the n1=3 dimension and y along the n2=4 dimension. y| 3| 2| 1| 0| +------------ 0 1 2 x In each of the 12 cells, put the z value of a cube with those x and y, chosen on some pass in the game above. y 3| 3 - 0 2| 1 4 3 1| 4 1 2 0| 0 2 1 +------------ 0 1 2 x Because this game lasted only 11 passes, one of the cells is vacant, here x,y = 1,3. In cells that are not vacant, only one z value can occur. That is because the column of cubes (in a full box) resting on that cell is removed on some pass, and, once removed, no position in that column can be a candidate to be chosen on later passes. Observation 1: The game length on a box of any dimensions is upper bounded by the product of the two smaller dimensions, n1*n2. A "3Drook", the shape comprised of a chosen cube and all the cells it can remove, has volume n1 + n2 + n3 - 2. By the end of the game, all n3=5 cells in the column resting on 1,3 must be removed. For that to occur, some 3Drooks in other columns must hit those cells. The only columns that can affect the 1,3 column are the n1-1 colums with y=3, and the n2-1 columns with x=1. So we must have n1 + n2 - 2 >= n3 for any cell(s) in the base diagram to possibly be vacant, thus for the game to possiblly have varying length. Observation 2: If n1 + n2 - 2 < n3 the game length is constant and is n1*n2. Call these boxes "tall". Observation 3: If n1 + n2 - 2 >= n3 the game length may be less than n1*n2. Call these boxes "short". The Monte Carlo results show that some box sizes have game lengths less than n1*n2, so we predict that all "short" boxes have varying game length. ----- Monte Carlo results All "tall" box sizes investigated by Monte Carlo play showed constant game length, n1*n2, as expected. For "short" boxes, Monte Carlo play generally agrees with the above prediction that the game length varies, with exceptions. Some exceptions are individual box sizes, and other exceptions are a series of box sizes. Below, we list all exceptions seen in the Monte Carlo results. A word of caution: there could be more exception cases, beyond the range examined by Monte Carlo. Also, the Monte Carlo results could be incomplete; there could be game lengths that the 1000 games per box size did not happen to see. Especially, the execption cases could have varying game length. But the chance of that seems very small. Exception 1 -- 2 x N x N. When the smallest dimension is 2 and the other two dimensions are equal, the test predicts a varying game length. However, the Monte Carlo results saw only a constant game length for each such box studied. Christoph Pacher observed that these game lengths for n2=n3 <= 16 follow a pattern related to n2 mod 4, and suggested that larger size boxes be studied to see whether the pattern holds. That led to the computer run B, which extended the pattern to n2=n3 <= 100. For the 99 box sizes 2 = n1 <= n2 = n3 <= 100, all games had a length given by: if n2 = 0 mod 4, game length is 2 * n2 if n2 = 1 mod 4, game length is 2 * n2 - 1 if n2 = 2 mod 4, game length is 2 * n2 - 2 if n2 = 3 mod 4, game length is 2 * n2 - 1 It seems to me likely that an examination of the plays in boxes with small n2 would find a mechanism that explains these game lengths and that shows the above table holds for all n2. Exception 2 -- certain 3 x n2 x n3. For 4 box sizes with n1 = 3, the test predicts a varying game length, but Monte Carlo results saw only a constant game lengh for each of these cases. The box sizes are: 3 3 3 (game length 9 = n1*n2) 3 3 4 (game length 9 = n1*n2) 3 5 5 (game length 11 = n1*n2 - 4) 3 6 7 (game length 16 = n1*n2 - 2) Exception 3 -- 4 x 5 x 5. The test predicts a varying game length for a 4x5x5 box, but the Monte Carlo results saw only one game length: 4 5 5 (game length 13 = n1*n2 - 7) ----- Equivalence to 3-D torus Tom Karzes observed that the edges of the box serve no purpose except to provide a frame of reference. Opposite sides can be identified (considered contiguous), and the game definition and behavior are unchanged. Just as such identification makes a square into a torus, it makes a rectangular box into a "3-D torus". Instead of line segments through a cube chosen for removal, there are closed loops. This equivalence is an easy way to show that all first moves are equivalent. However, the analysis and results proceed the same as before. No advantage has been found to using the equivalence. ----- Variation -- Getting Cubes Dan Asimov suggested a variation he calls "Getting Cubes", in which the requirement to choose a cube with maximal yield is ignored. He asked whether it has the same behavior. Any valid Grabbing Cubes game is a valid Getting Cubes game. So, the range of game length(s) possible for a given box size can only remain the same or expand; no game lengths disappear in changing to Getting Cubes. The same analysis as used above shows that "tall" boxes have a constant game length that is n1*n2, and that n1*n2 is an upper bound for game length on any box size. So, only "short" boxes remain of interest in Getting Cubes. Intuitively, it seems likely that taking less than the maximal yield will often prolong the game. Less likely is that it could shorten the game. But there might be cases where taking a less than maximal yield choice at one step, would prepare the box state for higher yield choices later in the game, perhaps shortening the game. It seems that if there are such situations, they might be rare and hard to find. Monte Carlo play is again used, now to investigate Getting Cubes. This time, only "short" boxes are investigated, and special attention is paid to cases that are exceptions in Grabbing Cubes. We find that allowing any choice of cube does expand the range of game lengths seen, for all of the exception cases. (Those are box sizes that the test allows to have varying length, but Monte Carlo saw only one length in Grabbing Cubes.) First consider the exception series of boxes 2 x N x N, with 2 <= N <= 100. In Getting Cubes, most of these boxes now show three game lengths: n1*n2-2, n1*n2-1, and n1*n2. As N increases, the smallest of these lengths becomes more and more rare. By N = 50, game length n1*n2-2 (here 98) occurs only about once in 1000 games. There does not seem to be any large dependence on N mod 4. However, there are two exceptions, in which one of the three game lengths is not seen, even in 10^6 games: 2 2 2 (game length 2 or 4, never 3) 2 3 3 (game length 5 or 6, never 4) Turning to the other exception cases from Grabbing Cubes, we find these game lengths are seen in 10^6 games: 3 3 3 (game length 5, 7, 9) 3 3 4 (game length 7, 8, 9) 3 5 5 (game length 11, 12, 13, 14, 15) 3 6 7 (game length 15, 16, 17, 18) 4 5 5 (game lengths 13 through 20, no gaps) It is curious that the 3x3x3 box has only odd game lengths. As the box size increases, the low end tail of the distribution becomes thin. For example, in 10^4 games on the 3x6x7 box, a game length of 15 was seen only once. And there is a trend for the distribution peak to pull away from n1*n2 to lower values. For example, the game lengths in 10^6 games on the 4x5x5 box were: length 13 seen 29 times length 14 seen 328 times length 15 seen 14534 times length 16 seen 98570 times length 17 seen 297959 times length 18 seen 332966 times length 19 seen 212452 times length 20 seen 43162 times These comments about distributions and their tails are made to give a sense of how likely the Monte Carlo technique is to miss small values of game length. So, we see that allowing any cube to be chosen does indeed open the play to new game lengths, both larger and smaller than those in Grabbing Cubes. The smallest box in which a longer game occurs is 2x2x2. It is easy to see that a Getting Cubes game with this box can last 4 moves, more than the 2 moves in Grabbing Cubes. The smallest box in which Getting Cubes has a shorter game is 2x4x4. In Grabbing Cubes, the game always lasts 8 moves. In Getting Cubes, it can also be 6 or 7 moves. Here is an example 6-move game and its base diagram: pass 1: take @ 0 0 0, removes 8, alice 8 bob 0, 0 options pass 2: take @ 0 1 3, removes 6, alice 8 bob 6, 24 options pass 3: take @ 0 3 2, removes 4, alice 12 bob 6, 18 options pass 4: take @ 1 1 0, removes 5, alice 12 bob 11, 14 options pass 5: take @ 1 0 3, removes 5, alice 17 bob 11, 9 options pass 6: take @ 1 2 1, removes 4, alice 17 bob 15, 4 options y 3| 2 - 2| - 1 1| 3 0 0| 0 3 +--------- 0 1 x And with a 3x3x3 box, slightly smaller in volume, all Grabbing Cubes games last 9 moves. But in Getting Cubes, the game can also be 5 or 7 moves. Here is an example 5-move game and its base diagram: pass 1: take @ 0 0 0, removes 7, alice 7 bob 0, 0 options pass 2: take @ 1 1 0, removes 5, alice 7 bob 5, 20 options pass 3: take @ 2 2 2, removes 7, alice 14 bob 5, 15 options pass 4: take @ 0 1 1, removes 4, alice 14 bob 9, 8 options pass 5: take @ 1 0 1, removes 4, alice 18 bob 9, 4 options y 2| - - 2 1| 1 0 - 0| 0 1 - +------------ 0 1 2 x The above cases are ones with exceptional behavior in Grabbing Cubes, and the small box examples with longer and shorter games in Getting Cubes. For arbitrary box sizes that have varying length games, we expect the length to have a wider distribution in Getting Cubes than in Grabbing Cubes, as mentioned earlier. However, this seems to be hard to demonstrate. Consider a 7x11x13 box. In Grabbing Cubes, 10^4 games sees game lengths 63 through 77 (no gaps). But in Getting Cubes, even 10^6 games sees only lengths 71 through 77 (no gaps), and length 71 was seen only 3 times. Apparently, the restriction to maximal yield powerfully affects the course of the game, and without the restriction, the distribution is much more concentrated around the most likely values. ----- Other variations on Grabbing Cubes Other variations that come to mind are anticipated in the "Background -- interpretation" section. One is to stop the removal of cubes on each of the six lines emanating from the chosen cube, when a vacant cell is encountered. This would make a very different game, in which the box is no longer equivalent to a 3-D torus. Another variation is to have gravity, so any cubes above the removed cubes fall down into the vacated cells. This action is similar to various video games, such as Tetris. It would be essential to specify which dimension of the box is "up". Again, this would be a very different game. Grabbing Cubes can be extended to higher dimension boxes. Smaller dimension boxes are considered in the "Degenerate box sizes" section. ----- Conclusion Boxes are classified according to their dimensions into "tall" and "short". Tall boxes have game length equal to the product of their two smaller dimensions, which is also an upper bound on game length of all boxes. Most short boxes have several possible game lengths, but there are a few exceptions. The comparison n1 + n2 - 2 : n3 distinguishes tall (<) from short (>=) boxes. Monte Carlo analysis was used to investigate the game, and to derive and support the above test. It is possible, though unlikely, that further exception cases exist among short boxes larger than those explored. A variant called Getting Cubes has behavior similar to Grabbing Cubes, but differs in the details of exception cases and shape of the game length distributions for short boxes. The box in the original "Problem 327" published in Playground is 5 x 13 x 31. This is a tall box. Therefore, the magazine's claim that the game always lasts 65 moves, is correct. However, some discussion of why that box is not one with varying length games, might improve the published proof. ----- References "Problem 327", Playground department, "Math Horizons" magazine, September 2015 and February 2016 issues, Mathematics Association of America. Page numbers not known. James Propp challenged the answer in Playground, on March 10, 2016, in email on a private email list. Further discussion ensued on that list. ----- Acknowledgements Thanks to Jim Propp for raising doubt about the original problem and its answer in "Math Horizons", and for suggesting analysis of unconstrained box sizes. Some of the ideas used herein were first suggested by Dan Asimov and others.