Difference between revisions of "Longest road"

From Math Puzzle Wiki
Jump to: navigation, search
Line 1: Line 1:
 +
==Puzzle==
 +
 
Grid-town USA, in addition to its excellent donut shops, is known for its precisely laid out grid of streets and avenues.  The town has 12 avenues running east/west, creatively named 1st, 2nd, etc.  There are also exactly 12 streets (running north/south) also named 1st, 2nd, 3rd, and so on.   
 
Grid-town USA, in addition to its excellent donut shops, is known for its precisely laid out grid of streets and avenues.  The town has 12 avenues running east/west, creatively named 1st, 2nd, etc.  There are also exactly 12 streets (running north/south) also named 1st, 2nd, 3rd, and so on.   
  
 
Suppose you are a cab driver in Grid-town.  You pick up your fair at the corner of 1st and 1st and are instructed to travel all the way across town, to 12th and 12th.  Of course you want to maximize the length of the trip.  However, your passenger will get suspicious if you leave town or cross through any intersection more than once.  What is the longest path you can take?
 
Suppose you are a cab driver in Grid-town.  You pick up your fair at the corner of 1st and 1st and are instructed to travel all the way across town, to 12th and 12th.  Of course you want to maximize the length of the trip.  However, your passenger will get suspicious if you leave town or cross through any intersection more than once.  What is the longest path you can take?
 +
 +
==Help==
  
 
{{Hint| You could color the intersections in a checkerboard pattern.  What can you say about the parity of the length of any path?}}
 
{{Hint| You could color the intersections in a checkerboard pattern.  What can you say about the parity of the length of any path?}}
Line 8: Line 12:
 
{{Needs solution}}
 
{{Needs solution}}
  
[[Category:New]]
+
==See also==
[[Category:MCP]]
+
 
 +
[[Checker board and dominoes]]
 +
 
 +
[[Checkerboard cut-up]]
 +
 
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]
 
[[Category:Parity]]
 
[[Category:Parity]]
 
[[Category:Graph theory]]
 
[[Category:Graph theory]]

Revision as of 16:54, 14 July 2013

Puzzle

Grid-town USA, in addition to its excellent donut shops, is known for its precisely laid out grid of streets and avenues. The town has 12 avenues running east/west, creatively named 1st, 2nd, etc. There are also exactly 12 streets (running north/south) also named 1st, 2nd, 3rd, and so on.

Suppose you are a cab driver in Grid-town. You pick up your fair at the corner of 1st and 1st and are instructed to travel all the way across town, to 12th and 12th. Of course you want to maximize the length of the trip. However, your passenger will get suspicious if you leave town or cross through any intersection more than once. What is the longest path you can take?

Help

Hint
You could color the intersections in a checkerboard pattern. What can you say about the parity of the length of any path?
Answer
142 blocks

See also

Checker board and dominoes

Checkerboard cut-up