Results 1 to 3 of 3

Math Help - Set Theory Knights Tour

  1. #1
    Member
    Joined
    Mar 2006
    Posts
    82

    Set Theory Knights Tour

    Hey, please helppp meeeeee....Thanks a lot in advance.

    Algebraic Example: A will correspond to the squares on a chessboard, so that A= {1,2,3,4,5,6,7,8} X {1,2,3,4,5,6,7,8} and (x,y) will be related to (x',y') if and only if one of the quantities l x - x' l, l y - y' l is equal to 1 and the other is equal to 2. In nonmathematical terms this relation corresponds to the condition in chess that a knight positioned at square (x,y) is able to reach square (x',y') in one move provided the latter is not occupied by a piece of the same color.

    Let R be the binary relation in Algebraic Example (the set is a chessboard, and the relation is that two squares are related if there is a knight's move from one to the other).

    1) Let E be the equivalence relation generated by R. Show that E contains exactly one equivalence class; in other words, starting from the standard position on (1,2) the knight can reach every point on the chessboard.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jenjen View Post
    Hey, please helppp meeeeee....Thanks a lot in advance.

    Algebraic Example: A will correspond to the squares on a chessboard, so that A= {1,2,3,4,5,6,7,8} X {1,2,3,4,5,6,7,8} and (x,y) will be related to (x',y') if and only if one of the quantities l x - x' l, l y - y' l is equal to 1 and the other is equal to 2. In nonmathematical terms this relation corresponds to the condition in chess that a knight positioned at square (x,y) is able to reach square (x',y') in one move provided the latter is not occupied by a piece of the same color.

    Let R be the binary relation in Algebraic Example (the set is a chessboard, and the relation is that two squares are related if there is a knight's move from one to the other).

    1) Let E be the equivalence relation generated by R. Show that E contains exactly one equivalence class; in other words, starting from the standard position on (1,2) the knight can reach every point on the chessboard.
    This is equivalent to showing that a knight starting from any square can
    reach any other square by a sequence of legal moves. To prove this
    one need only display one such tour. This is called a knights tour, look here for examples.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I have an embarassing way to show this.

    Consider your set S and its relation R.
    Form a graph,
    G=(S,R)
    Show that there exists an Eulerian trail on this graph.
    Then we can conclude that this graph is connected, that is there exists a knight tour between any two points.

    The reason why this is embarassing is that you need to find an Eulerian trail which might be ugly (by guessing).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Salesman Tour
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 6th 2011, 01:11 AM
  2. Knights of the Board
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: April 30th 2010, 08:39 AM
  3. [SOLVED] Knights and Knaves help >__<
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 30th 2009, 04:42 AM
  4. What road to take? Knights and Knaves puzzle.
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: January 30th 2009, 11:26 AM

Search Tags


/mathhelpforum @mathhelpforum