6.1 Worksheet Exercise 6.1.1: Counting passwords made up of letters, digits, and special characters. Consider the following definitions for sets of characters: Digits = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Letters = { a, b, c, d, e, f, g, h, i, j, k, I, m, n, o, p, q, r, s, t, u, v, w, x, y, z} Special characters { *, &, $, # } Compute the number of passwords that satisfy the given constraints. %3D %3D %3D (a) Strings of length 6. Characters can be special characters, digits, or letters. (b) Strings of length 7, 8, or 9. Characters can be special characters, digits, or letters. (c) Strings of length 7, 8, or 9. Characters can be special characters, digits, or letters. The first character cannot be a letter. Exercise 6.1.2: Selecting lunch specials for the week. (a) A Chinese restaurant offers 10 different lunch specials. Each weekday for one week, Fiona goes to the restaurant and selects a lunch special. How many different ways are there for her to select her lunches for the week? Note that which lunch she orders on which day matters, so the following two selections are considered different. A different selection: One possible selection: Mon: Beef with broccoli Mon: Kung pao chicken Tues: Kung pao chicken Wed: Kung pao chicken Thurs: Moo shu pork Fri: Beef with broccoli Tues: Beef with broccoli Wed: Kung pao chicken Thurs: Moo shu pork Fri: Beef with broccoli (b) Now suppose that in addition to selecting her main course, she also selects between water or tea for her drink. How many ways are there for her to select her lunches? 6.2 Worksheet Exercise 6.2.1: Devising a 3-to-1 correspondence. , 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 x 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 = xR). 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 e,olgmexs ol (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 DOU re' hoo 1-otslnoitonu goiovifieoqomee1ol anenogasmo0 1-of slnoitonul en (b) What is |E10|? SuewSL Exercise 6.2.4: Using the bijection rule to count ternary strings whose digits sum to a multiple of 3. et 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 T6 that are balanced and T5. Explain why your function is a ijection. How many strings in T6 are balanced?