All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Back to throne (Posted on 2015-05-21) Difficulty: 2 of 5
Imagine a chess King placed in the central square C(5,5) of a 9x9 “checkerboard”. King’s step consists of his displacement to the neighboring square in one of the 8 directions.

What is the probability that his 4-step random walk terminates at square C?

See The Solution Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer exploration and solution | Comment 2 of 3 |
Probability distributions about the central square after moves 1, 2, 3 and 4:

 0.125000000 0.125000000 0.125000000
 0.125000000 0.000000000 0.125000000
 0.125000000 0.125000000 0.125000000

 0.015625000 0.031250000 0.046875000 0.031250000 0.015625000
 0.031250000 0.031250000 0.062500000 0.031250000 0.031250000
 0.046875000 0.062500000 0.125000000 0.062500000 0.046875000
 0.031250000 0.031250000 0.062500000 0.031250000 0.031250000
 0.015625000 0.031250000 0.046875000 0.031250000 0.015625000

 0.001953125 0.005859375 0.011718750 0.013671875 0.011718750 0.005859375 0.001953125
 0.005859375 0.011718750 0.023437500 0.023437500 0.023437500 0.011718750 0.005859375
 0.011718750 0.023437500 0.052734375 0.052734375 0.052734375 0.023437500 0.011718750
 0.013671875 0.023437500 0.052734375 0.046875000 0.052734375 0.023437500 0.013671875
 0.011718750 0.023437500 0.052734375 0.052734375 0.052734375 0.023437500 0.011718750
 0.005859375 0.011718750 0.023437500 0.023437500 0.023437500 0.011718750 0.005859375
 0.001953125 0.005859375 0.011718750 0.013671875 0.011718750 0.005859375 0.001953125

 0.000244141 0.000976563 0.002441406 0.003906250 0.004638672 0.003906250 0.002441406 0.000976563 0.000244141
 0.000976563 0.002929688 0.006835938 0.009765625 0.011718750 0.009765625 0.006835938 0.002929688 0.000976563
 0.002441406 0.006835938 0.017089844 0.024414063 0.030273438 0.024414063 0.017089844 0.006835938 0.002441406
 0.003906250 0.009765625 0.024414063 0.032226563 0.041015625 0.032226563 0.024414063 0.009765625 0.003906250
 0.004638672 0.011718750 0.030273438 0.041015625 0.052734375 0.041015625 0.030273438 0.011718750 0.004638672
 0.003906250 0.009765625 0.024414063 0.032226563 0.041015625 0.032226563 0.024414063 0.009765625 0.003906250
 0.002441406 0.006835938 0.017089844 0.024414063 0.030273438 0.024414063 0.017089844 0.006835938 0.002441406
 0.000976563 0.002929688 0.006835938 0.009765625 0.011718750 0.009765625 0.006835938 0.002929688 0.000976563
 0.000244141 0.000976563 0.002441406 0.003906250 0.004638672 0.003906250 0.002441406 0.000976563 0.000244141

The 0.052734375 at C after the 4th move, expressed as a common fraction, before reduction to lowest terms, must have a denominator of 8^4 = 32768. Multiplying by this we get 1728 for the numerator so the desired probability is:

0.052734375 = 1728/32768  =  27/512

from:

DefDbl A-Z
Dim crlf$, grid(9, 9, 4)

Function mform$(x, t$)
  a$ = Format$(x, t$)
  If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
  mform$ = a$
End Function

Private Sub Form_Load()
 Text1.Text = ""
 crlf$ = Chr(13) + Chr(10)
 Form1.Visible = True
 
 
 grid(5, 5, 0) = 1
 For stp = 1 To 4
    For row = 1 To 9
    For col = 1 To 9
     If grid(row, col, stp - 1) > 0 Then
      For r = row - 1 To row + 1
      For c = col - 1 To col + 1
        If r <> row Or c <> col Then
          grid(r, c, stp) = grid(r, c, stp) + grid(row, col, stp - 1) / 8
        End If
      Next
      Next
     End If
    Next
    Next
    For r = 5 - stp To 5 + stp
    For c = 5 - stp To 5 + stp
      Text1.Text = Text1.Text & mform(grid(r, c, stp), " 0.000000000")
    Next c
    Text1.Text = Text1.Text & crlf
    Next r
    Text1.Text = Text1.Text & crlf
 Next stp
 
 g = gcd(Int(grid(5, 5, stp - 1) * 2 ^ 15 + 0.5), Int(2 ^ 15 + 0.5))

 Text1.Text = Text1.Text & grid(5, 5, stp - 1) * 2 ^ 15 & "/" & 2 ^ 15 & "  =  "
 Text1.Text = Text1.Text & grid(5, 5, stp - 1) * 2 ^ 15 / g & "/" & 2 ^ 15 / g & crlf

 Text1.Text = Text1.Text & " done" & crlf
 
 
End Sub

Function gcd(a, b)
  x = a: y = b
  Do
   q = Int(x / y)
   z = x - q * y
   x = y: y = z
  Loop Until z = 0
  gcd = x
End Function

Edited on May 21, 2015, 10:35 am
  Posted by Charlie on 2015-05-21 10:34:51

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information