CMSC 250 Fall 2004 -- Homework 13 Answer

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.
      Answer: The proof will consist of two parts: (i) showing that we can choose 50 integers such that no one element in the set is divisible by another. (ii) showing that once we choose 51 integers, one of them is divisible by another.
      1. Consider the set $\{51,52,..., 99,100\}$. Since the double of each integer is at least 102, no one element in this set is divisible by another.
      2. Let the domain be $X \subset \{1,2,...,100\}$, codomain be $Y=\{1,3,5,...,97,99\}$, and $f:X\to Y$ be $f(x)=y$ if $x$ is of the form $2^k\cdot y$, where $k\geq 0$ and $y$ is odd. We know that $\vert Y\vert=50$. If $\vert X\vert=51$, then by pigeonhole principle, there exists $a,b \in X$ such that $a < b$, $a=2^c\cdot y$ and $b=2^d\cdot y$. Then $b$ is a multiple of $a$.
   2. 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.
      Answer: Let the domain be the set of people $X$ at the party, with $\vert X\vert\ge 2$. Let the codomain be $Y$ which is a set of numbers, meaning how many people a person may know. Then $f:X\to Y$ will be $f(x) =$ how many people person $x$ knows. The crucial fact is that $\vert Y\vert<\vert X\vert$, because it cannot happen that there exist 2 people in $X$ such that one knows nobody and another knows everybody. Therefore $Y$ is either $\{0,1,...,\vert X\vert-1\}$ or $\{1,2,...,\vert X\vert\}$. Therefore by pigeonhole principle the claim holds.
   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.
      Answer: The problem is the same as: given $x_1,x_2,...x_{75}$ such that $x_i \ge 1$ and $x_1+x_2+\cdots+x_{75} \le 125$. Show that there exists $j,k$ such that $\sum_{i=j}^k x_i = 24$.

      Solution: let $y_i = \sum_{m=1}^i x_m$. Then $1\leq y_1 < y_2 < \cdots < y_{75} = 125$. Moreover we know that $25\leq y_1+24 < y_2+24 < \cdots < y_{75}+24 = 149$. Now, let the domain $Y = \{\lq\lq y_i''\}\cup\{\lq\lq y_i+24''\}$, codomain $N = \{1,2,...,149\}$, and $f:Y\to N$ be $f(\lq\lq y'')=y$ (evaluate $\lq\lq y''$). Notice that $\vert Y\vert=150$ but $\vert N\vert=149$. Moreover, all $y_i$ are distinct. Then there exists $j,k$ such that $y_j +24 = y_k$, and thus $\sum_{i=j}^k x_i = 24$.

   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)$.
      Answer: Suppose, on the contrary, that it is not true. Then there are at most $m-1$ elements of $S$ that are mapped to the same value of $T$. How large can $S$ be? Since for any element in $T$ there are at most $m-1$ elements of $S$ that are mapped to it, it follows that $n(S) \le (m-1)n(T)$, which means $\lceil \frac{n(S)}{n(T)} \rceil \leq m-1$, contradiction.
2. Find four binary relations from $\{a,b\}$ to $\{x,y\}$ that are not functions from $\{a,b\}$ to $\{x,y\}$.
   Answer:
   1. $\{(a,x),(a,y)\}$
   2. $\{(b,x),(b,y)\}$
   3. $\{(a,x),(a,y),(b,x)\}$
   4. $\{(a,x),(a,y),(b,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.
   Answer:
   1. $R$: a circle with radius 2 and center at origin.
   2. $S$: a line with slope 1 and passing through the origin.
   3. $R\cup S$: the overlap of (i) and (ii).
   4. $R\cap S$: consist of only the intersection points of (i) and (ii).
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$).
   Answer:

   • Not reflexive, since $N(A)$ always equals itself.
   • Symmetric, since $\neq$ is symmetric.
   • Not transitive, since with $N(A)\neq N(B)$ and $N(B)\neq N(A)$ we can still have $N(A)=N(A)$.

Web Accessibility