GCD=1 Grid-Path Puzzle #2 (much easier)

This is much easier than 'GCD=1 Grid-Path Puzzle #1'.

Consider an n-by-n grid where the integers 1 to n^2 are arranged such that m is in the ceiling(m/n) row and the (m-1)(mod n)+1 column.

Take the n=4 grid of positive integers:

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

Try to find a permutation of {1,2,...,16} by starting at an integer in the grid, and then moving from integer to adjacent integer up/down/right/left/diagonally (like a King in chess), such that:

*The m_th term of the permutation is relatively prime to the (m-1)_th term.

*Each integer is moved onto once and only once.

*The path does not cross itself.

An example from the 3-by-3 grid:

1 2 3

4 5 6

7 8 9

A solution: 3, 2, 1, 4, 7, 8, 9, 5, 6

I will give my answer to the 4-by-4 case in a couple of days if no one finds a solution sooner. (But, of course, someone will.)

By the way, the reason I have not asked about the case for any 5-by-5 grid, is that there is no solution for this grid. There is no solution, I think, for any n-by-n grid, where n is an ODD integer greater or equal to 5.

Are there solutions for all even n?

Also, as with 'GCD=1 Grid-Path Puzzle #1', perhaps we should have some kind of competition. Who can solve this puzzle for the highest EVEN n?

Thanks, Leroy Quet

You are correct, now odd integer >=5 has a solution.

Proof: Look at the last two columns of any n-by-n grid, where n is odd. Look at the top three rows of this grid. We have: n-1 n 2n-1 2n 3n-1 3n

Now, 2n is not coprime to n and 3n (all multiples of n), and is not coprime to n-1 and 3n-1 (all even, since n is odd), thus in the path, you must either start or end at 2n (since it only has one coprime, adjacent element)

Now look at the 3rd through 5th rows: 3n-1 3n 4n-1 4n 5n-1 5n

Similar reasoning shows the path must begin/end at 4n. Continuing this way shows that the path must begin/end at 6n, 8n, etc. Since the path only has 2 ends, if n is greater than 7, no path can exist (more than two ends needed.

Now look at the full last two columns of the 5x5 case (the only one I have not showin impossible by the above reasoning): 4 5 9 10 14 15 19 20 24 25

Without loss of generality, we can assume the path STARTS at 10, and ENDS at 20 (by the above reasoning, 10 and 20 must be endpoints for any path that works, I am choosing which end has each for convenience), so the path is: 10-9-...-19-20 consider the 5. It must connect to the 4 and the 9 (the only remaining adjacent elements) consider the 25. If must connect to the 19 and the 24. So, the path is now: 10-9-5-4-...-24-25-19-20. But now, there is only one unsued element adjacent to the 15! Therefore, 15 must be at the start or end of the path. This is impossible. Therefore, the 5x5 case cannot be done.

As a side note, for the 3x3 case, as posted,

since we now know you MUST have 6-5 at an end, there are only 4 possible paths: 6-5-3-2-1-4-7-8-9 6-5-9-8-7-4-1-2-3 and their reverses (one of which was given in the example), since once you remove 6 and 5, there are only two ways to even visit every number. It turns out that both of these also satisfy the coprimality condition, since 5 is coprime to every number in the grid (and 3,9 in particular)

10 . . 9 . . 8 . . 7 . . 6 . . 5 . . 4 . . 3 . . 2 . . 1 . .

2-1-6-5-9-10-13-14-15-16-11-12-7-8-3-4 works. 8-7-4-3-2-1-6-5-9-10-13-14-15-16-11-12 is a nice, symmetric solution.

No, there are not.

Let's call an element of a cell 'isolated' if it has only one neighbour with which it has no divisor in common. Because all horizontal neighbours have no divisor in common, the point has to be either in the first or in the last column. But all vertical neighbours in the first column have no divisor in common (gcd ((i-1)*n+1, i*n+1) = gcd((i-1)*n+1, n) = gcd(1, n) = 1) and are thus not isolated (because they each have one or two vertical and one right neighbour which has no divisor in common with them) This leaves us with cells on the right border. We know that for those cells, the left neighbour will have no divisor in common with them; that means that they have to have a common divisor with each of the other 2 or 4 neighbours.

Obviously, the upper and lower neighbours of all cells in that row have the factor n in common; in order to find isolated cells, we'll only have to consider the two diagonal neighbours. That is, the number n*i (that's the rightmost cell in the i-th line) is isolated iff

gcd(n*i, n*i-n-1) = gcd(n*i, n+1) = gcd(i, n+1) != 1 and gcd(n*i, n*i+n-1) = gcd(n*i, n-1) = gcd(i, n-1) != 1.

(the cases i=1 and i=n have to be given exra attention, but as it turns out, neither of those can ever be an isolated point, and that's consistent with the condition just given)

In order to get many possible solutions, both i-1 and i+1 should have small prime factors. Choosing 3 and 5 as the prime factors, the first suitable candidates are n=26 and n=34. And indeed, we find 3 isolated numbers for n=34, namely 34*15, 34*21 and 34*30.

Because every isolated point must be an endpoint of the path and the path has only two endpoints, we can't find a valid path for n=34.

What I wonder now is, whether a solution always exists if there are no more than two isolated points for a given n.

regards,