# Cube Tubes & Cube Loops

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.

• Isn't it 5 for cube tube, n=2? – Avi Jan 24 '20 at 15:05
• @Avi don't think so, check your solution one plane should be missing a square at least. – cmxu Jan 24 '20 at 15:07
• @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. – gyancey Jan 24 '20 at 15:07
• Ah, so the key here is that all planes have a square projection – Avi Jan 24 '20 at 15:10
• You can decode that simple cipher (it's called rot13) here. – Avi Jan 24 '20 at 22:07

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