Unkown Blogger Pursues a Deranged Quest for Normalcy

  • Logo

    ubpdqn
  • Unknown Blogger

  • May 2012
    M T W T F S S
    « Apr   Jun »
     123456
    78910111213
    14151617181920
    21222324252627
    28293031  
  • Recent Posts

  • Pages

  • Categories

  • Archives

  • Meta

  • Blog Stats

    • 10,532 hits

Knight’s tour revisited

Posted by ubpdqn on May 13, 2012

Unknown Blogger Mathematica

Once again I have found food for thought in a post on John D Cook’s blog.

The puzzle posed:

Start a knight at a corner square of an otherwise-empty chessboard. Move the knight at random by choosing uniformly from the legal knight-moves at each step. What is the mean number of moves until the knight returns to the starting square?

As is discussed this can be solved by considering a random walk on the Knight’s tour graph (connected graph).

I found it instructive to count the edges of the Knight’s tour graph (though I am disappointed that it was not as ‘clear’ to me as suggested). Consider the $latex n\times n$ chessboard.  The sum of the degrees of all the vertices is twice the number of edges.

Consider the following 6 $latex \times$ 6 board. The color  represent  distinguishes the degree of the vertices.

Using insights from this chessboard, see the…

View original post 303 more words

Advertisements

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

 
%d bloggers like this: