The only difference I see is that the rules of the game require that each move grab the maximum number of cubes possible at that stage in the game, while the rook problem is equivalent to asking for the minimum number of moves a game can have without that restriction. (What I called "Getting Cubes".) Is it obvious the numbers are the same? —Dan
On Mar 15, 2016, at 3:48 PM, Allan Wechsler <acwacw@gmail.com> wrote:
This problem is asking, essentially, how many three-dimensional "rooks" it takes to "control" a three-dimensional "chessboard" of dimensions p, q, r. Assuming p<q<r, we know we can do it with pq rooks, and Mike's examples suggest that we can sometimes do better.
Suppose p=1 -- or, equivalently, let's consider the same problem in two dimensions. It's obvious that we can never do better than q. Suppose we place fewer than q rooks on a q-by-r board. Then, among the q rows, there must be at least one with no rooks on it. But then, to control the squares of that row, there must be a rook in every column, and that would require r or more rooks.
But this proof breaks down in three dimensions (or, equivalently, when p>1) -- though it still flies when r>pq.
On Tue, Mar 15, 2016 at 9:58 AM, Mike Beeler <mikebeeler@verizon.net> wrote:
I could be wrong. Thanks for sanity checking my results. Here are moves in a 49-pass game with box 5 x 11 x 13. “options” is how many cubes have maximal yield. The first cube is arbitrarily the one at the origin. Is there an illegal move here?
— Mike
starting run, box 5 11 13, 1 games in run pass 1: take @ 0 0 0, removes 27, alice 27 bob 0, 0 options pass 2: take @ 3 5 2, removes 27, alice 27 bob 27, 480 options pass 3: take @ 1 9 11, removes 27, alice 54 bob 27, 297 options pass 4: take @ 4 4 3, removes 27, alice 54 bob 54, 160 options pass 5: take @ 2 6 7, removes 27, alice 81 bob 54, 63 options pass 6: take @ 3 3 12, removes 25, alice 81 bob 79, 240 options pass 7: take @ 2 2 1, removes 25, alice 106 bob 79, 140 options pass 8: take @ 0 7 4, removes 25, alice 106 bob 104, 72 options pass 9: take @ 1 10 10, removes 25, alice 131 bob 104, 30 options pass 10: take @ 4 1 9, removes 25, alice 131 bob 129, 8 options pass 11: take @ 4 8 5, removes 23, alice 154 bob 129, 15 options pass 12: take @ 1 3 8, removes 21, alice 154 bob 150, 72 options pass 13: take @ 0 8 6, removes 21, alice 175 bob 150, 27 options pass 14: take @ 3 9 8, removes 21, alice 175 bob 171, 2 options pass 15: take @ 2 10 11, removes 20, alice 195 bob 171, 10 options pass 16: take @ 4 7 6, removes 19, alice 195 bob 190, 5 options pass 17: take @ 0 4 5, removes 19, alice 214 bob 190, 3 options pass 18: take @ 1 5 12, removes 19, alice 214 bob 209, 1 options pass 19: take @ 2 1 10, removes 18, alice 232 bob 209, 9 options pass 20: take @ 3 0 4, removes 18, alice 232 bob 227, 3 options pass 21: take @ 3 6 0, removes 16, alice 248 bob 227, 15 options pass 22: take @ 1 2 7, removes 16, alice 248 bob 243, 5 options pass 23: take @ 2 4 9, removes 15, alice 263 bob 243, 9 options pass 24: take @ 0 6 2, removes 15, alice 263 bob 258, 4 options pass 25: take @ 4 10 1, removes 14, alice 277 bob 258, 3 options pass 26: take @ 1 1 1, removes 14, alice 277 bob 272, 2 options pass 27: take @ 4 2 10, removes 14, alice 291 bob 272, 1 options pass 28: take @ 2 8 3, removes 13, alice 291 bob 285, 5 options pass 29: take @ 0 5 8, removes 12, alice 303 bob 285, 4 options pass 30: take @ 3 7 5, removes 12, alice 303 bob 297, 1 options pass 31: take @ 0 9 12, removes 11, alice 314 bob 297, 1 options pass 32: take @ 1 0 2, removes 10, alice 314 bob 307, 2 options pass 33: take @ 3 4 6, removes 9, alice 323 bob 307, 9 options pass 34: take @ 2 9 0, removes 9, alice 323 bob 316, 8 options pass 35: take @ 4 3 4, removes 9, alice 332 bob 316, 6 options pass 36: take @ 0 3 3, removes 9, alice 332 bob 325, 1 options pass 37: take @ 3 8 9, removes 8, alice 340 bob 325, 1 options pass 38: take @ 1 6 4, removes 7, alice 340 bob 332, 1 options pass 39: take @ 2 0 6, removes 6, alice 346 bob 332, 8 options pass 40: take @ 4 0 11, removes 6, alice 346 bob 338, 2 options pass 41: take @ 3 1 3, removes 5, alice 351 bob 338, 4 options pass 42: take @ 1 7 0, removes 5, alice 351 bob 343, 1 options pass 43: take @ 0 10 7, removes 4, alice 355 bob 343, 3 options pass 44: take @ 0 2 11, removes 4, alice 355 bob 347, 2 options pass 45: take @ 2 7 2, removes 4, alice 359 bob 347, 1 options pass 46: take @ 4 5 7, removes 3, alice 359 bob 350, 3 options pass 47: take @ 2 5 5, removes 3, alice 362 bob 350, 1 options pass 48: take @ 4 6 8, removes 2, alice 362 bob 352, 2 options pass 49: take @ 4 9 2, removes 1, alice 363 bob 352, 1 options box 5 11 13, 1 games, min options = 1, 0 sec, length 49 to 49 no gaps length 49, 1 games, example random seed = 163
On Mar 14, 2016, at 3:39 PM, James Propp <jamespropp@gmail.com> wrote:
I thought I was confused before, but now I am *really* confused.
I just wrote a short Mathematica program and checked that Dan's suggestion (which I somehow missed before --- more sloppy reading on my part!) seems to work to prove the original published version of the problem. That is, I verified that the set of triples {(j, j, j) | 0 <= j < 65}, taken (mod 5, mod 13, mod 31), doesn't have any two points on a coordinate line (what Dan calls a "segment").
But then I changed some numbers in my code and verified that the set of triples {(j, j, j) | 0 <= j < 55}, taken (mod 5, mod 11, mod 13), doesn't have any two points on a coordinate line. This seems to imply (by Dan's argument) that in this case, 55 moves are required --- contradicting Mike's claim!
Jim
_______________________________________________ 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