Twelve bugs – two of six different species – want to find their respective mates. Your job is to connect A to a, B to b, …, and so forth using an unbroken path between each bug pair. Your lines must travel through the center of each square in the array, and you can only travel up, down, left and right (not diagonally).
Because the bugs leave behind poison trails, no path can cross another, and no path can cross itself. When you are finished, every square must have been traversed once and only once.
_ _ _ _ _ _ _
|A|_|B|_|_|_|C|
|_|_|_|_|d|_|_|
|_|_|D|_|_|_|_|
|_|_|_|E|_|_|e|
|_|_|_|F|_|_|_|
|_|_|_|_|_|_|_|
|a|_|_|_|b|c|_|
|f|_|_|_|_|_|_|
Prove whether or not there is a solution.
If you think there is a bug in the problem, can you move EXACTLY one bug EXACTLY one square from its original position (not diagonally) and find a solution? Would it be unique?
The bulk of this problem was created by Clifford Pickover
The following are the proves that the original positions of the bugs are untraversable:
Let's commence in explaining the paths of F. There are either two paths from F to f. It is either to move around b and c in order to reach f or to move directly to f.
Let's assume that bug F takes a short-cut to move directly to f. The movement of the bug will be as follows:
A l l B l c l c l c l C
----------------------------------
a l l l c l d l c l c
-----------------------------------
a l l D l c l c l c l c
-----------------------------------
a l f l f l E l c l c l e
-----------------------------------
a l f l f l F l c l c l c
------------------------------------
a l f l f l f l b l c l c
------------------------------------
f l f l f l f l l c l c
The above diagram shows a direct movement of bug F from F to f. The numerous letters f as shown above reflect the possible movements of bug F from F to f through a direct path. After moving the bug, F, to f, advances the bug C from C to c. The above diagram shows the possible paths of the movements of bug C. In any movement of bug C from C to c, it is obvious from the diagram that the bug C has blocked the way of the bug E to advance from E to e. Thus, there is no way that the routes of all the bugs can be traversable through the direct movement of bug F from F to f due to the blocking of route of bug E from E to e.
The diagram below shows the shortest way of movement for bug F to commence from F to move around c and b in order to reach f:
A l l B l l l l C
-----------------------------------
l X l l l d l l
-----------------------------------
l l D l l l l
-----------------------------------
l l l E l l l e
-----------------------------------
l l l F l f l f l f
-----------------------------------
l l l l f l f l f
-----------------------------------
a l l l l b l f l f
-----------------------------------
f l f l f l f l f l f l f
Now, bugs B and C have to advance through the letter, X, as shown in the diagram in order to advance to b and c due to the movement of bug F at the right hand bottom has blocked the paths of bugs B and C. As the question only allows one to traverse once only instead of two, there is no way for bugs B and C to cross over the same letter of , X, as indicated above more than once. Thus, there is no way for bugs B & C to traverse to b & c due to X is the only path for bugs B & C to traverse.
From the above elaboration, it is certain that it is impossible for all the bugs to traverse in the original diagram as shown in the question.
As the puzzles experts, Mr. Erik O, Hugo and Mark have elaborated upon the movement of a bug to cause all the bugs to be traversable, I need not to elaborate further.
Thanks
Edited on April 27, 2005, 4:37 pm
Edited on April 27, 2005, 4:40 pm
Solution
