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.