$n$ mathematicians arrive at a river. On the shores of the river lies a boat, that is strong enough to carry three mathematicians. But, as the mathematicians are crazy, they only want to cross if, at the moment the boat lands on any shore, the number of mathematicians on each side of the river, including in the boat, are coprime.
In one of my previous blogs, , I demonstrated how to convert a river crossing problem to a maze. we are now doing the same, except that as we only have one dimension, we have way more freedom how to build our maze.
let's build it as follows
| 0 |
|
2 |
1 |
4 |
3 |
6 |
5 |
8 |
7 |
10 |
9 |
|
1 |
0 |
3 |
2 |
5 |
4 |
7 |
6 |
9 |
8 |
11 |
Each number represents the number of people on the right riverbank, and blue means the boat is on the right, red means the boat lies on the left. You can see that if the boat lies on the left, going back is sailing one person over, going sideways is siling two people over and going forward is sailing 3 people over. Similar if the boat is on the right, then going back is sailing three people back, sideways for 2 people, and going forward is sailing one person back. Now the fact if we can walk from one end of the tape to the other is dependant on which numbers are unreachable because they lead to coprime states. If two adjacent numbers, or two numbers differing two are blocked, then it is impossible to transverse the tape, otherwise it is possible.
For starters, two numbers are coprime if and only if one of them is coprime to the sum. This means that we just have to compare the number of people on the right bank with the total, and we can forget about the number on the left. Now imagine our original number of mathematicians has at least two different prime factors, $p$ and $q$. According to Bézout's identity, there exist $a$ and $b$ so $ap-bq = 1$. Now, if $ap$ and $bq$ are not in range of 0 to $n$, we can subtract multiples of $n$ until they are. This gives us two numbers, $ap$ and $bq$, that are both coprime with $n$, and are adjacent. This means that if $n$ is not a power of a prime, the mathematicians will never cross the river.
Now if $n$ is a power of a prime other than two, the blocking numbers are spread out far enough so the mathematicians can get to the other side. But if $n$ is a power of 2, then all even numbers will be coprime and, unless $n$ is 4 or 2, it will be impossible to cross the river.