Problems & Puzzles:
Puzzles
Puzzle 229.
Primes and Hypercubes
Tony
D.
Noe
sent the following puzzle:
Here is
a prime puzzle for those who can work in higher dimensions. For which n
can the numbers from 1 to 2^n be arranged at the vertices of an
ndimensional hypercube such that each of the n*2^(n1) edges connects two
numbers that sum to a prime? There are simple solutions in dimensions 1
and
2:
1:
1  2
2:
1  2


4
 3
A good
place to start
with
hypercubes
is
http://mathworld.wolfram.com/Hypercube.html
Mathematically, for an ndimensional cube, the coordinates of each vertex
are (x1,x2,...,xn), where each xi is either 0 or 1. Two vertices are
connected by an edge if the coordinates of the two points are different in
only one position. For example, in 4space, the two points (0,0,0,0) and
(1,0,0,0) are connected, but the points (1,0,0,0) and (0,0,0,1) are not
connected. All the edges are parallel (or perpendicular) to the
coordinate axes; there are no diagonal edges.
Question:
1. What is the
answer for higher dimensions?
2. If there is
more than one solution for a particular n, count the essentially different
solutions.
Solution:
Andrew Rupinski has
proved (17/8/03) that no solution exist for 3, 4 and 5Cube. As
maybe you have already devised the proof for a 3Cube is too elemental. I
will show only the Andrew's proof for a 4cube because is not too large.
If you are interested in the Andrew's proof for a 5Cube I can send
it to you on request.
Consider the possible adjacencies of each vertex. Since
each vertex of a 4cube is connected to 4 other vertices, consider
vertex 14 which connects to exactly 4 other vertices: 3, 5, 9, and 15.
Let (0,0,0,0) = 14 and without loss of generality, assume:
(1,0,0,0) = 3
(0,1,0,0) = 5
(0,0,1,0) = 9
(0,0,0,1) = 15
Now consider possible values for the 3 vertices
(1,1,0,0) = x
(0,1,1,0) = y
(0,1,0,1) = z
Then we must have distinct x, y, z such that {3,5,14,x},
{5,9,14,y}, and {5,15,14,z} are all completions. Upon inspection, we see
that:
x = 2 or 8
y = 2 or 8
z = 2 or 8
This is clearly impossible, hence there are no prime
4cubes.
***
Giovanni Resta
wrote (22/8/03) the following small report:
I only found a solution for the cube (8 vertices)
when the numbers start from 0 instead of 1. No solutions for 4cube and
5cube. A very coarse estimation suggest that with high probability there
are no solutions for larger dimensions.
***
