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$ 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$ 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.