Discrete Mathematics Answers

Let S = {a₁,a₂,a₃,...a_n}be a set of test scores. Prove using the the indirect method of proof that if the average of this set of test scores is greater than 90, then at least one of the scores is greater than 90.

For each of these relations on the set {1, 2, 3, 4}, decide

whether it is reflexive, whether it is symmetric, whether

it is antisymmetric, and whether it is transitive.

 {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}

Consider the following relation R on A where A = {1, 2, 3, 4, 5}

aRb ⇔

a

b

< min(a, b)

For example, 2R4 since

2

4

=

1

2

and min(2, 4) = 2 and 1

2

< 2.

(a) Draw the digraph of R (4)

(b) Give a path of length 2 from 3, if any (2)

(c) Give the domain and range of R. (4)

(d) Determine R(2)

a_n = a _0.5n + n, a₁ = 0, where n is a power of 2, is a linear recurrence relation. ( true / falsa ).

Helen wants to buy a bunch of flowers. There are five types of flowers available, namely roses, chrysanthemums, lilies, carnations and tulips. How many possible bunches of 16 flowers can she choose if the bunch must contain no more than two lilies, but any number of the types of flowers.

Use generating function to prove the identity

n

∑

k=o



r

k

 s

n−k



=



r +s

n



Using Boolean algebra simplify the statement ¬(𝑟 → 𝑠) → (¬𝑟) 

1 Let a relation R be represented by the following matrix MR =

1000001 1111000  1 0 1 1 0 1 0 

MR=1 0 0 1 0 0 0

 1 1 0 1 0 0 0  0 1 0 1 1 0 1 0111100

 

Determine whether R is

(a) reflexive

(b) irreflexive

(c) symmetric

(d) asymmetric

(e) antisymmetric

(f) transitive

GIVE REASONS for your answer.

2 Consider the following relation R on A where A = {1, 2, 3, 4,5}

aRb ⇔ ab < min(a, b)

For example, 2R4 since 24 = 12 and min(2,4) = 2 and 12 < 2.

(a) Draw the digraph of R

(b) Give a path of length 2 from 3, if any

(c) Give the domain and range of R.

(d) Determine R

6 a) Show, using the pigeonhole principle, that in any set of 5 integers, at least two have the same remainder when divided by 4.

(b) Use the extended pigeonhole principle to show that there are at least 3 ways of choosing 2 different numbers from 2, 3, 4, 5, 6, 7, 8, 9 so that all choices have the same sum.

7 Decide for each of the following relations whether or not it is an equivalence relation. Give full reasons. If it is an equivalence relation, give the equivalence classes.

(a) Leta,b∈Z. DefineaRbifandonlyif ab ∈Z (4)

(b) Let a and b be integers. Define aRb if and only if 3|(a − b) (In other words R is the

congruence modulo 3 relation

4 What is the probability that an arrangement of a, b, c, e, f, g begins and ends with a vowel?

5 Helen wants to buy a bunch of flowers. There are five types of flowers available, namely roses, chrysanthemums, lilies, carnations and tulips. How many possible bunches of 16 flowers can she choose if the bunch must contains no more than two lilies, but any number of the other types of flowers?