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