The question:
In how many ways can you arrange the numbers $1$ to $8$ in a circle so that neighboring numbers are relatively prime? Can you generalize for $1$ to $n$?
It's fairly easy to list all possible arrangements for the numbers $1$ to $n$ when $n \leq 7$; however, beyond this it is hard to do it by hand.
I've tried approaching the problem in three ways, but none of them have got me any success (for either the general case or the special one).
Consider the graph with vertices numbered $1, 2, \dotsc, n$. In this graph, there is an edge between two distinct vertices iff their numbers are relatively prime. For example, $1$ will be connected to all other vertices, $2$ to all odd numbers, etc. Then, the number of Hamiltonian cycles in this graph is our answer.
Another way to look at the problem is by recursion. Given an arrangement of $n-1$ vertices, the $n^{\text{th}}$ vertex (with the number $n$) can be inserted on an edge where both neighbors are relatively prime to it. Thus the edge will be split into two. To solve the problem, we have to solve the recurrence. But note that the initial arrangement of $n-1$ vertices does not have to have all neighbors relatively prime; the condition is that either all neighbors are relatively prime, or there is exactly one relatively non-prime pair such that both numbers are relatively prime to the inserted number $n$.
A third way is by making 'trees' for the choices of each next vertex. We start at $1$: there are $n-1$ branches for each of the $n-1$ remaining numbers. For each of the branches, there are further branches for each of the remaining numbers relatively prime to that branch, and so on. Counting the number of ways to get to the bottom of this tree will give us an answer. Edit: As in @Mark Main's answer, this approach is equivalent to making 'option sets' for a given number: starting from 1, choose any number in its option set, then choose any number from that number's option set, and so on. This is a good way to deal with the problem programmatically, but I can see no other advantage for the solution.
Sorry for making it so long, but I thought it's better if I put up all my attempts. Please add more specific tags if you can, I couldn't find any.
No comments:
Post a Comment