Results 1 to 4 of 4

Math Help - Equivalence classes on an 8x8 chessboard

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    29

    Equivalence classes on an 8x8 chessboard

    Hi there, I'm struggling a bit with a uni question I've been given. I think I understand the basics but possibly not!! Any help greatly appreciated!

    Take a standard 88 chessboard, and label the squares
    (i, j) 1 ≤ i ≤ 8, 1 ≤ j ≤ 8, with (1, 1) being the bottom lefthand square,
    and (8, 8) the top righthand square. Define a relation on these squares by
    (i, j) ∼ (i′, j′) iff i + j = i′ + j′.

    (a) Show that ∼ defines an equivalence relation on the chessboard.
    (b) How many equivalence classes are there, and what are their sizes?
    (c) Choose equivalence class representatives for the classes.

    Here are my thoughts...
    a) would I assume ~ if i+j not equal to i'+j' and show this is not the case?
    b) I'm not entirely sure but I would assume that as the canonical projection map is surjective and that there are 64 ways to write i+j that there are 64 equivalence classes of size 2, then again I'm well prepared to believe I've missed the point!
    c) As a set of class representatives is a subset of X which contains exactly one element from each equivalence class could the class representative just be either the i's or the j's

    Luckily this is over the computer so if people tell me I'm completly wrong you won't see me blushing!!

    Thanks for the help, Laura
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    Very often, when approaching a new problem, is it useful to consider several examples. What are all the squares for which the sum of coordinates is 4? 5? This will help you find out almost everything about equivalence classes.

    To show that ∼ is an equivalence relation (as well as to show anything in mathematics) one should start with definitions. Once you know the definitions of an equivalence relation and related notions, you need to know what it means to prove the statements involved. Those statements have the form "For all x, ...", so you need to know what it means to prove them.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    645
    Hello, leshields!

    With terms like "canonical projection map" and "surjective",
    . . you're overthinking the problem.


    Take a standard 88 chessboard, and label the squares: . (i, j)\quad 1 \leq i \leq 8,\;\;1 \leq j \leq 8

    with (1, 1) being the bottom lefthand square, and (8, 8) the top righthand square.

    Define a relation on these squares by: . (i,j) \sim (i',j') \;\;\Longleftrightarrow\;\;i+j \,=\,i' + j'
    Did you make a "sketch"?

    . . \begin{array}{cccccc}<br />
81 & 82 & 83 & 84 & \hdots & 88 \\<br />
\vdots & \vdots & \vdots & \vdots & & \vdots \\<br />
31 & 32 & 33 & 34 & \hdots & 38 \\<br />
21 & 22 & 23 & 24 & \hdots & 28 \\<br />
11 & 12 & 13 & 15& \hdots & 18\end{array}


    Two squares are related by \sim if the sums of their coordinates are equal.

    For example: . (1,4) \sim (2,3) \sim (3,2) \sim (4,1)



    (a) Show that \sim defines an equivalence relation on the chessboard.

    Reflexive

    Is (a,b) \sim (a,b) ?

    a+b \:=\:a+b\quad\hdots Yes, "they" have the same sum.


    Symmetric

    If (a,b) \sim (c,d), is (c,d) \sim (a,b) ?

    Since (a,b) \sim(c,d), we have: . a+b \,=\,c+d

    Then we have: c+d \,=\,a+b, which gives us: . (c,d) \sim (a,b)

    Yes, the relation is symmetric.


    Transitive

    If (a,b) \sim (c,d) and (c,d) \sim (e,f), is (a,b) \sim (e,f) ?

    Since (a,b) \sim (c,d), we have: . a+b \,=\,c+d

    Since (c,d)\sim(e,f), we have: . c+d\,=\,e+f

    Then we have: . a+b\,=\,e+f which gives us: . (a,b)\sim(e,f)

    Yes, the relation is transitive.


    Therefore, \sim is an equivalence relation.




    (b) How many equivalence classes are there, and what are their sizes?
    There are 15 equivalance classes . . .

    . . \begin{array}{cc}<br />
\text{Sum} & \text{Size} \\ \hline<br />
2 & 1 \\ 3 & 2 \\ 4 & 3 \\ 5 & 4 \\ 6 & 5 \\ 7 & 6 \\ 8 & 7 \\ 9 & 8 \end{array}
    . . . \begin{array}{cc}<br />
10 & \quad\; 7 \\ 11 & \quad\;6 \\ 12 & \quad\;5 \\ 13 & \quad\;4 \\ 14 & \quad\;3 \\ 15 & \quad\;2 \\ 16 & \quad\;1\end{array}




    (c) Choose equivalence class representatives for the classes.
    I don't know what this means . . .

    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Soroban View Post
    I don't know what this means . . .

    You said there were 15 classes. you need to explicitly state one member of each class to represent that class. for example, partitioning the integers according to parity is an equivalence relation. i can choose 0 to be the class representative of the even integers while 1 can be that of the odd integers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equivalence Classes
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 27th 2011, 10:12 AM
  2. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  4. equivalence classes
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 4th 2009, 03:20 AM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum