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 n-dimensional hypercube such that each of the n*2^(n-1) 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 n-dimensional 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 4-space, 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 5-Cube. As maybe you have already devised the proof for a 3-Cube is too elemental. I will show only the Andrew's proof for a 4-cube because is not too large. If you are interested in the Andrew's proof  for a 5-Cube I can send it to you on request.

Consider the possible adjacencies of each vertex. Since each vertex of a 4-cube 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 4-cubes.

***

Giovanni Resta wrote (22/8/03) the following small report:

***