Fall 2000, CSE 468: Solution of Assignment 1

Exercise 1

  1. R is an equivalence relation. In fact, x+y is an even number iff x+y = 2n for some n. Then the relation is reflexive, because x+x = 2x. Simmetry follows from the commutativity of +. As for transitivity, observe that x+y = 2n and y+z = 2m imply x+z = 2(m+n-y). The corresponding partition is constituted by the odd and the even numbers.
  2. R is not an equivalence relation, because transitivity is not satisfied. As a counterexample, consider x = 1, y = 10 and z = 19.
  3. R is an equivalence relation. Let us denote by rep(x) the decimal representation of x, and by all_but_last(rep(x)) the representation of x without the last digit. Then x R y iff all_but_last(rep(x)) = all_but_last(rep(y)). Since = is an equivalence relation, we have that also R is. As for the partition, note that all_but_last(rep(x)) represents the quotient of the integer division of x by 10. Hence the generic n-th element of the partition will be Pn = { x | x div 10 = n } (where div represents the integer division).
    Note: the first part of this question could also be solved by observing that x and y are related iff x div 10 = y div 10.

Exercise 2

Exercise 3

  1. One possible solution is: ((1+2+...+9)(0+1+...+9)*)*(0+2+4+6+8).
  2. One possible solution is: (a+c)*b(a+c)*.
  3. One possible solution is: ab(ab)*.
  4. One possible solution is: ((a+b)(a+b))*(a+b).

Exercise 4

The inductive step does not hold for n = 1. In fact, assume that in the room there are two persons, John and Jack. We can't prove that John and Jack have the same height, because we need at least another person to apply the transitivity reasoning implicit in the "proof". In other words, when we send away John, the remaining group is composed only by Jack. When we reintroduce John and send away Jack, the new group is composed only by John. There is nothing which links the heights of the two groups.