one-way random walks

A rather puzzling riddle from The Riddler on an 3×3 directed grid and the probability to get from the North-West to the South-East nodes following the arrows. Puzzling because while the solution could be reasonably computed with an R code like

sucz=0
for(i in 1:2^12){
  path=intToBits(i)[1:12]
  sol=0
  for(j in 1:12)sol=max(sol,
        prod(path[paz[[j]][paz[[j]]>0]]==01)*
        prod(path[-paz[[j]][paz[[j]]<0]]==00))
  sucz=sucz+sol

where paz is the list of the 12 possible paths from North-West to South-East (excluding loops!), leading to a probability of 1135/2¹², I could not find a logical reasoning to reach this number. The paths of length 4, 6, 8 are valid in 2⁸, 2⁶, 2⁴ of the cases, respectively and logically!, but this does not help as they are dependent.

11 Responses to “one-way random walks”

  1. Carl Witthoft Says:

    Remind me NEVER to visit this town!

  2. Could you give us the paz list, so we can replicate your solution?

  3. […] article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here) […]

  4. Wouldn’t the numerator need to be even? I’d expect that every path starting east would have a similar (symmetric) path starting south. So any set of one-way directions that works if you start going east would would have a corresponding set of one-way directions that would work by staring going south. But 1135 isn’t even, so am I missing something?

    • Never mind. I just realized my mistake — a set of one-way directions could work for more than one path. But it only gets counted once. So the number can be odd.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.