# IST 230

REVIEW SECTION (30 points)

Chapter 1

State and prove the converse of “if x-1 is an even integer, then x-2 is an odd integer” using the proof format given in the example proof in the February 5 announcement. (5 points)

Chapter 2

2. True or False: If A = {x: x is the square of an integer} and B = {z: z is an integer}, then B is a subset of A. (5 point)

Chapter 3

3a. Let the function f from the integers to the natural numbers be defined by f(x) = x*x (where * is ordinary multiplication in the natural numbers). Determine whether f is one-to-one, and explain why it is or isn’t. (2 points)

3b. Let sets A and B be defined as follows: A = {a1, a2} and B = {b1}. List as set(s) of ordered pairs all onto functions from A to B; if there are no onto functions from A to B, explain why not. (3 points)

Chapter 5

5. Let the set A be defined as A = {a, b, c, d}, and let the relations R and S on the set A be defined as

R = {(d, a), (a, b), (b, c)}, and S = {(a, a), (b, d), (d, c)}.

Explain why the ordered pair (a, d) is or is not an element of the composition of R and S (denoted S o R). (5 points)

Chapter 6

6. What is the value of the variable count after all the loops in the following pseudocode execute? (5 points)

count:=0

For i= 1 to 2

For j=1 to 2

count:=2j(count)

End-for

End-for

Chapter 7

7. Prove by mathematical induction that 2+4+6+…+2n = n(n+1) for all positive integers n. (5 points)

NEW MATERIAL (70 points)

Chapter 8

8a. Show calculations and determine how many digits are needed to represent the base 5 expansion of 1024 (where 1024 is in base 10). Then write the base 5 expansion of 1024. (5 points)

8b. Explain why a multiplicative inverse mod 10 of 7 does or does not exist. If one does exist, calculate it, and explain why there is or is not only one such multiplicative inverse. If one does not exist, explain why not. (10 points)

Chapter 9

9a. Given sets A = {a1, a2} and B = {b1, b2}, let the function f from A to B be given by the following set of ordered pairs. If f has an inverse function, call it g, and write g as a set of ordered pairs. If f does not have an inverse function, explain why it doesn’t. (10 points)

f = { (a1, b1), (a2, b2) }

9b. List all the ways to form a committee of three people consisting of a chair, a secretary, and a worker bee. Designate the chair by c, the secretary by s, the worker bee by w, and the three people by p1, p2, and p3. (5 points)

9c. Let A = {1, 2, 3, 4, 5}. Consider a subset of A that contains exactly two elements. For instance, {1, 2} is such a subset. Call such a subset a ‘2-subset’ of A. Similarly, consider a subset of A that contains exactly three elements. For instance {1, 2, 3} is such a subset. Call such a subset a ‘3-subset’ of A. Let B equal the set of all 2-subsets of A, , and let C equal the set of all 3-subsets of A. Explain why there is or is not a bijection between the sets B and C. (10 points)

Chapter 10

10a. Let A = {a, b, c}. Use the standard lexicographic order for words in English and the ‘<‘ symbol to designate this order relation. Write a complete list of all ordered 3-tuples from the set A, using the ‘<‘ symbol to show lexicographic order.

(10 points)

10b. Explain why it is or is not the case that among a group of eleven people there are at least two people whose birthday falls in the same month. (10 points)

Chapter 11

11a. An experiment is performed to flip a fair coin 10 times and observe the outcome of each flip: heads (labeled ‘H’) or tails (labeled ‘T’). For instance, one outcome, written as a 10-tuple, might be (H,T,T,T,T,T,T,H,H,H). (10 points)

a. How many total outcomes are there for this experiment? Explain your reasoning.

b. How many ways can the result of the experiment show exactly nine tails? Explain your reasoning.