Module 3 Problem Set

Problem 2 Ten kids line up for recess. The names of the kids are: { Alex, Bobby, Cathy, Dave, Emy, Frank, George, Homa, Ian, Jim } . Let S be the set of all possible ways to line up the kids. For example, one order might be: (Frank, George, Homa, Jim, Alex, Dave, Cathy, Emy, Ian, Bobby) The names are listed in order from left to right, so Frank is at the front of the line and Bobby is at the end of the line. Let T be the set of all possible ways to line up the kids in which George is ahead of Dave in the line. Note that George does not have to be immediately ahead of Dave. 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 George is ahead of Dave in the ordering x , then f ( x ) = x . If Dave is ahead of George in x , then f ( x ) is the ordering that is the same as x , except that Dave and George have swapped places. (a) What is the output of f on the following input? (Frank, George, Homa, Jim, Alex, Dave, Cathy, Emy, Ian, Bobby) Since George is ahead of Dave, the output remains the same as the in- put. (Frank, George, Homa, Jim, Alex, Dave, Cathy, Emy, Ian, Bobby) (b) What is the output of f on the following input? (Emy, Ian, Dave, Homa, Jim, Alex, Bobby, Frank, George, Cathy) Since Dave is a head of George, the must swap places, leaving the out- put at (Emy, Ian, George, Homa, Jim, Alex, Bobby, Frank, Dave, Cathy) (c) Is the function f a k -to-1 correspondence for some positive integer k ? If so, for what value of k ? Justify your answer. No, there is not a k to 1 correspondence as the order of George and Dave matter. (d) There are 3628800 ways to line up the 10 kids with no restrictions on who comes before whom. That is, | S | = 3628800. Use this fact and the answer to the previous question to determine | T | . Since T is a subset of S (bijection) we can use the k to 1 rule.

Problem 5 A university offers a Calculus class, a Sociology class, and a Spanish class. You are given data below about two groups of students. (i) Group 1 contains 170 students, all of whom have taken at least one of the three courses listed above. Of these, 61 students have taken Calculus, 78 have taken Sociology, and 72 have taken Spanish. 15 have taken both Cal- culus and Sociology, 20 have taken both Calculus and Spanish, and 13 have taken both Sociology and Spanish. How many students have taken all three classes? Lets define our variables: c=Calculus s=Sociology sp=Spanish We are looking to find c and s and sp. Since we are only looking for how man students took all three classes, we can subtract our students who took only one or two. Thus: 170 = 61 + 78 + 72 - 15 - 20 - 13 + ( c ∧ s ∧ sp ). 170 = 163( c ∧ s ∧ sp ). 7 Students have taken all three courses. (ii) You are given the following data about Group 2. 32 students have taken Calculus, 22 have taken Sociology, and 16 have taken Spanish. 10 have taken both Calculus and Sociology, 8 have taken both Calculus and Span- ish, and 11 have taken both Sociology and Spanish. 5 students have taken all three courses while 15 students have taken none of the courses. How many students are in Group 2? c=calculus s=sociology sp=spanish n = 32 + 22 + 16 - 10 - 8 - 11 + 2 * n ( c ∧ s ∧ sp ) n = 41 + 2 * n ( c ∧ s ∧ sp ) n = 41 + 2 x Since we do not know the value of x, it is not possible to determine the number of students in group 2.