Le Monde puzzle [#1011]

An combinatoric Le Monde mathematical puzzle (with two independent parts):

Given the following grid,

  1. What is the longest path from A to B that does not use the same edge twice?
  2.  What is the probability that two minimal length paths from A to B [of length 13] share the same middle [7th] edge?

The first question can be solved by brute force simulation. I ran a very simple minded self-avoiding random walk starting from A and restarting each time a dead-end was reached. (The details are not of capital interest: I entered the above grid as an 8×7 matrix for the nodes and associated with each node a four bit number indicating which edge had been visited. Picking at random among those not yet visited.) The longest path I found along 10⁷ simulations is 51 edges long, confirmed by an additional exploration of the paths on both square grids, separately. The associated path is as follows, the irregular shape being obtained by jittering the node locations towards a better visualisation of the order of the visits.

The second puzzle can be solved directly by looking at the number of paths sharing the seventh edge, which is ¼ (as checked by a further simulation of minimal length random walks).

3 Responses to “Le Monde puzzle [#1011]”

  1. FOULLEY Jean-Louis Says:

    Found the same length (51) as you but with a different path. Did you find in your simulation other paths with the same length?

    • Thank you, Jean-Louis, I did not check the paths themselves, but I would think that switching horizontal and vertical should provide similar versions.

    • update: I reran the R code and found another maximal length path, the differences being on the lower grid.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s