7
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ This is an interesting question. You ask "how to tackle this problem". My answer would be to start with what happens for small values of the parameters. When two of them are $1$ the answer is easy. When one of them is $1$ the problem is almost planar. What happens with small examples then? Can you work out the $2,2,2$ case by brute force? $\endgroup$ Mar 3 at 15:06
  • $\begingroup$ Good question... sounds like you are looking for an Hamiltonian Path in a 3D Grid... $\endgroup$ Mar 3 at 15:22
  • $\begingroup$ @MichaelSchreiber A Hamiltonian path using the long diagonals of the cells in a 3D grid. $\endgroup$ Mar 3 at 15:31
  • $\begingroup$ And since you need to keep track of not just the cells, but the vertices, and not all vertices will be used, I don't see how you can formulate it as a Hamiltonian path problem. $\endgroup$ Mar 3 at 15:37
  • $\begingroup$ @RobertIsrael If you represent a position by an integer vector $(x, y, z)$, an invariant is $(y-x\text{ mod } 2, z-x \text{ mod } 2)$, and only two vertices of each unit cube share the same invariant, so we can reduce to some kind of Hamiltonian path problem. $\endgroup$
    – caduk
    Mar 3 at 21:15

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

enter image description here

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.

enter image description here

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;
$\endgroup$
3
  • 1
    $\begingroup$ If $p, q,r$ share some common factors, you are not guaranteed to visit every cube. Think of it in 2D, it's easier. $\endgroup$
    – caduk
    Mar 3 at 22:43
  • 1
    $\begingroup$ I agree that the examples you exhibited are valid solutions, I was just pointing out that this would not work as a general solution, because for some values of $p,q,r$, no matter where we start, we will not visit every cube with the bouncing light strategy. take $p=q=4, r=1$ for example. $\endgroup$
    – caduk
    Mar 3 at 23:33
  • $\begingroup$ Cultural corner : "corner cubes" laser reflectors on the moon : see paragraph "How Lunar laser ranging works" in this document. $\endgroup$
    – Jean Marie
    Mar 4 at 17:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .