Packing lines in a hypercube, Discrete Mathematics 117 (1993) 1077112.
We characterize the n-tuples (a 1, _, a, ) for which one can find ai lines in the ith direction in the n-cube, i= 1, ., n, so that all lines are disjoint.
Let Q"= (0, l}" denote the n-dimensional hypercube; we shall refer to it simply as the n-cube. An i-line (or a line in the ith direction) in Q" is a pair of vertices of Q" which differ in the ith coordinate and agree in all other coordinates. We address the following question: Given n nonnegative integers a,, . . . . an, under what conditions can one find ai i-lines in Q', for i = 1, , n, so that all lines are disjoint? When this is possible, we say that the n-tuple (a,, , a,) is implementable.
An obvious necessary condition for implementability is 1 r= 1 aid 2"-'. To see that this condition is not sufficient, try to find two disjoint lines in the 2-cube, one in each direction. We shall treat first the case when I;= i Ui=2"-l.
In this case, a system of lines as required would necessarily form a partition of Q".
Theorem 1. Suppose that n 3 2 and C I= 1 ai = 2"-'. A necessary and su$icient condition for (a,, . , a,,) to be implementable is that all ai, i= 1, . . . . n, be even.