Re: [math-fun] AB=B.AA; Gosper's packing problem
Rich writes: << Gosper's packing puzzle is to fit as many 4x4x1 bricks as possible into a 7x7x7 cube. I'm assuming an "orthogonal, registered" fit, with each brick oriented parallel to a cube face, and placed at integral subcube boundaries. The answer is 18 bricks. [Here is a packing of 18.] My proof is the same as Michael Reid's: Consider the (orthogonal) lines going through the center of the 7x7x7 cube. Take the union, remove the center cell. Resulting collection of subcubes has 18 cells. Any 4x4x1 brick must occupy at least one of these cells. Note that the simple volume constraint gives an upper bound of 7^3/4^2 = 343/16 = 21.4375.
Cute proof. As usual I'm interested in the torus version of this cube puzzle. QUESTION: Suppose we identify the opposite faces of this 7x7x7 cube, to get a 7x7x7 three-torus T. How many registered* 4x4x1 bricks will fit ? (Of course from the cube solution & the volume constraint, the answer lies in {18, 19, 20, 21}. And the proof of Michael & Rich for the cube no longer works for the torus.) --Dan ____________________________________________ * To register your bricks, just send me a check for $50.
It's still 18. Note first that each 7x7x1 plane can contain at most one entire brick, so in order to fit more than 18 bricks, one of the directions must have one entire brick in each plane; call these the base set. Looking at each of the other dimensions, there are 28 1x4 cross-sections of the base set distributed amongst the 7 planes. Since no plane can have more than 7 of these (one from each brick in the base set), there must be at least two planes with at least 4 such cross-sections (5*3+6+7=28). A little fiddling will show that it is impossible to fit a brick and 4 parallel cross-sections into a single plane (they have to be parallel because they come from bricks aligned in the same dimension). So each of the other dimensions can have at most 5 bricks, for 17 total, contrary to our assumption. Franklin T. Adams-Watters -----Original Message----- From: dasimov@earthlink.net To: math-fun <math-fun@mailman.xmission.com> Sent: Tue, 14 Feb 2006 18:09:52 -0500 (EST) Subject: Re: [math-fun] AB=B.AA; Gosper's packing problem Rich writes: << Gosper's packing puzzle is to fit as many 4x4x1 bricks as possible into a 7x7x7 cube. I'm assuming an "orthogonal, registered" fit, with each brick oriented parallel to a cube face, and placed at integral subcube boundaries. The answer is 18 bricks. [Here is a packing of 18.] My proof is the same as Michael Reid's: Consider the (orthogonal) lines going through the center of the 7x7x7 cube. Take the union, remove the center cell. Resulting collection of subcubes has 18 cells. Any 4x4x1 brick must occupy at least one of these cells. Note that the simple volume constraint gives an upper bound of 7^3/4^2 = 343/16 = 21.4375.
Cute proof. As usual I'm interested in the torus version of this cube puzzle. QUESTION: Suppose we identify the opposite faces of this 7x7x7 cube, to get a 7x7x7 three-torus T. How many registered* 4x4x1 bricks will fit ? (Of course from the cube solution & the volume constraint, the answer lies in {18, 19, 20, 21}. And the proof of Michael & Rich for the cube no longer works for the torus.) --Dan ____________________________________________ * To register your bricks, just send me a check for $50. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
You may be amused by the motivation. I built a 7x7x7 analog of Conway's 5x5x5 box packing problem, and was looking for ways to invite solvers by presenting it misassembled. I started by packing 13 4x4x1s, and was badly startled when the 14th didn't fit! (>69% unfilled volume.) I had to restore a bunch of the smaller pieces, largely reconstructing the complete packing, before I regained my marbles. So this is a great subpuzzle for the inexperienced: Hand them the solution. Tell them to take it apart, and then merely repack the 4x4x1s. So far, tested only once, on a photographer who was so shaken that he blurred www.tweedledum.com/rwg/7x7x7noflash.jpg (assembled correctly) and www.tweedledum.com/rwg/7x7x7flash.jpg . --rwg
People might be interested in some correspondence between Martin Gardner and David Klarner (ca 1987) on related packing problems that I have on this page http://www.plambeck.org/oldhtml/mathematics/klarner/martingardner/index.htm Thane Plambeck http://www.plambeck.org/ehome.htm R. William Gosper wrote:
You may be amused by the motivation. I built a 7x7x7 analog of Conway's 5x5x5 box packing problem, and was looking for ways to invite solvers by presenting it misassembled. I started by packing 13 4x4x1s, and was badly startled when the 14th didn't fit! (>69% unfilled volume.) I had to restore a bunch of the smaller pieces, largely reconstructing the complete packing, before I regained my marbles. So this is a great subpuzzle for the inexperienced: Hand them the solution. Tell them to take it apart, and then merely repack the 4x4x1s. So far, tested only once, on a photographer who was so shaken that he blurred www.tweedledum.com/rwg/7x7x7noflash.jpg (assembled correctly) and www.tweedledum.com/rwg/7x7x7flash.jpg . --rwg
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thane>People might be interested in some correspondence between Martin Gardner and
David Klarner (ca 1987) on related packing problems that I have on this page
http://www.plambeck.org/oldhtml/mathematics/klarner/martingardner/index.htm
Cool. Wasn't Klarner arrested for his habit of clandestinely refurbishing cannon in public parks and then firing them in the middle of the night? In the house where I live is a redwood 5x5x5 that Klarner made for Richard Weyhrauch. I still don't understand why there's a 2x2x2 in Conway's 5x5x5. Is there a nice proof that it always needs to contact the 2x2x1? But its ability to do so in a 1x2 area makes it replaceable by another 4x2x1. --rwg PS, A program I wrote finds several solutions/sec to the 7x7x7, e.g. www.tweedledum.com/rwg/7x7x7sol.gif , but only if told where the odd pieces go. When I permute them to be no longer cornerwise connected, yet consistent with the 21 parity constraints, it finds no solutions after many minutes. I assume the same holds for the 5x5x5 (15 constraints), which is probably small enough to search exhaustively. In the 7x7x7, replacing two 2x4x1s with a 15th 4x4x1 had no luck running overnight.
A slightly questionable program sez that if we replace all but two of the fourteen 2x4x1s with six 4x4x1s, the solution is *unique*. (Other pieces: three 3x1x1, one 2x2x1, no 2x2x2.) I think this is actually an easier puzzle, but would like to hear otherwise. --rwg PS, I like Klarner's distinction: perfect packing -> tiling. DISORIENTATING DISINTEGRATION
participants (4)
-
dasimov＠earthlink.net -
franktaw＠netscape.net -
R. William Gosper -
Thane Plambeck