## Le Monde puzzle [#1011]

**A**n combinatoric Le Monde mathematical puzzle (with two independent parts):

Given the following grid,

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

**T**he 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).

June 9, 2017 at 1:34 am

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

June 9, 2017 at 8:12 am

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

June 9, 2017 at 5:39 pm

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