Thread: 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.

Originally Posted by jenjen

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

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).