Discrete Math (see the attachment)

Discrete Math Final Exam Study Guide Name:___________________________

1. Prove by contradiction that 7 is irrational.

2. Indicate whether the argument is valid or invalid. Support your answer by drawing

diagrams.

All teachers occasionally make mistakes.

No gods ever make mistakes.

No teachers are gods.

3. Determine whether the statement is true or false. Justify your answer with a proof or a

counterexample, as appropriate.

The difference between any odd integer and any even integer is odd.

4. Use the following definition to prove the following statement: for all real numbers c, if c

is a root of a polynomial with rational coefficients, then c is a root of a polynomial with

integer coefficients.

Definition: A number c is called a root of a polynomial p(x) if, and only if, p(c)=0.

5. Determine whether the statement is true or false. Justify your answer with a proof or a

counterexample, as appropriate.

For all real numbers a and b, baba 

6. Prove that for all integers b, if 2

b is odd then b is odd.

7. a) How many ways can the letters in the word COMPUTER be arranged in a row?

b) How many ways can the letters of the word COMPUTER be arranged if the letters CO

must remain next to each other as a unit?

8. a) How many even integers are between 1 and 100?

b) How many odd integers are between 1 and 100?

e) What is the probability that a randomly chosen number between 1 and 100 is even?

8. There are 15 students.

a) How many ways can a committee of six be selected?

b) Suppose that this group of students has eight boys and seven girls.

i) How many committees of six contain three boys and three girls?

ii) How many committees of six contain at least one girl?

9. Suppose that 4 tables in a production run of 50 are defective. A sample of 7 is to be

selected to be checked for defects.

a. How many different samples can be chosen?

b. How many samples will contain at least one defective table?

c. What is the probability that a randomly chosen sample of 7 contains at least one defective

table?

10. a) Define f: ZZ  by the rule f(n) = 7n-8, for all integers n.

i) Is f one-to-one? Prove or give a counterexample.

ii) Is f onto? Prove or give a counterexample.

iii) b) Define F: RR  by the rule F(x) = 7x-8 for all real numbers x. Is F onto?

Prove or give a counterexample.

11. Use mathematical induction to verify that 6

)12)(1( ......4321

2222  

nnn n .

12. Determine whether the given binary relation is reflexive, symmetric, transitive, or none

of these. Justify your answers.

A is the set of people living in the word today. A relation R is defined on A as follows:

For all p, q from A, p R q  p lives within 100 miles of q.

13. F is the relation defined on Z as follows: For all Znm , , m F n  5| (m-n).

Is F an equivalence relation?

14. In a group of 15 people, is it possible for each person to have exactly 3 friends? Explain.

15. Either draw a graph with the given specifications or explain why no such graph exists.

Tree with 7 vertices, 6 edges

16. a)Find adjacency matrix for the following (undirected) graph:

b) Let

  





  







012

101

211

A , where A is an adjacency matrix

How many walks of length 2 are there from 1

v to 3

v ?

17. Draw binary tree to represent the following expression: )/( cdab 

18. Prove for all integers 3n that P(n+1,3)-P(n,3)=3P(n,2).

19. Let A, B, C be events in a sample space S such that CBAS  . Suppose that

P(A)=0.4, P(B)=0.5, and .1.0)(  BAP Find each of the following:

a) P ( )BA 

b) P )( CC

BA 

e3

e4

v4

e5

v3

e6

v2

e2

e1

v1