6.2 Worksheet Exercise 6.2.1: Devising a 3-to-1 correspondence. (a) Find Find a function from the set {1, 2, ., 30} to {1, 2, ..., 10} that is a 3-to-1 correspondence. (You may find that the division, ceiling or floor operations are useful.) *** Exercise 6.2.2: Using the bijection rule to count palindromes. If x is a string, then xR is the reverse of the string. For example, if x = 1011, then x = 1101. A string is a palindrome if the string is the same backwards and forwards (i.e., if x = x*). Let B = {0, 1}. The set B" is the set of all n-bit strings. Let Pn be the set of all strings in B" that are palindromes. (a) Show a bijection between P6 and B3. %3D %3D %3D %3D (b) What is | P6|? (c) Determine the cardinality of P7 by showing a bijection between P7 and B" for some n. Exercise 6.2.3: Using the bijection rule to count binary strings with even parity. Let B = {0, 1}. B" is the set of binary strings with n bits. Define the set En to be the set of binary strings with n bits that have an even number of 1's. Note that zero is an even number, so a string with zero 1's (i.e., a string that is all 0's) has an even number of 1's. (a) Show a bijection between B° and E10. Explain why your function is a bijection. %3D (b) What is |E10|? Exercise 6.2.4: Using the bijection rule to count ternary strings whose digits sum to a multiple of 3. Let T = {0, 1, 2}. A string x E T is said to be balanced if the sum of the digits is an integer multiple of 3. (a) Show a bijection between the set of strings in Tó that are balanced and T. Explain why your function is a %3D bijection. (b) How many strings in T6 are balanced? Page 1 of 2 h 6.2 Worksheet Exercise 6.2.5: Using the k-to-1 rule for counting ways to line up a group. Ten kids line up for recess. The names of the kids are: {Abe, Ben, Cam, Don, Eli, Fran, Gene, Hal, Ike, Jan}. Let S be the set of all possible ways to line up the kids. For example, one ordering might be: (Fran, Gene, Hal, Jan, Abe, Don, Cam, Eli, Ike, Ben) The names are listed in order from left to right, so Fran is at the front of the line and Ben is at the end of the line. Let T be the set of all possible ways to line up the kids in which Gene is ahead of Don in the line. Note that Gene does not have to be immediately ahead of Don. For example, the ordering shown above is an element in T. Now define a function f whose domain is S and whose target is T. Let x be an element of S, so x is one possible way to order the kids. If Gene is ahead of Don in the ordering x, then f(x) = x. If Don is ahead of Gene in x, then f(x) is the ordering that is the same as x, except that Don and Gene have swapped places. (a) What is the output of f on the following input? (Fran, Gene, Hal, Jan, Abe, Don, Cam, Eli, Ike, Ben) %3D (b) What is the output of f on the following input? (Eli, Ike, Don, Hal, Jan, Abe, Ben, Fran, Gene, Cam) (c) Is the function fa k-to-1 correspondence for some positive integer k? If so, for what value of k? Justify your answer. (d) There are 3628800 ways to line up the 10 kids with no restrictions on who comes before whom. That is, IS| = 3628800. Use this fact and the answer to the previous question to determine |T|. (e) Let Q be the set of orderings in which Gene comes before Don and Jan comes before Abe (again, not necessarily immediately before). Define a k-to-1 correspondence from S to Q. Use the value of k to determine |Q|. Page 2 of 2