Discrete Mathematics Answers

Draw the directed graph that represents the relation {(a,a), (a, b), (b, c), (c, d), (a, d), (b, d), (d, b)}.

Suppose a recurrence relation

an=2an−1−an−2

where a1=7 and a2=10

can be represented in explicit formula, either as:

Formula 1:

an=pxn+qnxn

       or  

Formula 2:

an=pxn+qyn

where 

x

and

y

are roots of the characteristic equation.

  Determine p and q

List the quadruples in the relation { a,b,c,d} where a, b, c, d are integers with

0 < a < b < c < d < 8.

Determine whether the following relation is reflexive, symmetric, antisymmetric and/or transitive.

(x, y) ∈ R if x ≥ y, where R is the set of positive integers.

A survey of 119 persons was conducted at TTC, and it was found that 89 persons carried a cell phone, 10 person carried a tablet computer, and 8 carried both cellphone and tablet.

1. how many people carried a cellphone or a tablet?
2. how many people carry neither a cell phone nor a tablet? 
3. how many people carried a cell phone only?
4. how many people carried a tablet but not a cell phone?

a. Construct a truth table for (~p ˄ r) ˅ (q ˄ ~r).

b. Use the truth table that you constructed in part to determine the truth value of (~p ˄ r) ˅ (q ˄ ~r), given that

p is false, q is true, and r is false.

Construct a truth table for (~p ˄ r) ˅ (q ˄ ~r).

State the Pigeonhole Principle. In a result sheet of a list of 60 students, each marked “Pass” or “Fail

“. There are 35 students pass. Show that there are at least two students pass in the list exactly nine

students apart. (for example students at numbered 2 and 11 or at numbered 50 and 59 satisfy the

condition).

State the Pigeonhole Principle. A chess player wants to prepare for a championship match by playing

some practice games in 77 days. She wants to play at least one game a day but no more than 132

games altogether. Prove that there is a period of consecutive days within which she plays exactly 21

games

4.      In Exercises i) and ii) determine whether the given graph has a Hamilton circuit. If it does, find such a circuit. If it does not, give an argument           

5.      Suppose that G is a connected multigraph with 2k vertices of odd degree. Show that there exist k subgraphs that have G as their union, where each of these subgraphs has a Euler path and where no two of these subgraphs have an edge in common.