1. Pairs of integers a. Consider a set S = {(a, b) = Z x Z|a + b is divisible by 3 and a b}. Write all elements of this set S for which a + b < 10. b. Give a recursive definition (by specifying its basis and recursion) of this set S (that is, the set of pairs of nonnegative integers with first no larger than second and their sum divisible by 3, where a + b is not bounded). 2. Binary strings with same number of 0s and 1s. a. Give a recursive definition of a set S of all binary strings that have the same number of Os and 1s. Hint: in particular, the following strings have the same number of 0s and 1s: the empty string A, the string 000111 and the string 10100011. Check that your recursive definition can generate all of them. b. Give an example of a string that can be put into S by two different sequences of applications of your recursive definition rules. c. Now show, using structural induction on your recursive definition, that every string in your set has even number of symbols.