Arranging Drilled Unit Cubes into a Rectangular Prism Without Breaking the Thread

Question

Given positive integers p, q, and r, we have $p \cdot q \cdot r$ unit cubes. Each cube has a hole drilled along one of its space diagonals. These cubes are then strung onto a very thin thread of length $p \cdot q \cdot r \cdot \sqrt{3}$, resembling beads on a string. The task is to arrange these unit cubes into a rectangular prism with side lengths $p$, $q$, and $r$ without breaking the thread.

The problem can be divided into two parts:

a) For which values of $p$, $q$, and $r$ is it possible to arrange the cubes into the prism without breaking the thread?

b) For which values of $p$, $q$, and $r$ can this arrangement be done in such a way that the beginning and end of the thread come together?

I have attempted to visualize and manipulate various configurations but have yet to devise a systematic approach to solve this problem. Does anyone have ideas on how to tackle this problem, or are there any similar problems or theories that might shed light on a possible solution? Any guidance or references to relevant mathematical concepts would be greatly appreciated.

Answer 1

We label the coordinates of a unit cube vertex by an integer vector $(x, y, z)$.

We easily see that an invariant for the vertices visited by the thread is given by $(y-x \text{ mod } 2, z-x \text{ mod } 2)$ and that only two vertices of each unit cube share the same invariant. There are four possible invariants: (even, even), (even, odd), (odd, even) and (odd, odd).

Thus, all the visited vertices will share the same invariant. Because for each cube, there will be only one diagonal such that the two endpoints satisfy this invariant, we know exactly in which diagonal the thread will pass. So the problem reduces to find an Eulerian path/cycle in the graph induced by the diagonals with endpoints satisfying the invariant. We need to find such an Eulerian path/cycle in one of the four possible graphs – one for each possible invariant.

For each vertex, the degree in the graph will be equal to the number of cubes meeting at this vertex. We see that all the vertices will induce an even degree, except for the $8$ corner vertices.

We can do a case analysis on the parity of $p, q$ and $r$:

• $p, q, r$ odd: The four possible invariants will all contain two corners, so no matter which invariant we choose, we will have two odd-degree vertices, thus we can only find an Eulerian path.
• two odd, one even: Same thing.
• one odd, two even: Two invariants will contain four corners each and the two other invariants will contain no corner. By choosing one of these latter invariants, we can find an Eulerian cycle.
• three even: One invariant contains all the corners, the three other ones will yield an Eulerian cycle.

---

A constructive solution:

• $(p, q, r)$ odd: Start from $(x, y, z) = (0, 0, 0)$ (suppose that the prism of cubes has a corner in $(0, 0, 0)$ and is in the main orthant): you do a zigzag in the rectangle $p\times q\times 1$ (like if you are doing a Hamiltonian path in a grid). this rectangle has an odd number of cubes, so you go up or down an odd number of times, hence you end your path with the $z$-coordinate equal to $1$. You can then do the same for each $p\times q\times 1$ until you reach the opposite corner.

• two odd, one even: Same thing, but you need to suppose WLOG that $p$ and $q$ are the odd values.

• one odd, two even: Suppose WLOG that $p$ and $q$ are the even values. Remove the $1\times 1\times r$ column with a corner in $(0, 0, 0)$. Do the same thing as before, except that in slice is not a rectangle, but a rectangle with a missing square. You start from the vertex $(1, 0, 0)$ and find a Hamiltonian path going from the starting cube square (that is adjacent to the missing square) to the other cube adjacent to the missing square. Like before, there is an odd number of cubes in each slice, so you can go up to the next slice after that. In the end, you go down the $1\times 1\times r$ column to close the loop.

• three even: Same thing.

Answer 2

Here are two examples obtained by considering a "light ray bouncing on mirror borders".

Fig. 1 : Eulerian path : the first diagonal (numbered 1 ) connects vertex $(0,0,0)$ to vertex $(1,1,1)$. As can seen by following the diagonals' numbering from 1 to $2 \times 3 \times 5 = 30$, every cube is traversed once. The complete path isn't closed (the last diagonal, numbered 30, isn't connected to the first one). For a Eulerian circuit, see Fig. 2.

Fig. 2 : Eulerian circuit in the case $p=10,q=3,r=4$. Initial vector $(1,1,1)$ as before. The initial point $(1,0,0)$ (red point) is also the final point.

Remark : "Bouncing light rays" is a way to obtain a solution, but there are solutions which can be obtained in a different way as can be seen in the answer by @caduk.

Here is the Matlab program with which Fig. 1 and 2 have been constructed :

 Lx=2;Ly=3;Lz=5;
 sr=@(x)(-2*x+1); % sign reversal function : 1 -> -1, 0 -> 1
 P=[0,0,0]; % initial point
 V=[1,1,1]; % initial vector
 N=Lx*Ly*Lz; % number of steps
 A=[P]; % array containing the coordinates of points of the path
 for k=1:N;
    Pn=P+V; % new point = old point + vector
    M=(Pn+P)/2; % midpoint
    text(M(1),M(2),M(3),num2str(k)); hold on;
    P=Pn ;
    A=[A;P]; % appending new point
    % 3 booleans managing limit cases :
    Bx=(mod(P(1),Lx)==0); % Bx=1 iff abscissa of current point = 0 or L1
    By=(mod(P(2),Ly)==0); % By=1 iff ordinate ...
    Bz=(mod(P(3),Lz)==0); % Bz=1 iff altitude ...
    V=V.*sr([Bx,By,Bz]); % possible reflection = sign reversal on some coord. 
 end;
 plot3(A(:,1),A(:,2),A(:,3),'-ob');axis([0,L1,0,L2,0,L3]);axis equal;