CMSC250, Spring 2004 Homework 13Due Wednesday, May 5 at the beginning of your discussion section.You must write the solutions to the problems single-sided on your own linedpaper, with all sheets stapled together, and with all answers written in sequentialorder or you will lose points.1. There are twelve people in a club. Each member of the club agrees to pick six peopleat random (they can’t pick themselves) from the club and send each of the six peoplea p ostcard.(a) Prove that there are two members of the club who exchange postcards (that is,m sends a postcard to n and n sends a postcard to m).Hint: Figure out the number of pairs of members of the club.(b) Does the conclusion in part (a) still hold if each member only picks five others tosend postcards? Why or why not?(c) The members of the club set out twelve chairs in a row for them to sit in at theirupcoming meeting. However, three members are sick and have to stay home.Prove that when everyone sits down at the beginning of the meeting, there willbe a consecutive group of three chairs that are all occupied.(d) If another person gets sick, does the conclusion from part (c) still hold? Why orwhy not?2. Prove that given a set of any 38 integers, there exist two in the set whose difference isdivisible by 37.3. Prove that there exists a multiple of 37 whose decimal expansion contains only digits1 and 0.Hint: Use the same technique as problem 2.4. You are given a sequence of five positive integers: a1, a2, a3, a4, and a5. Prove thateither one of them is divisible by 5, or the sum of two or more consecutive numbers inthe sequence is divisible by 5.Hint: C onsider the five sums a1, a1+ a2, a1+ a2+ a3, a1+ a2+ a3+ a4, and a1+ a2+a3+ a4+ a5. Use the same technique as problem 2.5. You just finished your CMSC114 project, and it took you 9 days and 250 lines of code.Find the maximum integral value of x to make the following statement true: “Therewas one day where you wrote at least x lines of code.” Prove your answer is correct.16. Let the function f : R → R be defined by f (x) = x2, and let g : Rnonneg→ R bedefined by g(x) =√x.(a) Let h1= f ◦g. Describe h1: give the domain, co-domain, range, and definition ofthe function itself.(b) Let h2= g ◦ f. Describe h2: give the domain, co-domain, range, and definition ofthe function itself.7. Given a function f : X → Y0and a function g : Y → Z, explain why you cannotcompose f and g (into g ◦ f) unless the range of f is a subset of (or equal to) Y
View Full Document
Unlocking...