CMSC 250 Homework 11 Fall 2005

0201 & 0202

Due Wed Dec 7 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. Define 1#1 by the rule 2#2, for all integers 3#3. Is 4#4 one-to-one? Is 4#4 onto? Prove or give counterexamples.

2. Let 5#5 and 6#6 be functions, and 7#7 be defined by 8#8 for all real numbers 9#9.
   1. If 10#10 and 4#4 are both one-to-one, is 11#11 also one-to-one?
   2. If 10#10 and 4#4 are both onto, is 11#11 also onto?
   Justify your answer.

3. If 12#12 and 13#13 are functions and 14#14 is onto, must both 10#10 and 4#4 be onto? Prove or give a counterexample.

4. For this set of problems, you must clearly define what the domain is, what the size of the domain, what the codomain is, what the size of the codomain is, and what the total function is that maps from the domain to the codomain. Make sure you indicate which of these are known and how the pigeon hole principle can be applied to reach the parts you need.
   1. Let 15#15. Suppose five integers are chosen from 16#16. Must there be two integers whose sum is 10? Why?

   2. How many integers from 100 through 999 must you pick in order to be sure that at least two of them have a digit in common? (For example, 256 and 530 have the common digit 5.)

   3. What is the largest number of elements that a set of integers from 1 through 100 can have so that no one element in the set is divisible by another? (Hint: Imagine writing all the numbers from 1 through 100 in the form 17#17, where 18#18 and 19#19 is odd.

   4. Prove that at a party where there are at least two people, there are two people who know the same number of other people there. You may assume that if person a knows person b then person b must know person a as well.

   5. A arm wrestler is the champion for a period of 75 hours. The arm wrestler had at least one match an hour, but no more than 125 total matches. Show that there is a period of consecutive hours during which the arm wrestler had exactly 24 matches.

5. Find four distinct binary relations from 20#20 to 21#21 that are not functions from 20#20 to 21#21.

Web Accessibility