# Unusual 3D Packing Problem

I made up this interesting problem playing with wire sculptures:

If I have a $10 \times 10 \times 10$ clear box and inside I can put wireframe unit cubes, what's the maximum number of unit edges (or total edge length) I can get if I must have exactly $800$ unit cubes in my box? Every unit cube is clear and you can see all $12$ edges, and if two unit cubes are connected by an edge it only counts as a single edge. The unit cubes can float, too and must be on lattice points.

My guess would be to spread out the unit cubes as much as possible to get the most unique edges. Is this equivalent to spreading out the "air pockets" as well as possible? I believe this is some kind of packing problem, but I don't have any experience with those.

• "You can see all $6$ edges." Doesn't a cube have $12$ edges? – mjqxxxx Apr 18 '14 at 2:48
• @mjqxxxx woops, fixed – qwr Apr 18 '14 at 2:48

If the unit cubes are not constrained to the lattice and can float, you can make sure that none of the edges overlap, so can have $12 \cdot 800 = 9600$ edges

If the unit cubes are constrained to the lattice, with many fewer than $800$ cubes you can make sure to have all the edges. In each direction there are $11 \times 11$ edges perpendicular to each layer, for $3 \cdot 11 \cdot 11 \cdot 10 = 3630$ total edges.

Challenge for you: what is the fewest number of cubes constrained to the lattice that give all $3630$ edges?

• The cubes should be on the lattice. I'm not sure how your solution works, I want to know for exactly 800 cubes. Also, I thought that the maximum edges you could get was 500*12, by placing all the cubes so none of them are touching. I've edited my question to say the maximum number of unit edges. – qwr Apr 18 '14 at 2:54
• Where does $500$ come from? My $3630$ is all the edges that are there if you fill the $10 \times 10 \times 10$ cube (ignoring the restriction to $800$ cubes). Even $500 \cdot 12 = 6000$ is greater than this (in case your $800$ should have been $500$), but I can't get all $3630$ from $500$ – Ross Millikan Apr 18 '14 at 3:02
• 500 comes from filling the entire cube with an alternating checkerboard pattern, then each cube has 12 edges. I'm probably missing something, but I'm not sure what. – qwr Apr 18 '14 at 4:57
• But checkerboarding has interior edges covered twice, so you don't get $6000$. The cube in the upper left front and the one diagonally in from it on the top face share an edge, for example. – Ross Millikan Apr 18 '14 at 14:18

You can checkerboard (in 3D) the clear box with only 500 unit cubes. This will pretty much give you every unit edge except 60 along the edges of the clear box. With just 552 (some of the remaining edges share the same unit cube) you already have all the unit edges.

• This does not answer the question, I must have exactly 800 unit cubes. – qwr Apr 18 '14 at 4:41
• @qwr The point is that additional unit cubes can't decrease the number of edges you cover, so once you have all of the edges covered you can put the other cubes wherever you want. – Steven Stadnicki Apr 18 '14 at 4:51
• @qwr: Adding cubes can only increase the number of edges. So if $552$ can do it, so can $800$. – Ross Millikan Apr 18 '14 at 4:51
• @StevenStadnicki hmm, good point. – qwr Apr 18 '14 at 4:57