CMSC 250 Fall 2004 -- Homework 13

Due Wed., Dec. 1 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. 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. 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 $2^k\cdot m$, where $k\geq 0$ and $m$ is odd.

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

   3. 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.

   4. Show that if f is a function from S to T where S and T are both finite sets and $m = \lceil \frac{n(S)}{n(T)} \rceil$, then there are at least m elements of S that are mapped to the same value of T. That is, show that there are elements $s_1, s_2, ... s_m$ of S such that $f(s_1) = f(s_2) = ... = f(s_m)$.

2. Find four binary relations from $\{a,b\}$ to $\{x,y\}$ that are not functions from $\{a,b\}$ to $\{x,y\}$.

3. Define binary relations $R$ and $S$ from ${\bf R}$ to ${\bf R}$ as follows:
   
   $$R = \{ (x,y)\in {\bf R}\times{\bf R}\vert x^2 + y^2 = 4 \}$$
   
   
   and
   
   $$S = \{ (x,y)\in {\bf R}\times{\bf R}\vert x = y \}$$
   
   
   Graph $R,S,R\cup S$, and $R\cap S$ in the Cartesian plane.

4. Determine whether the given binary relation is reflexive, symmetric, transitive, or none of these. Justify your answers.

   Let $X=\{a,b,c\}$ and $P(X)$ be the power set of $X$. A binary relation ${\mathcal{N}}$ is defined on $P(X)$ as follows: For all $A,B \in P(X)$, $A\ {\mathcal{N}}\ B \Leftrightarrow N(A) \neq N(B)$ (that is the number of elements in $A$ is not equal to the number of elements in $B$).

Web Accessibility