CMSC 250 Fall 2004 -- Homework 12

Due Wed., Nov. 24 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. In a 3-dimensional world, whenever you stand in position $(x,y,z)$, you can proceed one of the positions $(x+1,y,z)$, $(x,y+1,z)$ and $(x,y,z+1)$. How many ways can you walk from the starting position $(0,0,0)$ to the exit $(10,10,10)$?
2. Define $g:{\bf Z}\to{\bf Z}$ by the rule $g(n) = 4n-5$, for all integers $n$. Is $g$ one-to-one? Is $g$ onto? Prove or give counterexamples.
3. Let $f:{\bf R}\to{\bf R}$ and $g:{\bf R}\to{\bf R}$ be functions, and $(f+g):{\bf R}\to{\bf R}$ be defined by $(f+g)(x)=f(x)+g(x)$ for all real numbers $x$.
   1. If $f$ and $g$ are both one-to-one, is $f+g$ also one-to-one?
   2. If $f$ and $g$ are both onto, is $f+g$ also onto?
   Justify your answer.
4. If $f:X\to Y$ and $g:Y\to Z$ are functions and $g\circ f$ is onto, must both $f$ and $g$ be onto? Prove or give a counterexample.
5. Prove that $$\log_a b = \frac{\log_c b}{\log_c a}$$.
6. Let $T=\{1,2,3,4,5,6,7,8,9\}$. Suppose five integers are chosen from $T$. Must there be two integers whose sum is 10? Why?
7. 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.)
8. Suppose $a_1,a_2,...,a_n$ is a sequence of $n$ integers none of which is divisible by $n$. Show that at least one of the differences $a_i-a_j$ (for $i\neq j$) must be divisible by $n$.

Web Accessibility