I agree that the explanation in Math Horizons doesn't prove what it claims to prove. It also sloppily omits the dimensions of the intended box: 5 x 11 x 13 (= 2015). But it also says that each player must play in such a way as to remove, in each move, the maximum number of cubes they can. The 2nd example of the second player picking (1, 2, 2) can't remove the maximum number of remaining cubes, or it would end the game. —Dan

On Mar 10, 2016, at 12:41 PM, James Propp <jamespropp@gmail.com> wrote:

Let me be more pointed about what troubles me.

Suppose we play Grabbing Cubes with a 2x2x2 block. Number the cubes (i,j,k) with i,j,k each equal to 1 or 2. If the first player grabs (1,1,1) (removing also (1,1,2) and (1,2,1) and (2,1,1)) and the second player grabs (2,2,2) (removing also (1,2,2) and (2,1,2) and (2,2,1)), then the game ends after two moves. On the other hand, if the first player grabs (1,1,1) and the second player grabs (1,2,2), then the game lasts more than two moves.

Am I missing something here?

Jim Propp

On Thu, Mar 10, 2016 at 12:11 PM, James Propp <jamespropp@gmail.com> wrote:

...

Am I the only one who is dissatisfied with the solution to Problem 327 in the Playground feature of the February 2016 issue of "Math Horizons" (see http://digital.ipcprintservices.com/article/The_Playground/2387298/289441/ar... , page 31)?

To show that a certain cube-grabbing game always ends in 65 moves, the authors first show that an obvious way to play the game ends in 65 moves, and then show that "the algorithm for removing the maximum number of cubes at each steps takes 65 steps".

But I don't see why it follows that EVERY way to play the game ends in 65 moves.

Question #1: Am I right to be dissatisfied?

Question #2 (assuming that the answer to Question #1 is "Yes"): Can someone provide a proof that will satisfy me?

Jim Propp

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Dan and James, I think you meant 5 * 13 * 31 = 2015, as opposed to 5 * 11 * 13 = 715. James Propp writes:

As Gareth and Dan point out, I missed the part of the problem statement that says that each move must remove the maximum possible number of cubes. Sloppy reading on my part.

If all such ways of playing out the game are isomorphic under the action of S(5) x S(11) x S(13), then that would provide a simple way of seeing that the claim holds.

Incidentally, I think it's conceivable that the fact that 5, 11, and 13 are distinct might play a role in narrowing the field of possibilities. Indeed, the claim could be true for an a-by-b-by-c block when a, b, and c are distinct but false when a=b=c! This would be a rare example of a proposition that holds in the generic case but fails in degenerate cases. (Most true assertions about rectangles are true for squares as well!)

Jim

On Thursday, March 10, 2016, Dan Asimov <asimov@msri.org <javascript:_e(%7B%7D,'cvml','asimov@msri.org');>> wrote:

...

I agree that the explanation in Math Horizons doesn't prove what it claims to prove. It also sloppily omits the dimensions of the intended box: 5 x 11 x 13 (= 2015).

But it also says that each player must play in such a way as to remove, in each move, the maximum number of cubes they can.

The 2nd example of the second player picking (1, 2, 2) can't remove the maximum number of remaining cubes, or it would end the game.

—Dan

...

On Mar 10, 2016, at 12:41 PM, James Propp <jamespropp@gmail.com> wrote:

Let me be more pointed about what troubles me.

Suppose we play Grabbing Cubes with a 2x2x2 block. Number the cubes (i,j,k) with i,j,k each equal to 1 or 2. If the first player grabs (1,1,1) (removing also (1,1,2) and (1,2,1) and (2,1,1)) and the second player grabs (2,2,2) (removing also (1,2,2) and (2,1,2) and (2,2,1)), then the game ends after two moves. On the other hand, if the first player grabs (1,1,1) and the second player grabs (1,2,2), then the game lasts more than two moves.

Am I missing something here?

Jim Propp

On Thu, Mar 10, 2016 at 12:11 PM, James Propp <jamespropp@gmail.com> wrote:

...

Am I the only one who is dissatisfied with the solution to Problem 327 in the Playground feature of the February 2016 issue of "Math Horizons" (see

http://digital.ipcprintservices.com/article/The_Playground/2387298/289441/ar...

...

, page 31)?

To show that a certain cube-grabbing game always ends in 65 moves, the authors first show that an obvious way to play the game ends in 65 moves, and then show that "the algorithm for removing the maximum number of cubes at each steps takes 65 steps".

But I don't see why it follows that EVERY way to play the game ends in 65 moves.

Question #1: Am I right to be dissatisfied?

Question #2 (assuming that the answer to Question #1 is "Yes"): Can someone provide a proof that will satisfy me?

Jim Propp

_______________________________________________ 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

Here is more strange data on Grabbing Cubes. It looks like Jim Propp was right to be suspicious of the proof in Math Horizons, because it does not say why 5 x 13 x 31 has no shortcut, as several other box sizes do. Consider all 120 boxes with distinct odd prime dimensions p1<p2<p3<32. For each box size, I ran 1000 games. Whenever more than one cube had maximal yield, a random choice among those was made. 87 box sizes had the same game length in all 1000 games, namely p1*p2. But the other 33 box sizes have a distribution of game lengths. The maximum game length seen is p1*p2. In general, for larger boxes, the game lengths seen becomes farther and farther below p1*p2. It seems that there are shortcut strategies available for these boxes, and the larger the box, the more the shortcuts become unavoidable. What distinguishes the box sizes that have shorter games??? The 33 are: box 5 11 13, length 49 to 55 no gaps box 5 17 19, length 78 to 85 no gaps box 5 29 31, length 138 to 145 no gaps box 7 11 13, length 63 to 75 with gaps box 7 13 17, length 85 to 91 no gaps box 7 17 19, length 107 to 118 no gaps box 7 19 23, length 126 to 133 no gaps box 7 29 31, length 190 to 201 no gaps box 11 13 17, length 123 to 140 no gaps box 11 13 19, length 131 to 142 no gaps box 11 17 19, length 157 to 177 with gaps box 11 17 23, length 175 to 187 no gaps box 11 19 23, length 188 to 205 no gaps box 11 23 29, length 242 to 253 no gaps box 11 23 31, length 248 to 253 no gaps box 11 29 31, length 288 to 309 with gaps box 13 17 19, length 178 to 201 no gaps box 13 17 23, length 202 to 218 with gaps box 13 19 23, length 218 to 235 no gaps box 13 19 29, length 242 to 247 no gaps box 13 23 29, length 278 to 295 no gaps box 13 23 31, length 288 to 299 no gaps box 13 29 31, length 331 to 357 no gaps box 17 19 23, length 263 to 294 no gaps box 17 19 29, length 305 to 319 no gaps box 17 19 31, length 312 to 323 no gaps box 17 23 29, length 348 to 373 no gaps box 17 23 31, length 360 to 381 with gaps box 17 29 31, length 407 to 451 with gaps box 19 23 29, length 379 to 410 with gaps box 19 23 31, length 393 to 419 with gaps box 19 29 31, length 454 to 497 with gaps box 23 29 31, length 527 to 584 with gaps The range of game lengths is those seen in 1000 games. "With gaps" means some value(s) in the range were not seen. For instance, box 7 11 13, game length 64 was not seen. But running 10^4 games not only saw 64, but also saw 76 and 77, extending the range to p1*p2 = 7*11 = 77: box 7 11 13, 10000 games, length 63 to 77 no gaps But running box 7 17 19 for 10^4 games saw only one smaller game length (106), the max seen (118) still falling short of p1*p2 = 119. The high end tail for 7 17 19 might be very thin, so running many more games might encounter length 119. That seems unlikely for 11 17 19, where 10^4 games saw only a new low game length (156). Its high game length seen (177) is far short of p1*p2 = 187. -- Mike

Sure, this is fun! My program is written to take any box dimensions, so doing non-primes is easy. I wondered about that myself, but figured odd primes may have some sort of “primitive” quality that non-prime dimensions would obscure. Another observation is that none of the boxes with a dimension (necessarily the smallest) = 3 are on the list of variable game lengths. I wonder whether there is something about 3 that precludes the “shortcut” phenomenon? I am thinking about running cases of 3 x p2 x p3 with p2 and/or p3 higher than 31. Currently, the max box volume is 21000, to accommodate the 23 x 29 x 31. My program can allow boxes with 2 or 3 dimensions equal. Are those of interest? Are there any box sizes or ranges of box sizes you are particularly interested in? I’m happy to run anything that executes in less than a day or so. Run time seems to be roughly proportional to p1^2 * p2^2 * p3. 23 x 29 x 31 takes 23 minutes for 1000 games. — Mike

On Mar 14, 2016, at 11:18 AM, James Propp <jamespropp@gmail.com> wrote:

Thanks Mike! Do you have a feeling for why primeness might play a role here? It might be illuminating to look at n1-by-n2-by-n3 boxes with n1 < n2 < n3 where n1, n2, and n3 are not required to be odd primes. Delving into an example smaller than the 5-by-11-by-13 block (the smallest block on your list) might give us some insight into what's going on in the general case.

Meanwhile, I'll try to find out who's responsible for the problem. It's quite possible that the author submitted a valid solution but that the editor of the column didn't appreciate the subtlety of the problem and therefore published a shorter invalid solution.

Jim

Fascinating! I had proposed earlier that, maybe, the set X = X(p1,p2,p3) = {(j, j, j) | 0 <= j < p1*p2} with the coordinates are taken (mod p1, mod p2, mod p3), gives a set of cubes that require p1*p2 moves to grab.* Clearly Mike's data shows that is wrong at least in many cases. This shows that X must have more than one member in the same row (x direction), row (y direction), or column (each of which we could call a "segment"). Maybe in the cases where the minimum game (all games?) is p1*p2, no two members of X lie in the same segment? Question: In any p1 x p2 x p3 game, with the pj distinct primes: What is the maximum size of a subset of cubes such that no 2 of them lie in the same segment? And how do you find such a subset? —Dan ————————————————————————————————————————————————————————————————— * Though that was for p1, p2, p3 be not just primes but any three numbers that are pairwise relatively prime. Mike Beeler (mikebeeler@verizon.net) wrote: Here is more strange data on Grabbing Cubes. It looks like Jim Propp was right to be suspicious of the proof in Math Horizons, because it does not say why 5 x 13 x 31 has no shortcut, as several other box sizes do. Consider all 120 boxes with distinct odd prime dimensions p1<p2<p3<32. For each box size, I ran 1000 games. Whenever more than one cube had maximal yield, a random choice among those was made. 87 box sizes had the same game length in all 1000 games, namely p1*p2. But the other 33 box sizes have a distribution of game lengths. The maximum game length seen is p1*p2. In general, for larger boxes, the game lengths seen becomes farther and farther below p1*p2. It seems that there are shortcut strategies available for these boxes, and the larger the box, the more the shortcuts become unavoidable. What distinguishes the box sizes that have shorter games??? The 33 are: box 5 11 13, length 55 > 49 to 55 no gaps box 5 17 19, length 85 > 78 to 85 no gaps box 5 29 31, length 145 > 138 to 145 no gaps box 7 11 13, length 77 > 63 to 75 with gaps box 7 13 17, length 91 > 85 to 91 no gaps box 7 17 19, length 119 > 107 to 118 no gaps box 7 19 23, length 133 > 126 to 133 no gaps box 7 29 31, length 203 > 190 to 201 no gaps box 11 13 17, length 143 > 123 to 140 no gaps box 11 13 19, length 143 > 131 to 142 no gaps box 11 17 19, length 187 > 157 to 177 with gaps box 11 17 23, length 187 > 175 to 187 no gaps box 11 19 23, length 209 > 188 to 205 no gaps box 11 23 29, length 253 > 242 to 253 no gaps box 11 23 31, length 253 > 248 to 253 no gaps box 11 29 31, length 319 > 288 to 309 with gaps box 13 17 19, length 221 > 178 to 201 no gaps box 13 17 23, length 221 > 202 to 218 with gaps box 13 19 23, length 247 > 218 to 235 no gaps box 13 19 29, length 247 > 242 to 247 no gaps box 13 23 29, length 299 > 278 to 295 no gaps box 13 23 31, length 299 > 288 to 299 no gaps box 13 29 31, length 377 > 331 to 357 no gaps box 17 19 23, length 323 > 263 to 294 no gaps box 17 19 29, length 323 > 305 to 319 no gaps box 17 19 31, length 323 > 312 to 323 no gaps box 17 23 29, length 391 > 348 to 373 no gaps box 17 23 31, length 391 > 360 to 381 with gaps box 17 29 31, length 493 > 407 to 451 with gaps box 19 23 29, length 437 > 379 to 410 with gaps box 19 23 31, length 437 > 393 to 419 with gaps box 19 29 31, length 551 > 454 to 497 with gaps box 23 29 31, length 667 > 527 to 584 with gaps The range of game lengths is those seen in 1000 games. "With gaps" means some value(s) in the range were not seen. For instance, box 7 11 13, game length 64 was not seen. But running 10^4 games not only saw 64, but also saw 76 and 77, extending the range to p1*p2 = 7*11 = 77: box 7 11 13, 10000 games, length 63 to 77 no gaps But running box 7 17 19 for 10^4 games saw only one smaller game length (106), the max seen (118) still falling short of p1*p2 = 119. The high end tail for 7 17 19 might be very thin, so running many more games might encounter length 119. That seems unlikely for 11 17 19, where 10^4 games saw only a new low game length (156). Its high game length seen (177) is far short of p1*p2 = 187. -- Mike _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <mailto:math-fun@mailman.xmission.com> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun <https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>

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

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

I forgot it first! :-) Jim On Tue, Mar 15, 2016 at 6:54 PM, Allan Wechsler <acwacw@gmail.com> wrote:

You are quite right; I forgot that restriction completely!

On Tue, Mar 15, 2016 at 6:52 PM, Dan Asimov <asimov@msri.org> wrote:

...

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

_______________________________________________ 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

My observations from the results in (1) for n1=2, n2=n3 are the numbers not divisible by four and game length = 2*n2 - 1 - is_even(n2) you could try whether this patterns continues for n2=n3>16... Christoph ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Mike Beeler [mikebeeler@verizon.net] Sent: Wednesday, March 16, 2016 2:42 AM To: math-fun Subject: Re: [math-fun] Grabbing Cubes Some further Grabbing Cubes results. The strangeness continues. -- Mike Consider distinct odd prime boxes with (p1=3) < p2 < p3 < 100. There are 23 odd primes between 3 and 100; C(23,2) = 253. For each of the 253 box sizes, 1000 games were played, with random choice to break ties among maximal-yield cubes. In all games for all 253 boxes, the game length = p1(=3) * p2, as in the original problem. None were seen to have varying game length. It seems a box must have minimum dimension > 3 to have the "shortcuts" phenomenon that causes varying game lengths on these box sizes. Then 1000 games, with random tie breaking, were played on boxes with not necessarily distinct and not necessarily prime dimensions. Box dimensions 2 <= n1 <= n2 <= n3 <= 16 were run. This is 680 cases. Results: (1) In 14 box sizes, the 1000 games had constant length, but that length was not n1*n2. The box sizes and the game lengths are: 2 2 2, game length = 2 2 3 3, game length = 5 2 5 5, game length = 9 2 6 6, game length = 10 2 7 7, game length = 13 2 9 9, game length = 17 2 10 10, game length = 18 2 11 11, game length = 21 2 13 13, game length = 25 2 14 14, game length = 26 2 15 15, game length = 29 3 5 5, game length = 11 3 6 7, game length = 16 4 5 5, game length = 13 (2) Over all 680 cases, only the 14 noted above had a constant game length not equal to n1*n2. All others had length=n1*n2, or had varying length. (3) For n1 = 3, most (82) box sizes had constant game length. The 23 others with varying game length were: 3 4 4 3 4 5 3 5 6 3 6 6 3 7 7 3 7 8 3 8 8 3 8 9 3 9 9 3 9 10 3 10 10 3 10 11 3 11 11 3 11 12 3 12 12 3 12 13 3 13 13 3 13 14 3 14 14 3 14 15 3 15 15 3 15 16 3 16 16 (4) For various n1, the following table shows n1, the total number of boxes analyzed, the number with varying game lentgh, the number with constant n1*n2 game length, and the number with constant < n1*n2 game length. This covers all 680 cases, including those in (1)-(3) above. n1 cases varying const=n1*n2 const<n1*n2 2 120 0 109 11 3 105 23 80 2 4 91 35 55 1 5 78 42 36 0 6 66 45 21 0 7 55 45 10 0 8 45 42 3 0 9 36 36 0 0 10 28 28 0 0 11 21 21 0 0 12 15 15 0 0 13 10 10 0 0 14 6 6 0 0 15 3 3 0 0 16 1 1 0 0 The table seems to suggest that larger boxes are more likely to have varying length games, but that may be an artifact of the cutoff (the search limited all dimensions to at most 16). For example, consider: 4 10 10, varying length 4 10 11, varying length 4 10 12, varying length 4 10 13, constant length = 40 4 10 14, constant length = 40 4 10 15, constant length = 40 4 10 16, constant length = 40 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun