Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Exam #2

Tues., Nov. 22, 2005

Write all answers legibly on the paper provided. If you need extra paper, raise your hand and request a blank paper - you must put your name on and hand-in any paper you receive. You can also use the back of the last page which is blank. Clearly label any answers that appear on a paper different from where the question appears. You must indicate the continuation of the answer on the paper where the question is and on the paper where the answer is continued. The number of points possible for each question is indicated in square brackets - the total number of points on the exam is 100, and you will have exactly 70 minutes to complete this exam. In order to receive any partial credit, you must show your work, clearly labled in the space provided. You may not use calculators, textbooks or any other external aids during this exam. The formula sheet is attached - this can be removed from the back of the exam and does not need to be handed in at the end.



Important Note: The final exam will be on Saturday, December 17 4:00-6:00pm in EGR 1202. Send mail to your instructor if you have a conflict with another exam at that time.

**** This area is for grading purposes (points lost per page)- Do not write below this line ****

1. [12 pnts.] You have been selected to manage a clothing store, and you need to make some decisions about how to handle situations. You want to make sure you are considering all options when making these decisions - so answer the following questions by giving the formula you would use to solve the problem followed by a solution to a form that includes no more than just addition, subtraction, multiplication, division, factorials and/or exponents. [note: two items of the same color are considered to be identical.]
   1. You need to display the dress shirts you have available by hanging them on two parallel bars that are against a wall (one high and the other low). You have 40 dress shirts: 10 red, 15 white, 3 blue and 17 green. How many ways can they all be hung on these two bars if you do need to hang them all and nothing else is hung on these two bars ? (note: the bars are long enough that all could hang on either the high bar or the low bar. Also note that hanging them all on the top bar looks different and should be counted separately from hanging them all on the low bar.)
      $\frac{46!}{10!15!3!17!}$
      
      
      
      
      
      
      
      
      
      
      
      
      
   2. You also want to display the 50 t-shirts you have available. Since the t-shirts have hand embroidery on them, no two are identical. You decide there is only enough space to dispaly 30 of them on a single bar rack on the back wall of the store. How many ways can you select the order in which the selected t-shirts are hung?
      $P(50, 30) = \frac{50!}{20!}$
   3. You have red scarves (3 of them) and blue scarves (5 of them) that you decide should not be sold in your store. You decide instead to give them to your 12 employees (for free). How many ways could you distribute the scarves among the 12 employees? [note: some employees could get none and there could be one employee that gets all]
      $\frac{(3 + 12 - 1)!}{3! (12 - 1)!} * \frac{(5 + 12 - 1)!}{5! (12 - 1)!}$
      
      
      
      
      
      
      
      
      
      
      
      
      
   4. You have 20 indistinguishable white scarves that you do decide to sell (at a deep discount). The first 6 constomers that come in purchase all of them. Each of the six customers purchases at least one, and they are all gone after the sixth customer leaves the store. How many different ways could the scarves be distributed between those six customers?
      First distribute 6 scarves to 6 customers, then distribute the rest 14 among the 6
      $\frac{(14 + 6 - 1)!}{14! (6 - 1)!}$
      
      
      
      
      
      
      
      
      
      
      
      
      
2. [30 pnts.] For each of the four parts of this question: Either give a counter example to dispove. If you are disproving, you must give specific members for the sets A, B, C, D and U(the universal set) as needed or prove the following statements concerning Sets. Be sure to give the name of the reason which justifies each step you give in the proof.
   1. $\forall A,B,C \in \{$non-empty sets $\}, A \subseteq B \wedge A \subseteq C \rightarrow A \subseteq (B \times C)$
      Counter example:
      $A = \{1\} \hspace{.5in} B = \{1, 2\} \hspace{.5in} C = \{1, 3\}$
      $B \times C = \{(1, 1), (1, 3), (2, 1), (2, 3)\}$
      $A \subseteq B$ because $\{1\} \subseteq \{1, 2\}$
      $A \subseteq C$ because $\{1\} \subseteq \{1, 3\}$
      Therefore the antecedent which is a conjunction of these two is true
      However
      $A \nsubseteq B$ because ${1} \nsubseteq \{(1, 1), (1, 3), (2, 1), (2, 3)\}$
      Therefore the consequent is false.
   2. $\forall A,B,C \in \{$non-empty sets $\}, (A \times B) - (A \times C) \subseteq A \times (B \cup C)$

      Let A, B and C be arbitrary non empty sets
      Let (x, y) be arbitraty in U
      Assume $(x, y) \in (A \times B) - (A \times C)$
      $(x, y) \in A \times B \wedge (x, y) \not \in A \times C$	by def. of set diff.
      $(x, y) \in A \times B$	by conj. simp.
      $x \in A \wedge y \in B$	by def. of $\times$
      $x \in A$	by conj. simp.
      $y \in B$	by conj. simp.
      $y \in B \vee y \in C$	by disj. add.
      $y \in (B \cup C)$ 7by def. of union
      $x \in A \wedge y \in (B \cup C)$	by conj. add.
      $(x, y) \in A \times (B \cup C)$	by def of $\times$
      $(x, y) \in (A \times B) - (A \times C) \rightarrow (x, y) \in A \times (B \cup C)$	by C.C.W. without contradiction
      $\forall (x, y) \in (A \times B) - (A \times C) \rightarrow (x, y) \in A \times (B \cup C)$	by Gen. from G.P.
      $(A \times B) - (A \times C) \subseteq A \times (B \cup C)$	by def. of subset
      $\forall A,B,C \in \{$non-empty sets $\}, (A \times B) - (A \times C) \subseteq A \times (B \cup C)$	by Gen. from G.P.

   3. $\forall A,B,C \in \{$non-empty sets $\}, ((A-C) \cap (B-C) \cap (A-B)) \subseteq C$

      $(A - C) \cap (B - C) \cap (A - B)$
      $= (A \cap C') \cap (B \cap C') \cap (A \cap B')$	Alternative representation of set diff.
      $= (A \cap A \cap C') \cap (B \cap B')$	assoc. and comm.
      $= (A \cap A \cap C') \cap \varnothing$	intersection with comp.
      $= \varnothing$	intersection with empty set
      $\varnothing \subseteq C$	since the empty set is a subset of every set
      $(A - C) \cap (B - C) \cap (A - B) \subseteq C$	by substitution

3. [43 pnts.] For all of the parts of this question: Either find a specific counter example or prove each of the indicated statements is true. When using induction to prove something true, you must only use strong induction if it is required by that problem - using strong induction to prove something that only required regular induction, will result in a loss of points. You must use induction of some form to prove any and all of the following statements that are true.
   1. 
      
      $$\forall n \in Z^+, \sum_{i=1}^n (2i-1) = n^2$$
      
      
      Base Case (n = 1)
      LHS: $\sum_{i=1}^n (2i-1) = \sum_{i=1}^1 (2i-1) = 2(1) - 1 = 2 - 1 = 1$
      RHS: $n^2 = 1^2 = 1$
      IH $(n = k) \sum_{i=1}^k (2i-1) = k^2$
      IS$(n = k + 1)$
      show: $\sum_{i = 1}^{k + 1} (2i-1) = k^2$
      proof:
      

      $\sum_{i = 1}^{k + 1}(2i - 1)$
      $= \sum_{i = 1}^{k}(2i - 1) + \sum_{i = k + 1}^{k + 1}(2i - 1)$	by series sep.
      $=\sum_{i = 1}^{k}(2i - 1) + (2(k + 1) - 1)$	by series expansion
      $=\sum_{i = 1}^{k}(2i - 1) + (2k + 1)$	algebra
      $= k ^ 2 + (2k + 1)$	by IH
      $= (k + 1)^ 2$	algebra

   2. Let $q \in Z^{\geq 2}$, let $r \in \{0,1,2,...,q-1\}$, and let $c \in Z.$
      Let $\{a_n\}$ be a sequence with the following properties:
      $a_1 \equiv_q r$ and $a_2 \equiv_q r$ and
      $\forall n \in Z^{\geq 3}, a_n = (c)a_{n-1} + (q - c + 1)a_{n-2}$
      
      Statement that must be proved or disproved: $\forall k \in Z^{\geq 1}, a_k \equiv_q r$ Base Case (k = 1, k = 2)
      $k = 1, a_k = a_1, a_1 \equiv_q r, a_k \equiv_q r$
      $k = 2, a_k = a_2, a_2 \equiv_q r, a_k \equiv_q r$
      IH $(k = p, \forall p \in Z 1 \leq p < y) a_p \equiv_q r$
      IS$(k = y)$
      show: $a_y \equiv_q r$
      proof:
      

      $a_y = (c) a_{y - 1} + (q - c + 1) a_{y - 2}$
      $y - 1 \in Z, y - 2 \in Z$	by closure of Z in sub.
      $y - 1 < y, y - 2 < y$	by subtracting positive integer
      $1 \leq y - 1, 1 \leq y - 2$	$y \geq 3$
      $a_{y - 1} \equiv_q r, a_{y - 2} \equiv_q r$	by I.H.
      $\exists f \in Z, a_{y - 1} = qf + r$	def. of mod.
      $\exists g \in Z, a_{y - 2} = qg + r$	def. of mod.
      $a_y = ca_{y - 1} = (q - c + 1)a_{y - 2}$
      $= c(qf + r) + (q - c + 1)(qg + r)$	alg.
      $= cqf + cr + (q - c + 1)qg + (q - c + 1)r$	alg.
      $= q(cf + (q - c + 1)g) + r(c + q - c + 1)$	alg.
      $= q(cf + (q - c + 1)g) + r(q + 1)$	alg.
      $= q(cf + (q - c + 1)g) + rq + r$	alg.
      $= q(cf + (q - c + 1)g + r) + r$	alg.
      $a_y \equiv_q r$	def. of mod.

   3. $\forall n \in Z^{\geq 3}, 2n+1 < 2^n$ Base Case (n = 3)
      LHS: $2(3) + 1 = 6 + 1 = 7$
      RHS: $2 ^ 3 = 8$
      $7 < 8$
      so LHS $<$ RHS
      IH $(n = k) 2k + 1 < 2 ^ k$
      IS$(n = k + 1)$
      show: $2(k + 1) + 1 < 2 ^{k + 1}$
      proof:
      

      $2k + 1 < 2 ^ k$	by IH
      $2k + 1 + 2 < 2 ^ k + 2$	adding both side by 2
      $2k + 3 < 2 ^ k + 2$	alg
      $2(k + 1) + 1 < 2 ^ k + 2$	alg.
      Assume $2 ^ k + 2 > 2^{k + 1}$
      $2 ^ {k - 1} + 1 > 2^k$	dividing by 2
      $1 > 2 ^ k - 2 ^ {k - 1}$
      $1 > 2 ^ {k - 1}$	alg.
      $k - 1 \geq 3$
      $2 ^ {k - 1} > 2 ^ 2 = 4$
      contradiction
      $2 ^ k + 2 \leq 2^{k + 1}$	CCW with contradiction
      $2(k + 1) + 1 < 2 ^ k + 2 \leq 2^{k + 1}$	transitivity
      $2(k + 1) + 1 < 2 ^{k + 1}$

4. [15 pnts.] You do not need to explain the process for the ones in this set, you only need to show the formula and then solve it. NOTE: You do not have to do all of the arithmetic, but you do have to get each answer to a form that includes ONLY: addition, subtraction, multiplication, division, exponents and factorials.
   1. A balanced 6 sided die is thrown three times and the resulting sequence of digits on the upper face is recorded. What is the probability that either all three recorded values are equal or that none of them is a three? $\frac{6}{6^3} + \frac{5^3}{6^3} - \frac{5}{6^3}$
      or
      $\frac{5*5*5 + 1}{6^3}$
      
      
      
      
      
      
      
      
      
      
      
   2. There are three red balls and four white balls in a box. Four balls are selected at random from these balls. Find the probability that exactly two of the selected balls are red and two are white.
      $\frac{{3 \choose 2}{4 \choose 2}}{{7 \choose 4}} = \frac{\frac{3!}{2!1!} * \frac{4!}{2!2!} }{\frac{7!}{4!3!}} = \frac{18}{35}$
      
      
      
      
      
      
      
      
      
      
      
   3. If you have a bit string of length 10 that has exactly three ones, what is the probability that it either starts and/or ends with a 1. (note: A bit string is made of only 1's and 0's.) $\frac{{8 \choose 2} + {8 \choose 2} + {8 \choose 1}}{{10 \choose 3}} = \frac{\frac{8 * 7}{2} + \frac{8 * 7}{2} + 8 }{120} = \frac{15}{8}$
      or
      $\frac{{9 \choose 2} + {9 \choose 2} - {8 \choose 1}}{{10 \choose 3}} = \frac{\frac{9 * 8}{2} + \frac{9 * 8}{2} + 8 }{120} = \frac{15}{8}$
      
   This page intentionally blank for you to have extra paper to continue any answer that took more room than the space provided.
   This page intentionally blank for you to have extra paper to continue any answer that took more room than the space provided.

Web Accessibility