CMSC250, Spring 2004 Homework 13

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.

   2. Does the conclusion in part (a) still hold if each member only picks five others to send postcards? Why or why not?

   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.

   4. If another person gets sick, does the conclusion from part (c) still hold? Why or why not?

2. Prove that given a set of any 38 integers, there exist two in the set whose difference is divisible by 37.

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.

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

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.

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.
   2. Let $h_2 = g \circ f$. Describe $h_2$: give the domain, co-domain, range, and definition of the function itself.

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

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 hw13

The translation was initiated by Phillip Kirlin on 2004-04-29

Web Accessibility