## Solution To Puzzle #107: The Longest Path

I was surprised to see relatively fewer answers for this puzzle. I received two partially correct answer and one fully correct answer. Anisha, my 11 year old, correctly pointed out the maximum length, and so did Mayank Aggarwal from California. Only Suman Saraf gave a proof of the maximum path – well done all!

Here is the answer – You can have a maximum length of 34. A brief logic is as follows, though the video does a better job of explaining this:

– Color the intersections as black and white so that no two adjacent intersections are of the same color (like a chess board, where the intersections are the squares) – you have a 6×6

– Since there are 36 intersections, and A & B are part of the path, there can be a maximum path of 35

– However, since A and B will always be the same color (either black and white), one needs an even number of steps to go from A to B

– Therefore maximum path length can be 34

Attaching the answer in the following video:

Hope you all enjoyed the puzzle!

This entry was posted in Solution and tagged , , . Bookmark the permalink.