Suppose we're given a 5 by 5 grid squared grid of nodes. We're told the bottom left point is the starting point. The second from the right on the bottom row is the finishing point. We have to travel to every node from the start to the finish, visiting all 25 nodes exactly once. We can travel from each node to a neighbouring node either by going horizontally or vertically one step. We cannot go diagonally.
So what path can we choose? Here is an example of a path we might try:
In that case, although we have successfully travelled from the start to the finish. We have skipped one node.
We can try lots of different paths and each time we find that something goes wrong. We can't get from the start to the finish visiting every node exactly once.
In fact it turns out it can't be done. And here's the proof:
Suppose we lable each node on the grid by its position (1,1) to (5,5). We deem a node to be odd if the sum of its two indices is odd. It is deemed to be even if the sum of its indices is even.
The starting node (1,1) is even since 1+1=2 is even.
The finishing node (4,1) is odd since 4+1=5 is odd.
Every step we take in the path will toggle from odd to even or even to odd, since in each step one index is changed by 1.
If we find a path to get to get from the start to the finish, we'll need to visit 25 nodes, that's 24 steps. So the final node will be even since the starting node was even. However we know that the final node is odd. So we have a contradiction. Hence no such path exists.
So you can spend as long as you like searching for a path, but you won't find one.
No comments:
Post a Comment