CMSC 250 Fall 2004 -- Homework 12 Answer

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)$?
   Answer: Observe that whatever way to walk from (0,0,0) to (10,10,10) it must involve exactly 30 steps, while 10 out of 30 are on $x$-axis and 10 out of the remaining 20 are on $y$-axis, and the remaining 10 on the z axis. Therefore these steps can be taken in any order but the steps in the same direction are indistinguishable from each other so answer =
   $${30\choose10}{20\choose10}{10\choose10} = \frac{30!}{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.
   Answer: $g$ is one-to-one. Prove by showing that $\forall x, y \in Z, g(x)=g(y) \to x=y$.
   Proof:
   Let x and y be arbitrary in Z.
   Assume $g(x) = g(y)$
   $\to 4x-5 = 4y-5$ by substitution
   $\to 4x = 4y$ by adding 5 to both sides
   $\to x=y$ by dividing both sides by 4
   
   $g(x) = g(y) \to x=y$ by closing conditional world
   $\forall x, y \in Z, g(x)=g(y) \to x=y$ by generalizing from GP
   $g$ is not onto.
   Disproof by Counter Example.
   Let $g(n)=0$
   $4n-5=0$ by substitution
   $n=5/4$ by algebra
   But $5/4$ is not in ${\bf Z}$ so this is a valid counter example.
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?
      Answer: No. Counterexample:
      Let $f(x) = x$ and $g(x)=-x$. Clearly they are 1-1. But $(f+g)(x) = f(x)+g(x) = x+(-x) = 0$ is clearly not 1-1.
   2. If $f$ and $g$ are both onto, is $f+g$ also onto?
      Answer: No. Counterexample:
      Let $f(x) = x$ and $g(x)=-x$. Clearly they are onto. But $(f+g)(x) = f(x)+g(x) = x+(-x) = 0$ is clearly not onto.
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.
   Answer: No. $f$ is not necessary be onto. Counterexample: Let $f:{\bf Z}\to{\bf Z}$ be defined by $f(x) = abs(x)$ and $g:{\bf Z}\to{\bf Z}^{\geq0}$ be defined by $g(x) = abs(x)$. Where $abs$ represents the absolute value of its argument. Then $g\circ f:{\bf Z}\to{\bf Z}^{\geq0}$ defined by $g\circ f(x) = abs(x)$ is onto, but $f$ is not.
5. Prove that $$\log_a b = \frac{\log_c b}{\log_c a}$$.
   Answer:
   $$\log_a c = \frac{\log_c a\log_a c}{\log_c a} = \frac{\log_a c^{\log_c a}}{\log_c a} = \frac{1}{\log_c a}$$
   $$\log_a b = \log_a c^{\log_c b} = \log_c b \log_a c = \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?
   Answer: No. Counterexample: $\{1,2,3,4,5\}$
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.)
   Answer: Two steps:
   Step 1: Once you pick 10 integers, at least two of them have a digit in common.
   Proof: Each integer you pick will ``occupy'' at least one digit from 1 to 9. By pigeonhole principle the claim holds.
   Step 2: Picking only 9 integers may not cause at least two of them to have a digit in common.
   Proof: by example: pick $\{ 111,222,333,444,555,666,777,888,999 \}$
   Therefore, answer = 10 In other words:
   The domain is the set of numbers picked (we don't know the size of the domain).
   The function is the value of the result of integer division when the selected value is divided by 100 (in other words only looking at the 100's place).
   The codomain are the set of possible answers in that division which are onlly the values 1-9 since the number must be a 3-digit number so the size of the codomain is 9.
   Since we want to be sure the function is not one-to-one, we must have the size of the domain to be 10.
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$.
   Answer: Since none of the $a_i$'s is divisible by $n$, $a_i \bmod n \neq 0$. By quotient remainder theorem, $a_i \bmod n \in \{1,2,...,n-1\}$. Since there are $n$ integers but $n-1$ possible remainders, at least two of the integers will have the same remainders when divided by $n$. Let them be $an+r$ and $bn+r$ where $a,b$ are integers. Then $(an+r)-(bn+r)=(a-b)n$ is divisible by $n$. In other words:
   The domain is the n integers in the series so the size of the domain is n.
   The function is the remainder of integer division of that integer by n.
   The co-domain are the values 1 through n-1 becasue since none of them are divisible by n, these are the only possible values. The size of the codomain is n-1.
   Since the size of the domain is larger than the size of the co-domain and this is a total function, the pigeon hole principle can be applied and we know that this function is not one-to-one. This means that there must be at least two elements in the domain that map to a single element in the codomain. In other words, two of the integers in the domain have the same remainder. Since they have the same remainder, they are equivalent mod n and n divides there difference.

Web Accessibility