[math-fun] Grabbing Cubes
I tried 4 tie breaking rules, applied when more than one candidate cube has the same (maximal) size of family that would be removed. If the rule leaves more than one candidate, the one with smallest index x+5y+65z is chosen, where box dimensions in x, y, z are 5, 13, 31 and x, y, z begin at 0. A) Remove cube closest to any corner of the box. B) Remove cube closest to center of any edge of the box. C) Remove cube closest to center of any side of the box. D) Remove cube closest to center of the box. I was surprised that all four rules make games that end after 65 moves. Maybe it’s time to look for a proof. However, the number of cubes Alice and Bob end with differ: A) Alice 1023, Bob 992 (like Taylor and Jamie found) B) same as A C) Alice 1025, Bob 990 D) Alice 1021, Bob 994 Perhaps Dmitry (Alice 1024, Bob 991) had yet another tie breaking rule. — Mike
What if you just break ties by x + 5y + 65z from the outset? On Fri, Mar 11, 2016 at 4:48 PM, Mike Beeler <mikebeeler@verizon.net> wrote:
I tried 4 tie breaking rules, applied when more than one candidate cube has the same (maximal) size of family that would be removed. If the rule leaves more than one candidate, the one with smallest index x+5y+65z is chosen, where box dimensions in x, y, z are 5, 13, 31 and x, y, z begin at 0.
A) Remove cube closest to any corner of the box. B) Remove cube closest to center of any edge of the box. C) Remove cube closest to center of any side of the box. D) Remove cube closest to center of the box.
I was surprised that all four rules make games that end after 65 moves. Maybe it’s time to look for a proof.
However, the number of cubes Alice and Bob end with differ:
A) Alice 1023, Bob 992 (like Taylor and Jamie found) B) same as A C) Alice 1025, Bob 990 D) Alice 1021, Bob 994
Perhaps Dmitry (Alice 1024, Bob 991) had yet another tie breaking rule.
— Mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On third thought, all of these rules just amount to arranging the 2015 cubes in some order. It might be worth assigning a random order to them to see how well that works. Alternatively, just pick one of the maximal-yield cubes at random. On Fri, Mar 11, 2016 at 4:53 PM, Allan Wechsler <acwacw@gmail.com> wrote:
What if you just break ties by x + 5y + 65z from the outset?
On Fri, Mar 11, 2016 at 4:48 PM, Mike Beeler <mikebeeler@verizon.net> wrote:
I tried 4 tie breaking rules, applied when more than one candidate cube has the same (maximal) size of family that would be removed. If the rule leaves more than one candidate, the one with smallest index x+5y+65z is chosen, where box dimensions in x, y, z are 5, 13, 31 and x, y, z begin at 0.
A) Remove cube closest to any corner of the box. B) Remove cube closest to center of any edge of the box. C) Remove cube closest to center of any side of the box. D) Remove cube closest to center of the box.
I was surprised that all four rules make games that end after 65 moves. Maybe it’s time to look for a proof.
However, the number of cubes Alice and Bob end with differ:
A) Alice 1023, Bob 992 (like Taylor and Jamie found) B) same as A C) Alice 1025, Bob 990 D) Alice 1021, Bob 994
Perhaps Dmitry (Alice 1024, Bob 991) had yet another tie breaking rule.
— Mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's an observation: The edges of the box actually serve no purpose, other than to provide a frame of reference. Specifically, I believe you could rotate the cubes along any of the 3 axes without affecting the game play. This implies, for instance, that all initial moves are equivalent. Perhaps it would be better to think of the box as the surface of a 3D torus (i.e., a torus with a 3D surface), with no edges at all? The lines can then be thought of as circles through the torus. Tom Allan Wechsler writes:
On third thought, all of these rules just amount to arranging the 2015 cubes in some order. It might be worth assigning a random order to them to see how well that works. Alternatively, just pick one of the maximal-yield cubes at random.
On Fri, Mar 11, 2016 at 4:53 PM, Allan Wechsler <acwacw@gmail.com> wrote:
What if you just break ties by x + 5y + 65z from the outset?
On Fri, Mar 11, 2016 at 4:48 PM, Mike Beeler <mikebeeler@verizon.net> wrote:
I tried 4 tie breaking rules, applied when more than one candidate cube has the same (maximal) size of family that would be removed. If the rule leaves more than one candidate, the one with smallest index x+5y+65z is chosen, where box dimensions in x, y, z are 5, 13, 31 and x, y, z begin at 0.
A) Remove cube closest to any corner of the box. B) Remove cube closest to center of any edge of the box. C) Remove cube closest to center of any side of the box. D) Remove cube closest to center of the box.
I was surprised that all four rules make games that end after 65 moves. Maybe it’s time to look for a proof.
However, the number of cubes Alice and Bob end with differ:
A) Alice 1023, Bob 992 (like Taylor and Jamie found) B) same as A C) Alice 1025, Bob 990 D) Alice 1021, Bob 994
Perhaps Dmitry (Alice 1024, Bob 991) had yet another tie breaking rule.
— Mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I don't know if this is what Tom means, but it occurred to me that the rectangular solid could just as well be a torus to give a totally isomorphic game. And then an integer translation along any of the 3 axes will also give an isomorphic game. But somehow I feel as if I've seen a game like this before somewhere; I just don't recall where. —Dan
On Mar 11, 2016, at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Here's an observation: The edges of the box actually serve no purpose, other than to provide a frame of reference. Specifically, I believe you could rotate the cubes along any of the 3 axes without affecting the game play. This implies, for instance, that all initial moves are equivalent.
Perhaps it would be better to think of the box as the surface of a 3D torus (i.e., a torus with a 3D surface), with no edges at all? The lines can then be thought of as circles through the torus.
Tom
Allan Wechsler writes:
On third thought, all of these rules just amount to arranging the 2015 cubes in some order. It might be worth assigning a random order to them to see how well that works. Alternatively, just pick one of the maximal-yield cubes at random.
On Fri, Mar 11, 2016 at 4:53 PM, Allan Wechsler <acwacw@gmail.com> wrote:
What if you just break ties by x + 5y + 65z from the outset?
On Fri, Mar 11, 2016 at 4:48 PM, Mike Beeler <mikebeeler@verizon.net> wrote:
I tried 4 tie breaking rules, applied when more than one candidate cube has the same (maximal) size of family that would be removed. If the rule leaves more than one candidate, the one with smallest index x+5y+65z is chosen, where box dimensions in x, y, z are 5, 13, 31 and x, y, z begin at 0.
A) Remove cube closest to any corner of the box. B) Remove cube closest to center of any edge of the box. C) Remove cube closest to center of any side of the box. D) Remove cube closest to center of the box.
I was surprised that all four rules make games that end after 65 moves. Maybe it’s time to look for a proof.
However, the number of cubes Alice and Bob end with differ:
A) Alice 1023, Bob 992 (like Taylor and Jamie found) B) same as A C) Alice 1025, Bob 990 D) Alice 1021, Bob 994
Perhaps Dmitry (Alice 1024, Bob 991) had yet another tie breaking rule.
— Mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
No, Fred, it wasn't Chomp; it was more similar to this game. By the way, how about if we first try to solve the game obtained by ignoring the rule about always making a move that grabs the maximum possible number of cubes. (We could call that one "Getting Cubes".) And ask what is the minimum number of moves to Get all cubes. Is it possible that in the 5 x 13 x 31 case (and for any K x L x M box with K, L, M pairwise relatively prime and K < L < M), then the subset of the box having the (mod K, mod L, mod M) coordinates given by {(j, j, j), 0 <= j < KL} must require at least KL turns to remove? Showing that whichever of the two games are being played, KL is a minimum number of moves for removing all cubes? —Dan
On Mar 11, 2016, at 5:10 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 3/11/16, Dan Asimov <asimov@msri.org> wrote:
... But somehow I feel as if I've seen a game like this before somewhere; I just don't recall where.
—Dan
You're not thinking of Conway's "Chomp" game, by any chance? WFL
Being a (much) poorer mathematician than programmer, I used Monte Carlo as Allan suggested. With box (here a/k/a 3D torus) 5x13x31, a program played 10^6 games. In each game, when there was more than one maximal-yield cube, it picked a random one. All million games lasted exactly 65 passes. Although rare, there were occasional instances where only one cube had maximal yield. So maybe boxes of odd primes p1 < p2 < p3 always take (p1 * p2) passes? I explored boxes with p3<32. 10 odd primes are < 32, so C(10,3) =120 cases to consider. To limit run time, I excluded cases where volume > 4000; that excludes 36, leaving 84. I ran only 1000 games on those 84, with the random choice breaking maximal-yield ties. Of those 84, 75 (including 5x13x31) followed the suspected pattern — all 1000 games lasted the same number of passes. But the other 9 box sizes had games of varying length! I’ll post which those were a bit later. This seems very weird. — Mike
Never mind! Obviously you are expressing the same idea that I obliviously commented on. —Dan
On Mar 11, 2016, at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Here's an observation: The edges of the box actually serve no purpose, other than to provide a frame of reference. Specifically, I believe you could rotate the cubes along any of the 3 axes without affecting the game play. This implies, for instance, that all initial moves are equivalent.
Perhaps it would be better to think of the box as the surface of a 3D torus (i.e., a torus with a 3D surface), with no edges at all? The lines can then be thought of as circles through the torus.
Tom
Allan Wechsler writes:
On third thought, all of these rules just amount to arranging the 2015 cubes in some order. It might be worth assigning a random order to them to see how well that works. Alternatively, just pick one of the maximal-yield cubes at random.
On Fri, Mar 11, 2016 at 4:53 PM, Allan Wechsler <acwacw@gmail.com> wrote:
What if you just break ties by x + 5y + 65z from the outset?
On Fri, Mar 11, 2016 at 4:48 PM, Mike Beeler <mikebeeler@verizon.net> wrote:
I tried 4 tie breaking rules, applied when more than one candidate cube has the same (maximal) size of family that would be removed. If the rule leaves more than one candidate, the one with smallest index x+5y+65z is chosen, where box dimensions in x, y, z are 5, 13, 31 and x, y, z begin at 0.
A) Remove cube closest to any corner of the box. B) Remove cube closest to center of any edge of the box. C) Remove cube closest to center of any side of the box. D) Remove cube closest to center of the box.
I was surprised that all four rules make games that end after 65 moves. Maybe it’s time to look for a proof.
However, the number of cubes Alice and Bob end with differ:
A) Alice 1023, Bob 992 (like Taylor and Jamie found) B) same as A C) Alice 1025, Bob 990 D) Alice 1021, Bob 994
Perhaps Dmitry (Alice 1024, Bob 991) had yet another tie breaking rule.
— Mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thinking about this some more, I realize that you can, in fact, arbitrarily permute the coordinates of any given axis, at any point in the game, without affecting game play. So rather than think of the coordinates as ordered, you can think of them as unordered sets of indices. I think James Propp may have made this observation in an earlier post? With this observation, I believe the second move can be limited to 4 possibilities. You may preserve at most one coordinate index with respect to the initial move (to obtain a maximal number of cubes), so that leaves the following possibilities for the second move: (1) preserve x (2) preserve y (3) preserve z (4) preserve none. I'm not sure if this helps, but I thought I'd throw it out there. Tom Tom Karzes writes:
Here's an observation: The edges of the box actually serve no purpose, other than to provide a frame of reference. Specifically, I believe you could rotate the cubes along any of the 3 axes without affecting the game play. This implies, for instance, that all initial moves are equivalent.
Perhaps it would be better to think of the box as the surface of a 3D torus (i.e., a torus with a 3D surface), with no edges at all? The lines can then be thought of as circles through the torus.
Tom
Allan Wechsler writes:
On third thought, all of these rules just amount to arranging the 2015 cubes in some order. It might be worth assigning a random order to them to see how well that works. Alternatively, just pick one of the maximal-yield cubes at random.
On Fri, Mar 11, 2016 at 4:53 PM, Allan Wechsler <acwacw@gmail.com> wrote:
What if you just break ties by x + 5y + 65z from the outset?
On Fri, Mar 11, 2016 at 4:48 PM, Mike Beeler <mikebeeler@verizon.net> wrote:
I tried 4 tie breaking rules, applied when more than one candidate cube has the same (maximal) size of family that would be removed. If the rule leaves more than one candidate, the one with smallest index x+5y+65z is chosen, where box dimensions in x, y, z are 5, 13, 31 and x, y, z begin at 0.
A) Remove cube closest to any corner of the box. B) Remove cube closest to center of any edge of the box. C) Remove cube closest to center of any side of the box. D) Remove cube closest to center of the box.
I was surprised that all four rules make games that end after 65 moves. Maybe it’s time to look for a proof.
However, the number of cubes Alice and Bob end with differ:
A) Alice 1023, Bob 992 (like Taylor and Jamie found) B) same as A C) Alice 1025, Bob 990 D) Alice 1021, Bob 994
Perhaps Dmitry (Alice 1024, Bob 991) had yet another tie breaking rule.
— Mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Allan Wechsler -
Dan Asimov -
Fred Lunnon -
Mike Beeler -
Tom Karzes