8
$\begingroup$

Given a three dimensional n×n×n cube containing n^3 cubes of 1×1×1,

Define a cube tube to be a sequence of 1×1×1 cubes from the n×n×n cube such that:

1) No cube appears in the sequence more than once.

2) Each cube in the sequence shares a face with the cube directly after it in the sequence.

Define a cube loop to be a cube tube where the first and last cubes in the sequence share a face.

What is the shortest cube tube such that its projection in any of the three planes is a full n×n square? What about the shortest cube loop?

Example: For n=2 the answer is 6 for both the cube tube and the cube loop.

$\endgroup$
7
  • $\begingroup$ Isn't it 5 for cube tube, n=2? $\endgroup$
    – Avi
    Jan 24, 2020 at 15:05
  • $\begingroup$ @Avi don't think so, check your solution one plane should be missing a square at least. $\endgroup$
    – cmxu
    Jan 24, 2020 at 15:07
  • $\begingroup$ @Avi For n=2, we can remove the two corner pieces, leaving a cube loop of length 6, but if we remove any other square then one of the three planes will not have a full n×n square projection. $\endgroup$
    – gyancey
    Jan 24, 2020 at 15:07
  • 2
    $\begingroup$ Ah, so the key here is that all planes have a square projection $\endgroup$
    – Avi
    Jan 24, 2020 at 15:10
  • 1
    $\begingroup$ You can decode that simple cipher (it's called rot13) here. $\endgroup$
    – Avi
    Jan 24, 2020 at 22:07

1 Answer 1

2
$\begingroup$

Let me just think aloud a bit here, I think I have most of a solution for cube tubes.

To start, let's try to define the theoretical minimum for this problem. There are 3 planes that have to appear as $n\times n$ squares. Thus, we have to cover $3n^2$ total faces. The first cube you use, no matter where it is will cover $3$ faces, one on each plane of projection. Each subsequent cube you place must share a face with with the previous cube, thus it can cover at most $2$ faces. Thus, if $k_n$ is the minimum number of cubes needed for the cube tube in a cube of size $n$. Then we know that $$3 + 2(k_n-1) = 3n^2$$ Solving this, and accounting for fractional cubes, we find that $k_n = \lceil{\frac{3n^2-1}{2}}\rceil$. We can observe that $k_1 = 1$ and $k_2 = 6$. This is what we would expect from our known minimum solutions.

After this, I'm a bit less sure.

Now is where I think my solution is missing something. So the idea is some sort of inductive argument that I can create the minimum by taking a solution from a cube of size $n$ and use it to construct a solution of size $n+1$. You simply need to pad each of the faces by 1. If you start on a corner (which you can always ensure by this method) you can add thee 'lines' of cubes making two L shapes which fills in the edges this would cost $(n+1) + n + n + 1 = 3n+2$ cubes where the first three terms come from the lines, and the last comes from needing one cube to connect from the corner of the previous shape. However, we know that the minimum needed should be $$k_{n+1} = \frac{3(n+1)^2 -1}{2} = \frac{3n^2 + 6n + 3 - 1}{2} = k_n + 3n + \frac{3}{2}$$ Thus, every other iteration my solution will exceed the minimum by another cube and this builds up, so I don't know if my solution is minimal.

Let me know if anyone has any ideas or if I've made some mistake here.

$\endgroup$
1
  • $\begingroup$ I can comment on your minimum right off; I'll have to look more carefully at the rest. This is, indeed, the minimum needed for any face-connected set of cubes, and is equal to the following OEIS sequence. oeis.org/A032528 Such a set can be constructed for any n, I think, but it won't be a tube, but this is a whole other puzzle. $\endgroup$
    – gyancey
    Jan 24, 2020 at 15:27

Your Answer

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

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