CMSC250, Spring 2004 Homework 13 Answers

Due Wednesday, May 5 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. There are twelve people in a club. Each member of the club agrees to pick six people at random (they can't pick themselves) from the club and send each of the six people a postcard.
   1. 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.

      • Answer: Let set $A$ denote the set of postcards sent, and let set $B$ denote the set of (unordered) pairs of members in the club. There are $12 \cdot 6 = 72$ postcards sent in total, so $n(A)=72$. There are $\binom{12}{2} = 66$ pairs of members in the club, so $n(B) = 66$. Consider a function from $A$ to $B$ that maps postcards to the unordered set consisting of the sender and receiver.

        Since $n(A) > n(B)$, there must be at least one pair of club members that is mapped to by more than one postcard due to the pigeonhole principle. In other words, there are two postcards than end up at the same pair of members, which means those two members exchanged postcards.

   2. Does the conclusion in part (a) still hold if each member only picks five others to send postcards? Why or why not?
      • Answer: No. If each member only sends five postcards, then there are only $12 \cdot 5 = 60$ postcards put into the mail. If that happens, then it is possible that nobody exchanges postcards.

   3. The members of the club set out twelve chairs in a row for them to sit in at their upcoming meeting. However, three members are sick and have to stay home. Prove that when everyone sits down at the beginning of the meeting, there will be a consecutive group of three chairs that are all occupied.
      • Answer: There are nine members at the meeting (since three are sick), which means there will be three empty chairs. Think of these three chairs as separating the chairs into ``groups of consecutively filled chairs.'' Since there are three empty chairs, there are four groups of consecutively filled chairs -- we don't know how many are in each group, though; a group could even have zero people in it. We will prove that at least one of these groups has at least three people in it.

        Let set $A$ denote the set of nine people, so $n(A)=9$. Let set $B$ denote the set of groups of consecutively filled chairs, so $n(B)=4$. Think of a function from $A$ to $B$ that maps a person into the group of chairs in which they are sitting. To use the generalized pigeonhole principle, we must find a $k$ to satisfy the inequality $n(A) > k \cdot n(B)$, or equivalently, $9 > 4k$. The maximum value of $k$ that makes the statement true is 2. Therefore, by the generalized pigeonhole principle, there must be $k+1=3$ people that are mapped into one group of consecutively filled chairs.

   4. If another person gets sick, does the conclusion from part (c) still hold? Why or why not?
      • Answer: No. If another person gets sick, then there are 8 members to seat in five groups of consecutively filled chairs. But in this case, the inequality $8 > 2 \cdot 5$ does not hold.

2. Prove that given a set of any 38 integers, there exist two in the set whose difference is divisible by 37.
   • Answer: Let $S$ be a (particular but arbitrarily chosen) set of 38 integers. When an integer is divided by 37, by the quotient-remainder theorem, there are 37 possible remainders. Let this set of possible remainders be called $B$. Consider a function from $S$ to $B$ that maps each of the 38 integers to its remainder when divided by 37. Since $n(S) > n(B)$, or equivalently, $38>37$, if we divide each integer in $S$ by 37, there must be at least two that have the same remainder.

     Call that remainder $r$. Now we will show that the difference of the two integers that have a common remainder is divisible by 37.

     So there exist distinct integers $x$ and $y$ in $S$ such that

     $$x \equiv_{37} r$$   and$$\quad y \equiv_{37} r.$$
     Equivalently, by applying the definitions of mod and divides, we get

     $$37 \mid (r - x) \quad 37 \mid (r - y);$$

     $$\exists k,\ell \in {\bf {Z}}\ 37k = r - x \quad 37\ell =r - y.$$

     
     
     Subtracting these equations, we get
     $$37 (k-\ell) = y - x.$$
     Since $k - \ell \in {\bf {Z}}$ by closure of the integers under subtraction,
     $$37 \mid (y - x).$$

3. Prove that there exists a multiple of 37 whose decimal expansion contains only digits 1 and 0.

   Hint: Use the same technique as problem 2.

   • Answer: Consider the set $S = \{1, 11, 111, 1111, \ldots\}$ so that $S$ contains 38 integers whose digits consist of all 1's. By problem 2, we know there exist two integers in $S$ whose difference is divisible by 37 -- or equivalently, whose difference is a multiple of 37. Call these two numbers $x$ and $y$, as in problem 2. So we know $x-y$ is a multiple of 37. We also know $x$ and $y$ consist of all 1's. Suppose $x$ consists of $p$ 1's, and $y$ consists of $q$ 1's, where $p>q$. Then the quantity $x-y$ will clearly consist of $p-q$ 1's followed by $q$ 0's.

4. You are given a sequence of five positive integers: $a_1$, $a_2$, $a_3$, $a_4$, and $a_5$. Prove that either one of them is divisible by 5, or the sum of two or more consecutive elements in the sequence is divisible by 5.

   Hint: Consider the five sums $a_1$, $a_1 + a_2$, $a_1 + a_2 + a_3$, $a_1 + a_2 + a_3 + a_4$, and $a_1 + a_2 + a_3 + a_4 + a_5$. Use the same technique as problem 2.

   • Answer: Assume that none of the five integers is divisible by 5 (if this assumption isn't true, then one of them is divisible by 5 and we are done). Consider the five sums stated above. Assume that none of the five sums is divisible by 5 (again, if this isn't true, then one of the sums is divisible by 5 and therefore a sequence of consecutive elements in the sequence is divisible by 5).

     Since none of the five sums is divisible by 5, by applying the quotient-remainder theorem, there are only four possible remainders when divided by 5. Since there are 5 sums, and $5 > 4$, by the pigeonhole principle, two of the sums must have the same remainder when divided by 5. Call these two sums $x$ and $y$, where $x$ represents the sum that contains more terms.

     Consider the value $x-y$. By the definition of the sums, the terms in $y$ are a subsequence of those in $x$. So when we subtract $y$ from $x$, we will be left with a sequence of consecutive elements of the sequence, that by the technique of problem 2, is divisible by 5. Furthermore, we know this sequence contains at least two members because if it only contains one, then that violates our assumption that none of the terms are divisible by 5.

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: ``There was one day where you wrote at least $x$ lines of code.'' Prove your answer is correct.
   • Answer: Consider a function from the 250 lines of code (set $A$) to the 9 days (set $B$). This function maps each line of code to the day on which is was written. By the generalized pigeonhole principle, we want to find the maximum integral value of $k$ to satisfy the inequality $250 > k \cdot 9$. This value is $27$, since $250 > 27 \cdot 9$ but $250 \leq 28 \cdot 9$. Therefore, there must have been a day when you wrote $k+1=27+1=28$ lines of code.

6. Let the function $f : {\bf {R}}\to {\bf {R}}$ be defined by $f(x) = x^2$, and let $g : {\bf {R}}^$nonneg$\to {\bf {R}}$ be defined by $g(x) = \sqrt{x}$.
   1. Let $h_1 = f \circ g$. Describe $h_1$: give the domain, co-domain, range, and definition of the function itself.
      • Answer: $h_1$ is a function from ${\bf {R}}^$nonneg to ${\bf {R}}$ defined by $h_1(x) = (f \circ g)(x) = f(g(x)) = \left( \sqrt{x} \right)^2 = \vert x\vert = x$. (We know that $\vert x\vert = x$ because $x \geq 0$.) The range of $h_1$ is ${\bf {R}}^$nonneg.

        Note: $\vert x\vert$ denotes the absolute value of $x$, defined as

        $$\vert x\vert = \begin{cases} x & \text{for } x \geq 0 \\ -x & \text{for } x < 0. \end{cases}$$

   2. Let $h_2 = g \circ f$. Describe $h_2$: give the domain, co-domain, range, and definition of the function itself.
      • Answer: $h_2$ is a function from ${\bf {R}}$ to ${\bf {R}}$ defined by $h_2(x) = (g \circ f)(x) = g(f(x)) = \sqrt{x^2} = \vert x\vert$. The range of $h_1$ is ${\bf {R}}^$nonneg.

7. Given a function $f : X \to Y'$ and a function $g : Y \to Z$, explain why you cannot compose $f$ and $g$ (into $g \circ f$) unless the range of $f$ is a subset of (or equal to) $Y$.
   • Answer: If the range of $f$ is not a subset or equal to $Y$, then $f$ maps at least one value in $X$ to some value that is in $Y'$, but not in $Y$. In other words, $\exists a \in X \ \exists b \in Y' - Y \ f(a) = b$. We know that $(g \circ f)(a) = g(f(a)) = g(b)$. But the value $g(b)$ cannot be computed, because the function $g$ only accepts values from its domain, $Y$, but as we stated before, $b \not\in Y$. Therefore, composing $f$ and $g$ in this case is impossible.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -nonavigation -antialias_text -antialias hw13ans

The translation was initiated by Phillip Kirlin on 2004-05-07

Web Accessibility