For positive integers $p$, $q$ and $r$ we are given $p \cdot q \cdot r$ unit cubes. We drill a hole along the space diagonal of each of these cubes and then tie them to a very thin thread of length $p \cdot q \cdot r \cdot \sqrt{3}$ like a string of pearls. We now want to construct a cuboid of side lengths $p$, $q$ and $r$ out of the cubes, without tearing the thread. a) For which numbers $p$, $q$ and $r$ is this possible? b) For which numbers $p$, $q$ and $r$ is this possible in a way such that both ends of the thread coincide?
Problem
Source: Bundeswettbewerb Mathematik 2024, Round 1 - Problem 4
Tags: combinatorics, combinatorics proposed
29.03.2024 22:19
Ad a) This is possible for all positive side lengths p, q, r. Ad b) This is possible if and only if at least two of the positive side lengths p, q, r are even. Cannot post images yet, unfortunately.
06.04.2024 05:58
The answer to a) is all triples, and to b) is all triples with at least two even entries. Consider a $p\times q\times r$ cuboid, where the vertices of the unit cubes are the integer points from $(0,0,0)$ to $(p,q,r)$. We classify these integer points $(x,y,z)$ into four classes, according to the parity of $x-y$ and $x-z$. Note that if such an arrangement is possible, then the parity of each of $x$, $y$ and $z$ changes on every step while walking along the thread, so the class of the integer points used does not change. Observe that every integer point, except for the eight corners of the cuboid, is incident to an even number of unit cubes. There is a class $C$ that has at most two corners of the cuboid. Moreover, if at least two of $p,q,r$ are even, then there is a class which does not contain any corner. Consider the graph $G$ on the integer points of class $C$, where a pair of vertices is joined by an edge if it shares a unit cube. This graph is connected, and every vertex except at most two has even degree. Therefore there exists a Euerian trail or an Eulerian circuit, in each case. By arranging the thread along this trail, we get the desired constructions. To prove that b) is impossible if two of $p,q,r$ are odd (say $p$ and $q$), cut the cuboid along the plane $z=1/2$. The thread crosses this plane exactly once within each intersected unit cube, for a total of $pq$ times, an odd number. Thus the thread cannot loop, as it starts and ends on different sides of this plane.
28.07.2024 21:10
See https://artofproblemsolving.com/community/c6h220953p1225240.