Unkown Blogger Pursues a Deranged Quest for Normalcy

  • Logo

  • Unknown Blogger

  • May 2012
    M T W T F S S
    « Apr   Jun »
  • Recent Posts

  • Pages

  • Categories

  • Archives

  • Meta

  • Blog Stats

    • 10,700 hits
  • Advertisements

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


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

%d bloggers like this: