Problems: (1) Equivalence Relations and Coimages - Section 1. Problems 1 - 6; (2) Basics of Pigeon-hole Principle - Section 1. Problems 7 - 10; (3) Extended Pigeon-hole Principle - Section 1. Problems 11 - 16; (4) Finding Coimage Descriptions - Section 1. Problems 17 - 20; (5) Reflexive, Symmetric, Transitive - Section 2. Problems 1 - 7; (6) Counting Relations - Section 2. Problems 8 - 11; (7) Transitive Closure and Hasse Diagrams - Section 2. Problems 12 - 16; (8) Lexicographic Order - Section 2. Problems 17-20; (9) Topological Sorting Sections 2. Problems 21-22.

BEFORE LOOKING AT THESE SOLUTIONS BE SURE TO TRY TO WORK THE PROBLEMS ON YOUR OWN!

(1) Equivalence Relations and Coimages - Section 1. Problems 1 - 6:

(1) Let a :A -> N x N be the function that assigns to each student x, the age of x paired with the years completed. The equivalence class partition is the coimage partition of the function a.

(2) There are d equivalence classes: {x, x+d, x-d, x+2d, x-2d, ... }, x=0,1,2,..., d-1. They form the coimage partition of the function m(x) = x (mod d).

(3) Define t(x) to be the truth table of x. The coimage partition of t is the set of equivalence classes. The equivalence classes correspond to sets of equivalent forms in the usual sense that they represent the same Boolean function. How many equivalence classes are there?

(4) Define a function f(x)=x^k (mod d). The equivalence classes are the blocks of the Coimage(f). Can you describe the equivalence classes?

(5) This is a case where it is easy to show that the relation is reflexive, symmetric, and transitive. Defining the function f is not too bad either: f(x) = | x - |_x_| | . That is, f(x) is the absolute value of x minus the least integer in x. We have reached a "cross over" point where the local description of the equivalence relation is easier (barely) than the global description, Coimage(f).

(6) In this case, showing reflexive, symmetric, and transitive is the easiest way to show that we have an equivalence relation. One can define L(x) = y to be the lexicographically minimal permutation y (in one-line notation) that is related to x by as sequence of transpositions as defined in the problem. This works but is more awkward than showing reflexive, symmetric, and transitive. The set of lexicographically minimal elements of the equivalence classes is just one way of selecting one element from each equivalence class. A set D consisting of one element from each equivalence class is called a "system of distinct representatives" for the equivalence classes.

(2) Basics of Pigeonhole Principle - Section 1. Problems 7 -10:

(7) In any group of 677 or more people there must be at least two with the same first and last letters. There are 26*26=676 possible first-last letter pairs. Thus at least one block of the coimage of the function f that maps a name to its first-last letter pair must have more than one element.

(8)

(a) Yes. The mapping from a set of k integers to remainder mod k-1 has k-1 blocks in its coimage and k elements in its domain

(b) No. Take the set of integers to be {0, 1, 2, . . . k-1}. The mapping from integers to integers mod k is the identity mapping.

(9) Try S = {1,2,3,4,5,6,7,8,9}. Choose C={1,2,3,4,5}. No pair adds up to 10. Any choice C with 6 elements must have a pair that adds to 10. To see why, let f(x) be the set {x , |10 - x|} for x in C. The Image(f) has exactly 5 elements, so Coimage(f) has 5 blocks. But the domain of f is C and has 6 elements. Therefore there must be two distinct elements x, y in C that have the same value f(x)=f(y). Thus, {x, y} is in Image(f) and x+y=10. The same argument works if 9 is any integer n. Thus k= |^(n/2)^| + 1 (greatest integer in n/2, plus 1).

(10) For n=2, {0, . . . , 2n} = {0, 1, 2, 3, 4}. Note that there are n+1 even and n odd integers. To be sure of getting an even integer you must pick at least n+1. To be sure of getting an odd, you must pick at least n+2. This is a more elementary idea than the pigeon-hole principle. The maximum set with all odd has size n. Selecting any more produces an even. The maximum set with all even has n+1, selecting one more produces an odd.

(3) Extended Pigeonhole Principle - Section 1. Problems 11 - 16:

(11) The primes between 1 and 50 are P ={ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}. There are 15 of them. Define a function f from the set S to P by f(x) = smallest prime that divides x. If S has at least k=16 elements then one block of the Coimage(f) must contain at least two elements. Say s and t belong to the same block. Then f(s) = f(t) implies that the smallest primes that divides s and t are the same. Thus, gcd(s,t)>1. Clearly, if S has 15 elements we can't guarantee this result, take S=P.

(12) Think about the coimage partition of the function B that maps a person to his/her birthmonth. This partition has as most twelve blocks. If each block had less than three elements there would be at most 12*2=24 elements (persons) in the domain of B. Thus, if the domain of B contains more than 24 elements (persons) there must be at least one block in the coimage(B) with more than two elements. In other words, if there are more than 24 in a group of people, there must be at least three with the same birthmonth. k=25.

(13) Consider the function f that maps a person to his/her birthmonth. The table below shows the structure of the possible coimage partitions of f, given that no block has more than three elements. The first row indicates the possible block sizes, 1, 2, or 3. The entries in the other rows indicate how many blocks there are of that size. Thus, in the row with entries 9, 1, 1, there are 9 blocks of size 3, 1 block of size 2, and 1 block of size 1. Our solution given in the statement of the problem corresponds to the first row:

(14) Let B denote the map from persons to birth ATCs. The coimage(B) can have at most 1461 blocks. If every block had at most 3 elements then the domain of B would be no larger than 3*1461 = 4383. Thus, if the domain of B has more than 4383 elements there must be at least one block of coimage(B) with at least 4 elements. The value of $k$ is 4384.

(15) Let A be function from the set of N students to their scores (in the range 27 to 94). The codomain of A has maximum size 65. We have 65 x 2 = 130. Thus, N > 130 guarantees that 3 students must have the same score.

(16) You choose x pennies and look at the map from these pennies to their dates. There can be at most three blocks in the coimage. If each block had three elements, then x=9. Thus, you had better pick more than 9 to get one block with four pennies. If you pick 10 pennies, one block must contain at least four pennies. N4 = 10. To find N6 a little more care must be taken. There are only four 1971 pennies. To get the extremal configuration, take all four 1971 pennies, five 1968 pennies, and five 1967 pennies for a total of 14 pennies. Thus, you can choose 14 pennies and still not have 6 pennies with the same date. One more penny forces you to take 6 pennies of the same date. Thus, N6 = 15. By the same reasoning, N8 = 21.

(4) Finding Coimage Descriptions - Section 1. Problems 17 - 20:

(17) The fact that each congressman is assigned exactly one lawyer means that the assignment relation is a function A: {1,2, . . . , 15} -> {1,2,3,4,5}. The Coimage(A) has at exactly five blocks and each block has at most four elements. The former condition is from the fact that each lawyer is to represent at least one congressman (i.e., A is onto). The latter condition is explicit in the statement of the problem. Forget, for the moment, the question asked in the problem (this is a pretty good general approach in these problems). We need to make a table of possible assignments, without including unnecessary details, so that we can get a feel for the situation.

We consider assigments A where Coimage(A) has exactly five blocks. We make a "block-size chart" for possible coimages:

The top row gives the block sizes, from 1 to 4. The remaining four rows show how many blocks of that size can result from various assignments A. Thus, the first row shows 1 block of size 1 (one lawyer, one congressman), 1 block of size 2 (one lawyer, two congressmen), 0 blocks of size 3, and 3 blocks of size 4 (3 lawyers, 3 congressmen each for 12 congressmen total).

By now we have forgotten the original question. That shows we are doing things right! Checking back to the question, it was " Show that if two lawyers are assigned less than three congressmen, at least two must be assigned four congressmen." That is true and is evident from our table. Rows one and two represent the situation where two lawyers are assigned less than three lawyers. In both cases, 2 or more (3 for row 1) are assigned four congressmen.

Now "the shoe is on the other foot." We can ask the questions from looking at the table:

Show that if less than two lawyers are assigned less than three congressmen then at least four lawyers must be assigned more than two lawyers.

Show that at least three lawyers must be assigned three or more congressmen. Note that this question can be answered easily without the chart. The extremal situation would be exactly 2 lawyers assigned 4 congressmen (taking care of 8 of them) and three lawyers assigned 2 congressmen, taking care of 6 for a total of only 14, one short! Thus at least three must be assigned three or more.

(18) If n does not divide tk for any k, then look at the set R={ tk (mod n) | k=1, 2, ... n} of residues mod n. This set has cardinality at most n-1, since zero is not in R by assumption. Thus, by the pigeon-hole principle, there must be at least two of the integers ti and tj that have the same value mod n. Thus, n divides ti - tj .

(19) The approach is similar to problem (18). Let S= {{0}, {1,n-1}, {2,n-2}, ... {|_n/2_|, |^n/2^|}} be a collection of |_n/2_| + 1 sets, each with two elements except the first set and possibly, if n is even, the last set. Note that if any set in this collection has two elements, then the sum of those two elements is n. Let R={ ti | i=1, 2, ... k} be any collection of k integers and let f : R -> S be a function from R to S. If k > |_n/2_| + 1, then, by the pigeon-hole principle, there must be two elements of R that are mapped to the same set of S. In particular, take f(j) to be the set of S that contains the integer j (mod n). Thus if f(p) = f(q) there are two possibilities: (1) p (mod n) = q (mod n) or (2) p + q = 0 (mod n). Thus, n divides p - q , or n divides p + q. Thus, k = |_n/2_| + 2 will guarantee the condition of the problem. Why is this k minimal?

(20) Consider an example. Suppose n=12. The numbers are D={1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12}. Factoring out the highest power of two in each case, gives the same list 2^0*1, 2^1*1, 2^0*3, 2^2*1, 2^0*5, 2^3*1, 2^0*9, 2^1*5, 2^0*11, 2^2*3. Each number is written as 2^i*x where x is odd. Define f(2^i*x)=x. The function f takes a number to its "odd part." The domain of f is D. The range is R = {1, 2, 3, 5, 9, 11}, the odd integers in D. Note that |R| = 6 = n/2. If we take any subset S of D of size at least 7, then by the pigeon-hole principle, there are at least two different integers, p < q, in S such that f(p) = f(q). Thus, if f(p)=f(q)=x, we have that p=2^i*x and q=2^j*x and hence, since p<q, we must have i<j and p | q. In general, this process works for any n. The size of R is |^n/2^| + 1. The minimal k = |^n/2^| + 2. Why is k minimal?

(5) Reflexive, Symmetric, Transitive - Section 2. Problems 1 - 7:

(1)

(a) This relation is neither Reflexive, Symmetric, nor Transitive. Counter examples, in the form of three added edges, one for each property, are shown below:

(b) This relation is symmetric, but not reflexive: (1,1) is not in the relation, and not transitive: (1,3) and (3,1) are in the relation, but not (1,1), for example.

(c) This relation is not reflexive: (b,b) not in R, not symmetric: (b,a) not in R, but it is transitive: the only pair (x,y) in R, (y,z) in R where x not equal to y and y not equal to z is (a,b) and (b,c), but (a,c) is in R.

(d) Not reflexive, not symmetric, but it is transitive. To show that it is not transitive, you must find (a,b) and (b,c) in the relation with (a,c) not in the relation. No such elements can be found for this relation, so it is transitive.

(e) Not reflexive, is symmetric, and is transitive. a is in S but (a,a) is not in R. For symmetric, and transitive, no counter examples can be found, so they are true. If S were also empty, then R would be reflexive as well.

(2) Not Reflexive (2 not R 2, for example), Symmetric, Not Transitive (1 C 0, 0 C 1, but 1 not C 1).

(3) Reflexive, Symmetric, Not transitive. Note that if a - b is odd and b - c is odd, then a - c is always even and hence never odd. For a binary relation R to be not transitive we need only have that there exists some a, b, c such that a R b, b R c, and a not R c. The latter condition is much weaker than what we have here.

(4) Reflexive, Symmetric, Transitive. The equivalence classes are the blocks of the coimage partition of the function f(x)=x^2.

(5) Not Reflexive (1 not R 1), Symmetric, Not Transitive (2 R 10, 10 R 5, but 2 not R 5).

(6) Hint: Reflexive, Symmetric, Not Transitive. Explain.

(7) Reflexive, Symmetric (be sure you understand why), Not Transitive ({1,2} R {1}, {1} R {1,3} but {1,2} not R {1,3}).

(6) Counting Relations - Section 2. Problems: 8 - 11:

(8) A reflexive relation R must have xRx for all x in S. There are n^2 - n other pairs (x,y) for which we must decide whether or not xRy. We can make these decisions in 2^(n^2-n) ways. Thus 2^(n^2-n) is the number of reflexive binary relations. The number of relations that are not reflexive is 2^(n^2) - 2^(n^2-n) since 2^(n^2) is the total number of relations. Note that 2^(n^2) - 2^(n^2-n) = 2^(n^2-n) (2^n - 1). We could have written the latter number down as the answer directly (do you see why?).

(9) Suppose that S = {1, 2, 3, ... , n}. This won't change the answers. For a symmetric relation, we can decide whether or not pairs (x,y), x<y, satisify xRy and whether or not xRx for all x in S. Those are the only choices we get and there are C(n,2) + n such decisions to make. Thus there are 2^(C(n,2)+n) symmetric relations. The number of relations that are not symmetric is gotten by subtracting this number from 2^(n^2), the total number of relations.

(10) If a binary relation on S = {1, 2, 3, ... , n} is both reflexive and symmetric, then we can decide whether or not pairs (x,y), x<y, satisify xRy, and that is all the decisions we can make. This can be done in 2^C(n,2) ways.

(11) Choosing an antisymmetric binary relations on S = {1, 2, 3, ... , n} involves three choices for each of the pairs (x,y), x<y. We must decide if x not R y, if xRy, or if yRx. The number of such choices is 3^C(n,2). In addition, we must decide if xRx for each x in S. that makes 3^C(n,2) x 2^n total antisymmetric binary relations. If we only allow reflexive antisymmetric relations then the total number is 3^C(n,2).

(7) Transitive Closure and Hasse Diagrams - Section 2. Problems 12 - 16:

(12) Computing the transitive closure "by inspection" can be tricky. The following matrix is the incidence matrix representation of the binary relation given in this problem:

The meaning is that if a 1 appears in position (i,j) in the four by four matrix of zeroes and ones, then (i,j) is in the relation. If a 0 appears, then (i,j) is not in the relation. The four by four matrix M below is the incidence matrix of the relation of this problem:

The Boolean product M v M of M is gotten by taking the ordinary product M*M and replacing every nonzero entry by 1. For this matrix, M v M is

We form the Boolean sum S2 = M + M v M. The Boolean sum is the ordinary sum with nonzero entries replaced by 1. For S2 we get

We now form S2 v M + M = S3 :

If we now compute S3 v M + M = S4 we find that S3 = S4. Whenever this happens it means we have the incidence matrix S3 of the transitive closure of the relation we started with. Thus, in this case, S3 = S2 v M + M is the incidence matrix of the transitive closure of the relation given in this problem. Here are the drawings of the directed graphs of the relations for this problem, starting with the graph associated with M, then S2, and S3, showing the new pairs added to the relation at each stage:

The general procedure is to start with S1 = M and repeatedly Boolean multiply by M and add M to get S2, S3, etc., until the resulting matrix stops changing (i.e., Sk = Sk+1). The matrix Sk is the incidence matrix of the transitive closure. If M is already the matrix of a transitive relation, S1 = S2 (k=1).

(13) The matrix M is as follows:

S2 = M + M v M is as follows:

S2 = S3, so the transitive closure is {(a,c), (a,d), (b,c), (b,d), (c,d)}, which is easily found by inspection.

(14) The covering relation is {(4,8), (4,12), (4,20), (6,12), (6,18), (8,16),(9,18), (10,20)}. The minimal elements are 4, 6, 9, 1, 14, 15. The maximal elements are 12, 16, 18, 20, 14, 15. A chain of longest length is 4 | 8 | 16. It has length two and is unique.

(15) The covering relation has cardinality 15 (draw the Hasse diagram). There are 12 chains of length two. There is a greatest element: {1, 3, 5}.

(16) The covering relation is {((0,0), (0,1)), ((0,0), (1,0)), ((0,1), (1,1)), ((1,0), (1,1))}. Draw the Hasse diagram in the plane R^2 (use the points of the unit square to represent (0,0), (0,1), etc. The covering relation for the subsets of a two-element set under inclusion is essentially the same as this example. The correspondence is obtained by thinking of the vectors (0,0), (0,1), etc., as the one-line representations of the charateristic functions of the two-element set. The extension to 0-1 vectors of length three is that the Hasse diagram is represented by the unit cube in R^3. The extension to 0-1 vectors of length n is that the Hasse diagram is represented by the unit cube in R^n.

(8) Lexicographic Order - Section 2. Problems 17 -

ASIDE: In the common ASCII encoding of text used in programming, the encoded characters are assigned numbers from 0 to 127. A string of these characters can be thought of as a number, base 128. The lexicographic ordering of these strings (such as in a dictionary) is the same as the numerical ordering, regarding each string as a number base 128.

(17)

(a) reverse order

(b) in order

(c) incomparable

(18)

(a) 123, 124, 125, 134, 135, 145, 234, 235, 245, 345. There are C(5,3) = 10.

(b) 321, 421, 431, 432, 521, 531, 532, 541, 542, 543. There are C(5,3) = 10.

(c) There are C(7, 3) = 35:

111, 112, 113, 114, 115, 122, 123, 124, 125, 133,

134, 135, 144, 145, 155, 222, 223, 224, 225, 233,

234, 235, 244, 245, 255, 333, 334, 335, 344, 345,

355, 444, 445, 455, 555.

Why C(7,3) of these? Add 012 termwise to each vector, giving

123, 124, 125, 126, 127, 134, etc., ending in 367, 456, 457, 467, 567.

This is just the lex list of all strictly increasing vectors of length three from {1,2,3,4,5,6,7}.

(d) There are C(7, 3) = 35:

111, 211, 221, 222, 311, 321, 322, 331, 332, 333,

411, 421, 422, 431, 432, 433, 441, 442, 443, 444,

511, 521, 522, 531, 532, 533, 541, 542, 543, 544,

551, 552, 553, 554, 555.

(19) There are 13 configurations. In lex order they are as follows:

(20)

PASS 1

Bucket 1: 321, 441, 221, 311, 111

Bucket 2: 312, 422,

Bucket 3: 143,

Bucket 4: 214, 234

PASS 2

Bucket 1: 311, 111, 312, 214,

Bucket 2: 321, 221, 422,

Bucket 3: 234

Bucket 4: 441, 143

PASS 3

Bucket 1: 111, 143,

Bucket 2: 214, 221, 234,

Bucket 3: 311, 312, 321,

Bucket 4: 422, 441

(9) Topological Sorting - Sections 2. Problems 21 - 22

(21) The topological sort 15, 14, 10, 9, 6, 18, 4, 20, 12, 8, 16 has 25 in-order pairs. Can you do better? Here is the Hasse diagram:

(22) This poset has a least element, the empty set, and a greatest element, S. For convenience of notation, we leave those off of the linear extensions that we describe. Any linear extension must begin and end with these two sets. Start with the linear extension {a}, {b}, {c}, {a,b}, {a,c}, {b,c}. The three sets with one elment can be permuted in 3!=6 ways and, independently, the three sets with two elements can be permuted in 6 ways. This gives 6 x 6 = 36 linear extensions. Another linear extension is like this: {a}, {b}, {a,b}, {c}, {a,c}, {b,c}. Now the first two elements can be permuted in 2 ways and, independently, the last two elements can be permuted in 2 ways giving 4 linear extensions of this form. Now we have 40 linear extensions. We leave it to you to find 8 more.