16
$\begingroup$

This is a more geometric version of the previous question, "Lattice-cube minimal blocking sets". I will first specialize to $\mathbb{R}^3$, $d=3$.

View an $n \times n \times n$ cube $C_3(n)$ as formed of $n^3$ unit cubes glued face-to-face. I would like to find a minimal blocking object $B$ inside $C_3(n)$, which I define as a collection of the unit cubes in $C_3(n)$ with the following two properties: (a) The shadow of $B$ by parallel light rays in the three orthogonal directions (parallel to the cube edges) is an $n \times n$ filled square. (b) $B$ is a connected object, in the sense that its dual graph is connected. Here the dual graph has a node for each unit cube in $B$ and an edge between each pair of cubes that share a face.

$B$ is intended to be a minimal volume object that casts shadows like a cube. The connectedness condition ensures one could build a physical model of $B$.

The previous MO question did not include the connected condition. There it was shown that blocking sets of size $n^2$ are attainable, $n^{d-1}$ in dimension $d$. Certainly that lower bound is no longer achievable in general, as can be seen with $C_2(2)$: a $2 \times 2$ square in dimension $d=2$ needs $3$ rather than $2=2^1$ unit squares to form a connected blocking object. Exploring $n=3$ in $\mathbb{R}^3$, I have been unable to create a connected blocking object with fewer than 15 cubes:
            Blocking Object

\[ \left[\begin{array}{ccc} 0 & 1 & 1 \\\\ 0 & 1 & 0 \\\\ 1 & 1 & 0 \end{array}\right] \hspace{0.25 in} \left[\begin{array}{ccc} 0 & 1 & 0 \\\\ 1 & 1 & 1 \\\\ 0 & 1 & 0 \end{array}\right] \hspace{0.25in} \left[\begin{array}{ccc} 1 & 0 & 0 \\\\ 1 & 1 & 1 \\\\ 0 & 0 & 1 \end{array}\right] \]

Fifteen seems excessive—more than half!. Can anyone see a better solution? In addition, I do not see how to generalize to $C_3(n)$, let alone to $C_d(n)$, the same question in $d$ dimensions.

Addendum. Here is Joel's 13-cube blocker from his answer below:
            Joel: 13 cubes

$\endgroup$
9
  • 1
    $\begingroup$ A simpler (to me) configuration involves a 3x3 slice with 6 cubes on either diagonal, one above and one below. Gerhard "Ask Me About System Design" Paseman, 2012.08.03 $\endgroup$ Aug 4, 2012 at 0:20
  • 2
    $\begingroup$ Further, one can do two such planes for arbitrary n to get 2n^2 - n for C_3(n). Gerhard "Ask Me About System Design" Paseman, 2012.08.03 $\endgroup$ Aug 4, 2012 at 0:27
  • 1
    $\begingroup$ I also think one needs an extra cube for most every cube in the figure. I believe that (2n-1)n^(d-2) will be an upper if not exact bound in general. Gerhard "Ask Me About System Design" Paseman, 2012.08.03 $\endgroup$ Aug 4, 2012 at 0:53
  • $\begingroup$ @Gerhard: Your insights are (to me) amazing! And very much appreciated. $\endgroup$ Aug 4, 2012 at 1:25
  • 3
    $\begingroup$ A lower bound is $C_3(n)\geq (3n^2-1)/2$. This is best possible for $n=2,3$. $\endgroup$ Aug 4, 2012 at 5:22

5 Answers 5

10
$\begingroup$

Lower bound:

Let there be $c$ cubes in a blocking configuration. Consider the graph whose vertices are cubes so that cubes are connected if they share a face. Any connected graph has at least $c-1$ edges. By the pigeonhole principle, there is at least one direction with at least $(c-1)/d$ edges in that direction. When you project parallel to that axis, the image has size $n^{d-1}$, and the size of the image is also at most $c - (c-1)/d$ since at least one vertex on each of those edges is redundant. So,

$$ n^{d-1} \le c - \frac{c-1}{d} = c \frac{d-1}{d} + \frac 1d$$

$$ c \ge \bigg(\frac {d}{d-1}\bigg)n^{d-1} - \frac {1}{d-1}. $$

For $d=3$, $c \ge \frac 32 n^2 - \frac12$ (mentioned by Gjergji Zaimi in the comments). This is sharp for $n=3$ by the construction with $13$ cubes shown by Joel David Hamkins.

Upper bound ($d=3$):

Here is a construction of a connected blocking configuration with $\frac32n^2 + O(n)$ cubes related to Zack Wolske's constructions. We'll identify the cubes with lattice points. We start with the points $\lbrace(x,y,z) | x-y \equiv z \mod n, 0 \le x,y,z \lt n \rbrace$, illustrated for $n=7$.

|......X|  |x......|  |.x.....|  |..x....|  |...x...|  |....x..|  |.....x.|
|.....X.|  |......X|  |x......|  |.x.....|  |..x....|  |...x...|  |....x..|
|....X..|  |.....X.|  |......X|  |x......|  |.x.....|  |..x....|  |...x...|
|...X...|  |....X..|  |.....X.|  |......X|  |x......|  |.x.....|  |..x....|
|..X....|  |...X...|  |....X..|  |.....X.|  |......X|  |x......|  |.x.....|
|.X.....|  |..X....|  |...X...|  |....X..|  |.....X.|  |......X|  |x......|
|X......|  |.X.....|  |..X....|  |...X...|  |....X..|  |.....X.|  |......X|

This is made of two triangles of points, in the planes $x-y=z$ (marked X) and $x-y=z-n$ (marked x), which are separated by some distance. We'll first make the connections within the triangles, and then connect the triangles to each other.

To connect the bottom triangle, use $n-1$ extra points (marked A) to connect the base of the triangle in the plane $z=0$ to itself and to the points in the triangle with $z=1$. Then for $i = 2, ..., n-1$, use $\lceil (n-i-1)/2 \rceil$ points (marked O) to connect the points in the plane $z=i$ to each other and to the lower points in the triangle. These points have $y$ odd, and are just above an X in the layer below.

|......X|  |x......|  |.x.....|  |..x....|  |...x...|  |....x..|  |.....x.|
|.....XA|  |......X|  |x.....O|  |.x.....|  |..x....|  |...x...|  |....x..|
|....XA.|  |.....X.|  |......X|  |x......|  |.x.....|  |..x....|  |...x...|
|...XA..|  |....X..|  |....OX.|  |.....OX|  |x.....O|  |.x.....|  |..x....|
|..XA...|  |...X...|  |....X..|  |.....X.|  |......X|  |x......|  |.x.....|
|.XA....|  |..X....|  |..OX...|  |...OX..|  |....OX.|  |.....OX|  |x.....O|
|XA.....|  |.X.....|  |..X....|  |...X...|  |....X..|  |.....X.|  |......X|

This has added $n-1$ A's (this is one of the few correct uses of apostrophes to indicate a plural), and $0+1+1+2+2+...+\lfloor (n-1)/2 \rfloor = \lfloor (n-1)^2/4 \rfloor$ O's (see A002620).

We repeat the process upside down to connect the upper left triangle using $n-2$ A's and $\lfloor (n-2)^2/4 \rfloor$ O's.

|......X|  |x......|  |.x.....|  |..x....|  |...x...|  |....x..|  |....Ax.|
|.....XA|  |O.....X|  |xO....O|  |.xO....|  |..xO...|  |...x...|  |...Ax..|
|....XA.|  |.....X.|  |......X|  |x......|  |.x.....|  |..x....|  |..Ax...|
|...XA..|  |....X..|  |....OX.|  |O....OX|  |xO....O|  |.x.....|  |.Ax....|
|..XA...|  |...X...|  |....X..|  |.....X.|  |......X|  |x......|  |Ax.....|
|.XA....|  |..X....|  |..OX...|  |...OX..|  |....OX.|  |.....OX|  |x.....O|
|XA.....|  |.X.....|  |..X....|  |...X...|  |....X..|  |.....X.|  |......X|

Finally, we connect the upper and lower triangles with $n-2$ Z's. There are many choices for how to do this. We'll put them in $z=1$, $y=n-2$, $1 \le x \le n-2$.

|......X|  |x......|  |.x.....|  |..x....|  |...x...|  |....x..|  |....Ax.|
|.....XA|  |OZZZZZX|  |xO....O|  |.xO....|  |..xO...|  |...x...|  |...Ax..|
|....XA.|  |.....X.|  |......X|  |x......|  |.x.....|  |..x....|  |..Ax...|
|...XA..|  |....X..|  |....OX.|  |O....OX|  |xO....O|  |.x.....|  |.Ax....|
|..XA...|  |...X...|  |....X..|  |.....X.|  |......X|  |x......|  |Ax.....|
|.XA....|  |..X....|  |..OX...|  |...OX..|  |....OX.|  |.....OX|  |x.....O|
|XA.....|  |.X.....|  |..X....|  |...X...|  |....X..|  |.....X.|  |......X|

In total, this configuration contains $n^2$ X's, $2n-3$ A's, $n-2$ Z's, and $\lfloor (n-1)^2/4\rfloor +\lfloor(n-2)^2/4 \rfloor = {n-1 \choose 2}$ O's, a total of $\frac 32 n^2 + \frac 32 n - 4$.

Therefore,

$$ \frac 32 n^2 - \frac 12 \le \min |C_3(n)| \le \frac 32 n^2 + \frac 32 n - 4.$$

$\endgroup$
2
  • 1
    $\begingroup$ Very satisfying to see such a nearly tight result, with the constant $\frac{3}{2}$ hardly evident at the start, especially as it was truly a community effort! $\endgroup$ Aug 4, 2012 at 16:55
  • $\begingroup$ $n-3$ Z's can be used instead, lowering the upper bound by $1$. $\endgroup$ Aug 4, 2012 at 18:12
8
$\begingroup$

For the main case ($3\times 3\times 3$), here is a solution using 13 blocks:

 1 1 0   0 0 1   0 0 1 
 0 1 0   1 1 1   0 1 0
 0 1 1   1 0 0   1 0 0


Update: For the $4\times 4\times 4$ case, here is a solution using only 24 blocks, which is optimal according to the $\frac{3}{2}n^2-\frac 12$ lower bound provided by Douglas and Gjergji.

  0 1 1 1
  0 1 0 0
  1 1 0 0
  1 0 0 0

  1 0 0 0
  1 1 1 1
  0 0 1 0
  0 0 1 0

  1 0 0 0
  0 1 0 0
  0 0 0 1
  0 1 1 0

  1 0 0 0
  0 1 0 0
  0 0 0 1
  0 0 1 1


(Click on the edit history for my previous solutions, which used first 27 blocks, then 26, then 25, and now 24.)

$\endgroup$
4
  • 4
    $\begingroup$ $13$ is indeed the best possible for $n=3$ by the lower bound $\frac 32 n^2 - \frac 12 = 13$. $\endgroup$ Aug 4, 2012 at 13:47
  • 1
    $\begingroup$ For your $4\times 4\times 4$ example, you can get rid of one more cube: either the first cube in the second row of your first layer, or the third cube in the fourth row of the first layer. $\endgroup$
    – ARupinski
    Aug 4, 2012 at 15:20
  • 1
    $\begingroup$ This type of construction should also generalize up to higher dimensions to give an upper bound that is $O(2n^{d-1})$ which is one order of magnitude better than my upper bound. $\endgroup$
    – ARupinski
    Aug 4, 2012 at 15:23
  • $\begingroup$ And now I've changed it further, to get down to 24. But now there is no pretense of a general method... $\endgroup$ Aug 7, 2012 at 3:56
4
$\begingroup$

Edited image to correct an error, as per Michael Biro's comment

Here are a few small cases which can each be done with $\frac{3}{2}(n^2+n) - 5$ blocks. They're built by placing $n^2$ "X" blocks to give the correct shadows, then placing $\frac{n^2+n}{2} - 3$ "O" blocks to connect each "X" block to one of two components, and finally $n-2$ "Z" blocks to put the components together. The third example places the "Z" blocks in a funny way to indicate that there are many options available. They could just as easily have been placed in the second column of the second layer, like they were in the $n=4$ case.

Not sure if this will be helpful to you, because I don't have an argument that you can do this for every $n$, but the placement of "O" blocks seems to just repeat the previous levels (a similar arrangement works for n=7 just by copying the "above/below diagonal" positions from n=5) and you can certainly show that $n-2$ "Z" blocks will suffice to connect the two components, since there are many paths of length $n-1$ between "X" diagonals within a layer, and you only need a single "O" on any one of them. Maybe someone can extract an algorithm from this and make it precise. The OEIS didn't give any results for "1,3,13,25" where the next number was at most 40, so maybe 25 is not the best, or maybe it's not known.

$\endgroup$
4
  • 1
    $\begingroup$ Is your $C_3(4)$ example connected? It seems like the component of $3$ in the bottom right corner of the first picture never connects to the rest. $\endgroup$ Aug 4, 2012 at 14:42
  • $\begingroup$ Ah, good eye, you're absolutely correct. The "O" in the first row should be in the second row to connect everything. Blame it on bad eyesight translating from paper to Excel. $\endgroup$ Aug 4, 2012 at 18:16
  • $\begingroup$ Zack, could you clarify what you mean? Are you proposing to add another block, or merely to move a block? Could you draw your new configuration? $\endgroup$ Aug 7, 2012 at 2:50
  • $\begingroup$ @Joel: Just to move the block to the right and down. I've put up an image with the change. $\endgroup$ Aug 7, 2012 at 4:06
3
$\begingroup$

Here is a way to get $26$ for the $C_3(4)$ case, and $2(n^2-n) + 2$ in general.

In the bottom level, add $4n-5$ cubes around the outside, leaving one out adjacent to a corner. For the second level, fill in the interior $(n-2)^2$ cubes, add the two diagonal corners (one of which is next to the missing cube from the base), and then put a cube in the missing cube's column. For the remaining $n-2$ levels, stack on the diagonal.

 1 1 1 1  1 0 0 0  1 0 0 0  1 0 0 0 
 1 0 0 1  0 1 1 0  0 1 0 0  0 1 0 0
 1 0 0 1  0 1 1 0  0 0 1 0  0 0 1 0
 1 1 0 1  0 0 1 1  0 0 0 1  0 0 0 1

In general, that works out to $C_3(n) \leq (4n-5) + (n-2)^2 + 3 + n(n-2) = 2(n^2 - n) + 2$

Edit: My $26$ bound for $C_3(4)$ has since been improved, but here is an optimal $C_3(5) = 37$ arrangement.

1 0 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
0 0 0 0 1

0 1 0 0 0
0 1 0 0 0
1 1 1 1 1
0 0 0 1 0
0 0 0 1 0

0 0 1 0 0
0 0 1 1 1
0 0 1 0 0
1 1 1 0 0
0 0 1 0 0

0 0 0 1 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 1 0 0 0

0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0
$\endgroup$
2
  • $\begingroup$ Very clever, Michael! :-) $\endgroup$ Aug 4, 2012 at 15:43
  • $\begingroup$ Still no arrangement of $(3n^2-1)/2$ for general $n$, but this solution is symmetric enough that I'm somewhat confident that it's possible. Maybe the arrangements will be different for $n$ even, vs odd? $\endgroup$ Aug 7, 2012 at 15:31
2
$\begingroup$

For $C_3(n)$ an absolute upper bound is $3(n-1)^2+3$ which can always be attained by taking the cubes on three faces adjacent to a given corner, removing the corner itself, and removing all but one cube on each edge incident to the corner. Unfortunately, this gives a bound of 15 in the $n=3$ case., so does not improve your particular case. Somewhat generalizing this construction to higher dimensions, for $d\geq 4$ one gets an absolute upper bound for $C_d(n)$ of

$[n^d-(n-1)^d]-d(n-1)+1$

To prove this always works, consider $C_d(n)$. We will replace each cube by its center point and consider the lattice as in Joseph's previous question which he references.

WLOG, let one corner of $C_d(n)$ be centered at the origin. The lines we want to block have $(d-1)$ coordinates fixed and one coordinate which varies. Now consider the set of all cubes whose center has at least one coordinate equal to 0; this is exactly the set of all cubes lying on one (or more) $(d-1)$-dimensional faces adjacent to our origin cube. There are $[n^d - (n-1)^d]$ such cubes. Now remove all cubes along the edges incident to our cube centered at the origin, this removes $d(n-1)+1$ cubes leaving the set $S_d(n)$ which consists of all cubes with at least one and at most $(d-2)$ coordinates equal to 0. The only lines which do not intersect this set are those which have $(d-1)$ fixed coordinates equal to 0, i.e. the lines incident to our cube centered at the origin. Since cubes are adjacent iff they differ in exactly one coordinate, it is easy to check that the $S_d(n)$ is connected for $d\geq 4$ but not connected for $d=3$. So we need only add our cube centered at the origin, and one cube adjacent to it to block the remaining lines while ensuring the entire collection is connected.

Note that if the above held for $d=3$, one could use it to push our bound down from Joseph's 15 to 14; however the set $S_3(n)$ consists of 3 disconnected pieces and so the reasoning leading to this formula fails. However this formula does imply that as $d$ or $n$ gets large, one can block all lines with an arbitrarily small fraction of all available cubes.

There is probably a way to do some more inclusion-exclusion to further eliminate some particular pieces of $S_d(n)$ as unnecessary for blocking purposes and thereby further reduce our bound, but offhand I don't see it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.