1
$\begingroup$

Assume that you have an $10\times 10\times 10$ cube and many $3\times 3\times 3$ cubes. What is the smallest number of $3 \times 3\times 3$ cubes needed to cover the large cube?

The small cubes can overlap. They must be placed at integer coordinates and aligned with the large cube: if you divide the $10\times 10\times10$ cube into $1000$ unit cubes, each $3\times3\times3$ cube should cover $27$ of those unit cubes.

The boundary of the $10\times 10 \times 10$ cube is periodic: if you have a small cube intersecting one face of the large cube, it wraps around to come back in from the opposite face, Pac-Man style.

$\endgroup$
8
  • 1
    $\begingroup$ I can't understand the language. What are you trying to ask? $\endgroup$ Commented Sep 12, 2018 at 14:02
  • $\begingroup$ Teleports where exactly inside? Can you provide a drawing and add it to your question, please? $\endgroup$
    – dmtri
    Commented Sep 12, 2018 at 14:06
  • $\begingroup$ Do you mean periodic boundaries? Also, may smaller cubes overlap? Are possible small cube positions continuous or discrete? $\endgroup$
    – denklo
    Commented Sep 12, 2018 at 14:09
  • $\begingroup$ i have an 10x10 cube that consists of 1000 smaller ones,i need to fill it up using 3x3 cubes i can only give midle of a cube and that middle cube must be one of 1000 smaller ones,cubes can intersect and if midpoint of a cube is in the boundary(cubes that you can see,) cubes that outside the big cube go to other side of the cube like in pacman. sorry i am not a native english speaker and this is somewhat weird. feel free to edit the question (positions are discrete) $\endgroup$ Commented Sep 12, 2018 at 14:10
  • 2
    $\begingroup$ The boundaries of the cube wrap around (topologically, it is a three-torus). $\endgroup$ Commented Sep 12, 2018 at 14:39

1 Answer 1

6
$\begingroup$

A partial answer: we need at least $47$ $3\times3\times3$ cubes to cover a $10\times10\times10$ cube that wraps around, and $54$ are definitely enough.

For the lower bound: a $10\times 1 \times 1$ column needs at least $4$ cubes to cover it: $3$ are not enough, since each cube can cover at most $3$ of the $10$ squares. A $10 \times 10 \times 1$ slice contains $10$ columns, each one requiring at least $4$ cubes; that's $40$ cubes in total, but each one is counted $3$ times (by $3$ columns) so we actually just need at least $\frac{40}{3}$ cubes, or $\left\lceil \frac{40}{3}\right\rceil = 14$. Finally, the whole cube contains $10$ slices, each one requiring at least $14$ cubes; that's $140$ cubes in total, but each one is counted $3$ times (by $3$ slices) so we actually just need $\left\lceil \frac{140}{3}\right\rceil = 47$.

The bound on $10\times 10\times 1$ slices is tight: we can cover a $10\times 10$ square with only $14$ $3\times 3$ squares, as shown below. (Finding this was my first successful attempt at using simulated annealing, so go me!)

14-square covering

The actual coordinates of the squares are: $$\{(1, 2), (1, 7), (2, 4), (2, 10), (3, 3), (3, 7), (5, 6),\\ (5, 10), (6, 3), (6, 9), (8, 2), (8, 6), (9, 5), (9, 9)\}.$$

Replicate this $4$ times (with third coordinate, say, $1$, $4$, $7$, and $8$) and you cover the $10\times10\times10$ cube by $56$ $3\times3\times3$ cubes.

However, we can do slightly better. By another search, I found a covering of the $7\times7\times7$ cube with $20$ cubes; the coordinates are $$ \{(5, 5, 3), (5, 3, 7), (6, 7, 1), (6, 4, 1), (6, 4, 4), (7, 5, 5), (7, 1, 6),\\ (7, 1, 3), (1, 7, 2), (1, 2, 5), (1, 3, 2), (2, 5, 1), (2, 6, 4), (2, 4, 7),\\ (3, 6, 7), (3, 2, 1), (3, 3, 4), (4, 6, 6), (4, 1, 3), (4, 2, 5)\}. $$ (Sorry, I'm not sure how to draw a picture here.) We can turn this into a packing of the $10\times10\times10$ cube by replacing a cube at $(x,y,z)$ with $x\ge 4$ by two cubes, one at $(x,y,z)$ and one at $(x+3,y,z)$, then doing the same for $y$ and for $z$. This results, in this case, in a $54$-cube packing of the larger cube: $$\{(5, 5, 3), (5, 8, 3), (8, 5, 3), (8, 8, 3), (5, 3, 7), (5, 3, 10), (8, 3, 7), (8, 3, 10), (6, 7, 1), \\ (6, 10, 1), (9, 7, 1), (9, 10, 1), (6, 4, 1), (9, 4, 1), (6, 4, 4), (9, 4, 4), (7, 5, 5), (7, 5, 8), \\ (7, 8, 5), (7, 8, 8), (10, 5, 5), (10, 5, 8), (10, 8, 5), (10, 8, 8), (7, 1, 6), (7, 1, 9), (10, 1, 6), \\ (10, 1, 9), (7, 1, 3), (10, 1, 3), (1, 7, 2), (1, 10, 2), (1, 2, 5), (1, 2, 8), (1, 3, 2), (2, 5, 1), \\ (2, 8, 1), (2, 6, 4), (2, 9, 4), (2, 4, 7), (2, 4, 10), (3, 6, 7), (3, 6, 10), (3, 9, 7), (3, 9, 10), \\ (3, 2, 1), (3, 3, 4), (4, 6, 6), (4, 6, 9), (4, 9, 6), (4, 9, 9), (4, 1, 3), (4, 2, 5), (4, 2, 8)\}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .