Minimal blocking objects with shadows like a cube - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T08:38:47Z http://mathoverflow.net/feeds/question/103882 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube Minimal blocking objects with shadows like a cube Joseph O'Rourke 2012-08-03T16:50:12Z 2012-08-07T07:00:04Z <p>This is a more geometric version of the previous question, <a href="http://mathoverflow.net/questions/103719/" rel="nofollow">"Lattice-cube minimal blocking sets"</a>. I will first specialize to $\mathbb{R}^3$, $d=3$.</p> <p>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 <em>minimal blocking object</em> $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.</p> <p>$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$.</p> <p>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: <br /> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/BlockingObj15.jpg" alt="Blocking Object"> <br /></p> <p>$\left[\begin{array}{ccc} 0 &amp; 1 &amp; 1 \\ 0 &amp; 1 &amp; 0 \\ 1 &amp; 1 &amp; 0 \end{array}\right] \hspace{0.25 in} \left[\begin{array}{ccc} 0 &amp; 1 &amp; 0 \\ 1 &amp; 1 &amp; 1 \\ 0 &amp; 1 &amp; 0 \end{array}\right] \hspace{0.25in} \left[\begin{array}{ccc} 1 &amp; 0 &amp; 0 \\ 1 &amp; 1 &amp; 1 \\ 0 &amp; 0 &amp; 1 \end{array}\right]$</p> <p>Fifteen seems excessive&mdash;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.</p> <p><b>Addendum</b>. Here is Joel's 13-cube blocker from his answer below: <br /> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/BlockingObj13.jpg" alt="Joel: 13 cubes"> <br /></p> http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube/103907#103907 Answer by ARupinski for Minimal blocking objects with shadows like a cube ARupinski 2012-08-04T02:14:26Z 2012-08-04T02:20:12Z <p>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</p> <p>$[n^d-(n-1)^d]-d(n-1)+1$</p> <p>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.</p> <p>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. </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube/103908#103908 Answer by Joel David Hamkins for Minimal blocking objects with shadows like a cube Joel David Hamkins 2012-08-04T02:43:22Z 2012-08-07T03:25:00Z <p>For the main case ($3\times 3\times 3$), here is a solution using 13 blocks:</p> <pre> 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 </pre> <p><br> <b>Update: </b> 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.</p> <pre> 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 </pre> <p><br> (Click on the edit history for my previous solutions, which used first 27 blocks, then 26, then 25, and now 24.)</p> http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube/103912#103912 Answer by Michael Biro for Minimal blocking objects with shadows like a cube Michael Biro 2012-08-04T04:35:41Z 2012-08-07T07:00:04Z <p>Here is a way to get $26$ for the $C_3(4)$ case, and $2(n^2-n) + 2$ in general. </p> <p>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.</p> <pre> 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 </pre> <p>In general, that works out to $C_3(n) \leq (4n-5) + (n-2)^2 + 3 + n(n-2) = 2(n^2 - n) + 2$</p> <p>Edit: My $26$ bound for $C_3(4)$ has since been improved, but here is an optimal $C_3(5) = 37$ arrangement.</p> <pre> 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 </pre> http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube/103921#103921 Answer by Zack Wolske for Minimal blocking objects with shadows like a cube Zack Wolske 2012-08-04T08:40:28Z 2012-08-07T04:03:39Z <p><img src="http://s17.postimage.org/5vkzbmnsf/Blocking_Cubes2.png" alt=""></p> <p><strong>Edited image to correct an error, as per Michael Biro's comment</strong></p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube/103934#103934 Answer by Douglas Zare for Minimal blocking objects with shadows like a cube Douglas Zare 2012-08-04T11:00:57Z 2012-08-04T16:12:20Z <p><strong>Lower bound:</strong></p> <p>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, </p> <p>$$n^{d-1} \le c - \frac{c-1}{d} = c \frac{d-1}{d} + \frac 1d$$ </p> <p>$$c \ge \bigg(\frac {d}{d-1}\bigg)n^{d-1} - \frac {1}{d-1}.$$</p> <p>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.</p> <p><strong>Upper bound ($d=3$):</strong></p> <p>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$.</p> <pre><code>|......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| </code></pre> <p>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.</p> <p>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. </p> <pre><code>|......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| </code></pre> <p>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 <a href="http://oeis.org/A002620" rel="nofollow">A002620</a>). </p> <p>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. </p> <pre><code>|......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| </code></pre> <p>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$. </p> <pre><code>|......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| </code></pre> <p>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$. </p> <p>Therefore, </p> <p>$$\frac 32 n^2 - \frac 12 \le \min |C_3(n)| \le \frac 32 n^2 + \frac 32 n - 4.$$</p>