Problem:
In how many ways can you fill a table with the numbers through (each used once) such that all pairs of adjacent numbers (sharing one side) are relatively prime?
Problem:
In how many ways can you fill a table with the numbers through (each used once) such that all pairs of adjacent numbers (sharing one side) are relatively prime?
Solution:
2016
The numbers can be separated into four sets. Numbers in the set can be placed next to anything. The next two sets are and . The number , which forms the final set , can only be placed next to elements of . The elements of each group can be interchanged without violating the condition, so without loss of generality, we can pretend we have three 's, three 's, two 's, and one , as long as we multiply our answer by at the end. The available arrangements are, grouped by the position of the , are:
When is in contact with three numbers:
| 1 | 2 | 3 |
|---|---|---|
| 6 | 1 | 2 |
| 1 | 2 | 3 |
| 6 | 1 | 2 | |||
|---|---|---|---|---|---|
| 1 | 2 | 3 | 6 1 2 <br> 1 1 3 <br> 2 3 1 | 2 | 3 |
| 6 | 1 | 2 | |||
|---|---|---|---|---|---|
| 1 | 2 | 3 | 6 1 | 2 | |
| 1 | 2 | 3 | |||
| 1 | 3 | 2 | 3 | 1 | 2 |