Category: Discrete Mathematics Objective Questions

Discrete Mathematics Quiz on “Cartesian Product of Sets”.

1. Let set A = {1, 2} and C be {3, 4} then A X B (Cartesian product of set A and B) is?
a) {1, 2, 3, 4}
b) {(1, 3),(2, 4)}
c) {(1, 3), (2, 4), (1, 4), (2, 3)}
d) {(3, 1), (4, 1)}

Answer: c
Clarification: In set A X B : {(c , d) |c ∈ A and d ∈ B}.

2. If set A has 4 elements and B has 3 elements then set n(A X B) is?
a) 12
b) 14
c) 24
d) 7

Answer: a
Clarification: The total elements in n(A X B) = n(A) * n(B).

3. If set A has 3 elements then number of elements in A X A X A are __________
a) 9
b) 27
c) 6
d) 19

Answer: b
Clarification: n(A X A X A) = n(A)* n(A)* n(A).

4. Which of the following statements regarding sets is false?
a) A X B = B X A
b) A X B ≠ B X A
c) n(A X B) = n(A) * n(B)
d) All of the mentioned

Answer: a
Clarification: The Cartesian product of sets is not commutative.

5. If n(A X B) = n(B X A) = 36 then which of the following may hold true?
a) n(A)=2, n(B)=18
b) n(A)=9, n(B)=4
c) n(A)=6, n(b)=6
d) None of the mentioned

Answer: c
Clarification: n(A) should be equal to n(B) for n(A X B) = n(B x A).

6. If C = {1} then C X (C X C) = (C X C) X C the given statement is true or false.
a) True
b) False

Answer: b
Clarification: The Cartesian product is not associative, (C × C) × C = { ((1, 1), 1) } ≠ { (1,(1, 1)) } = C × (C × C).

7. Let the sets be A, B, C, D then (A ∩ B) X (C ∩ D) is equivalent to __________
a) (A X C) ∩ (B X D)
b) (A X D) U (B X C)
c) (A X C) U ( B X D)
d) None of the mentioned

Answer: a
Clarification: (A ∩ B) X (C ∩ D) = (A X C) ∩ (B X D) but in case of unions this is not true.

8. If A ⊆ B then A X C ⊆ B X C the given statement is true or false.
a) True
b) False

Answer: a
Clarification: Let an arbitrary element x ∈ A and y ∈ C, then x ∈ B (subset property), (x,y) ∈ AX C also (x,y) ∈ B X C. This implies A X C ⊆ B X C.

9. If set A and B have 3 and 4 elements respectively then the number of subsets of set (A X B) is?
a) 1024
b) 2048
c) 512
d) 4096

Answer: d
Clarification: The A X B has 12 elements, then the number of the subset are 2 12 = 4096.

10. If set A X B=B X A then which of the following sets may satisfy?
a) A={1, 2, 3}, B={1, 2, 3, 4}
b) A={1, 2}, B={2, 1}
c) A={1, 2, 3}, B={2, 3, 4}
d) None of the mentioned

Answer: b
Clarification: For set A X B = B X A, this is possible only when set A = B.

Discrete Mathematics Multiple Choice Questions on “Properties of Matrices”.

1. The determinant of identity matrix is?
a) 1
b) 0
c) Depends on the matrix
d) None of the mentioned

Answer: a
Clarification: In identity matrix a_ii = 1, and all other elements = 0, hence the determinant is 1.

2. If determinant of a matrix A is Zero than __________
a) A is a Singular matrix
b) A is a non-Singular matrix
c) Can’t say
d) None of the mentioned

Answer: a
Clarification: Determinant of singular matrices are zero.

3. For a skew symmetric even ordered matrix A of integers, which of the following will not hold true?
a) det(A) = 9
b) det(A) = 81
c) det(A) = 7
d) det(A) = 4

Answer: c
Clarification: Determinant of a skew symmetric even ordered matrix A is a perfect square.

4. For a skew symmetric odd ordered matrix A of integers, which of the following will hold true?
a) det(A) = 9
b) det(A) = 81
c) det(A) = 0
d) det(A) = 4

Answer: c
Clarification: Determinant of a skew symmetric odd ordered matrix A is always 0.

5. Let A = [ka_ij]_nxn, B = [a_ij]_nxn, be an nxn matrices and k be a scalar then det(A) is equal to _________
a) Kdet(B)
b) Kⁿdet(B)
c) K³det(b)
d) None of the mentioned

Answer: b
Clarification: The scalar is multiplied with each of the element of matrix A then determinant is multiplied, the number of row times to the scalar i.e. Kⁿdet(B).

6. The Inverse exist only for non-singular matrices.
a) True
b) False

Answer: a
Clarification: Since for singular matrix det(A)=0.Hence Inverse does not exist.

7. If for a square matrix A and B, null matrix O, AB = O implies BA=O.
a) True
b) False

Answer: b
Clarification: Let A = [0 1 0 0], B = [1 0 0 0]AB=O and BA is not equal to O.

8. If for a square matrix A and B,null matrix O, AB = O implies A=O and B=O.
a) True
b) False

Answer: b
Clarification: Let A = [0 1 0 0], B = [1 0 0 0]AB=O and B, A is not equal to O.

9. Let A be a nilpotent matrix of order n then?
a) Aⁿ = O
b) nA = O
c) A = nI, I is Identity matrix
d) None of the mentioned

Answer: a
Clarification: n is the smallest possible number such that An = O.

10. Which of the following property of matrix multiplication is correct?
a) Multiplication is not commutative in general
b) Multiplication is associative
c) Multiplication is distributive over addition
d) All of the mentioned

Answer: d
Clarification: Matrix multiplication is associative, distributive, but not commutative.

Basic Discrete Mathematics Questions and Answers on “Number Theory and Cryptography – Rules of Exponents”.

1. For some number b, (¹⁄_b)^-n is equal to _________
a) -bⁿ
b) n^b
c) bⁿ
d) none of the mentioned

Answer: c
Clarification: b^-1 reciprocal of b.

2. If ab = 1, where a and b are real numbers then?
a) a = b^-1
b) b = a
c) a = b = 2
d) none of the mentioned

Answer: a
Clarification: This means that a is inverse of b or b is inverse of a.

3. If a is a real number than a⁰ is defined as _________
a) 0
b) a
c) 1
d) -1

Answer: a
Clarification: Any number to the power zero is one.

4. For some number a, b and c, c^a x c^b is equal to _________
a) c^a-b
b) c^a+b
c) c
d) none of the mentioned

Answer: b
Clarification: If base are same then exponenents powers are added.

5. For some number a, b and c, c^a/c^b is equal to _________
a) c^a-b
b) c^a+b
c) c
d) None of the mentioned

Answer: a
Clarification: If base are same then exponenents powers are added, 1/c^b = c^-b.

6. State whether the given statement is true or false.
Exponentiation is commutative.
a) True
b) False

Answer: b
Clarification: A^b is not equal to b^A, exponentiation is not commutative.

7. State whether the given statement is true or false.
Exponentiation is associative.
a) True
b) False

Answer: b
Clarification: Exponentiation is not associative.

8. If 2^a-b = 1 then the value of a-b is equal to _________
a) 1
b) 0
c) 2
d) none of the mentioned

Answer: b
Clarification: 1 = 2⁰, so a-b = 0.

9. For some number a, b and c, a^c x b^c is equal to _________
a) (ab)^c
b) (ac)^b
c) (cb)^a
d) None of the mentioned

Answer: a
Clarification: If power are same then bases are multiplied.

10. If 0^a is not equal to zero then which of the values a cannot take _________
a) 1
b) 2
c) -1
d) 0

Answer: d
Clarification: a⁰ = 1, for any real number.

Discrete Mathematics Multiple Choice Questions on “Counting – Division of Objects”.

1. For a gaming competition, 8 girls are planning on splitting up into 3 (non-empty) groups. How many ways can they split up into these groups?
a) 465
b) 1056
c) 966
d) 3215

Answer: c
Clarification: Using the inclusion-exclusion principle, the total number of ways of splitting the girls into 3 groups is 3⁸ + 3.(2⁸) + 3.(1⁸). However, since the three groups are identical we need to divide by 3!. Hence, the answer is 966.

2. In a picnic with 20 persons where 6 chocolates will be given to the top 8 children(the chocolates are distinct: first, second). How many ways can this be done?
a) ¹⁸C₆
b) ²⁰P₆
c) ²⁵C₄ * 6!
d) ¹⁹P₅

Answer: b
Clarification: This is a permutation problem since the chocolates are distinct. The answer is P(20, 6) -> the number of ways to arrange 20 things taken 6 at a time -> which is (frac{20!}{(20-6)!}) = 20*19*18*17*16*15.

3. How many ways can one choose 20 cookies from 45 different types (assuming there are at least 20 of each type)?
a) ⁶⁴C₂₁ * 15
b) ⁶⁴C₂₀
c) ⁴⁴C₂₀ * 2!
d) ⁶⁵C₂₂

Answer: b
Clarification: Imagine the 20 cookies one is choosing are indistinguishable dots. The 45 different types of cookies are like 45 distinguishable boxes and so the answer is C(45 + 20-1, 20) = ⁶⁴C₂₀.

4. Assume that it is an afternoon. What is the time on the 24 hour clock after 146 hours?
a) 12:10 pm
b) 8:30 am
c) 3 am
d) 2 pm

Answer: d
Clarification: Divide 146 with 24. The remainder is the time on the 24 hour clock. So, 146 = 6*24 + 2 and the result is 2pm.

5. There are 28 identical oranges that are to be distributed among 8 distinct girls. How many ways are there to distribute the oranges?
a) ²²P₇
b) ³⁴C₆
c) ³⁵C₇
d) ²⁸C₈

Answer: c
Clarification: By the definition of star and bar problem, there are ^n+r-1C_r-1 possible distributions of n identical objects among r distinct bins. Now, there are n = 28 identical objects and r = 8 distinct bins. Using the formula above, there are ³⁵C₇ ways to distribute the oranges.

6. There are 5 distinct fruits. How many ways can they be planted into identical fruit plants?
a) 87
b) 52
c) 76
d) 128

Answer: b
Clarification: These fruits can be placed into 1, 2, 3, 4 or 5 fruit plants. The number of distributions of fruits into fruit plants will thus be the sum of Stirling numbers of the second kind: S(5,1) + S(5,2) + S(5,3) + S(5,4) + S(5,5) = 1 + 15 + 25 + 10 + 1 = 52.

7. A woman has 14 identical pens to distribute among a group of 10 distinct students. How many ways are there to distribute the 14 pens such that each student gets at least one pencil?
a) ¹⁵C₁₀
b) ¹⁰C₅ * 11
c) ¹⁵C₈ * 4!
d) ¹³C₉

Answer: d
Clarification: For this type of problem, n>=r must be true and so according to stars and bars model, the number of possible arrangements of stars and bars is n-1Cr-1 or equivalently, there are ^n-1C_r-1 distributions of n identical objects into r distinct non-empty bins. In this example, there are n = 14 identical objects to be distributed among r=10 distinct bins. Using the above formula, the number of possible distributions is ¹³C₉.

8. Suppose that M is the product of k distinct primes. Find the number of ways to write N as the product of positive integers(>1), where the order of terms does not matter.
a) ^MC_N-k
b) ^NC_M
c) N * B_k
d) B_k

Answer: d
Clarification: To solve the problem first find the prime factorization of each term of the product, and place the factors of each term into a box. Then, since N is the product of distinct prime factors, each prime factor appears in a unique box. Since the product of all of these terms is N, each prime factor must be in a box. Conversely, for any arrangement of these n distinct primes into r identical boxes, multiply the primes in a box to create a term and the product of these terms results in N. This establishes the bijection and the number of ways is B_k which is Bell number.

9. How many ways are there to place 7 differently colored toys into 5 identical urns if the urns can be empty? Note that all balls have to be used.
a) 320
b) 438
c) 1287
d) 855

Answer: d
Clarification: The problem can be described as distinct objects into any number of identical bins and this number can be found with B₇ = ∑S(7,k), where S(7,k) is the number of distributions of 5 distinct objects into k identical non-empty bins, so that S(7,1) = 1, S(7,2) = 63, S(7,3) = 301, S(7,4) = 350 and S(7,5) = 140. These values can be found using the recurrence relation identity for Stirling numbers of the second kind. Thus, B₇ = 1 + 63 + 301 + 350 + 140 = 855.

10. Suppose, there are 7 of your friends who want to eat pizza (8 distinct people in total). You order a 16-cut pizza (16 identical slices). How many distributions of pizza slices are there if each person gets at least one slice of pizza?
a) 346
b) 6435
c) 3214
d) 765

Answer: b
Clarification: This problem can be viewed as identical objects distributed into distinct non-empty bins. Using the formula for these kind of distributions ^n-1C_r-1 = ¹⁵C₇ = 6435. Thus, there are distributions of the pizza slices.

Discrete Mathematics Multiple Choice Questions on “Number of Relations”.

1. How many binary relations are there on a set S with 9 distinct elements?
a) 2⁹⁰
b) 2¹⁰⁰
c) 2⁸¹
d) 2⁶⁰

Answer: c
Clarification: S is the set with 9 elements. A relation on S is defined as S x S. There are 9² number of ordered pairs in relation. So, the number of binary relations is 2^(9*9) = 281.

2. _________ number of reflexive relations are there on a set of 11 distinct elements.
a) 2¹¹⁰
b) 3¹²¹
c) 2⁹⁰
d) 2¹³²

Answer: a
Clarification: Let A be a set consists of n distinct elements. There are 2^(n*n)-n number of reflexive relations that can be formed. So, here the answer is 2^(11*11)-11 = 2¹¹⁰.

3. The number of reflexive as well as symmetric relations on a set with 14 distinct elements is __________
a) 4¹²⁰
b) 2⁷⁰
c) 3²⁰¹
d) 2⁹¹

Answer: d
Clarification: Let A be a set consists of n distinct elements. There are 2^(n*(n-1))/2 number of reflexive and symmetric relations that can be formed. So, here the answer is 2^14*(14-1)/2 = 2⁹¹.

4. The number of symmetric relations on a set with 15 distinct elements is ______
a) 2¹⁹⁶
b) 2⁵⁰
c) 2³²⁰
d) 2⁷⁸

Answer: a
Clarification: Let S be a set consists of n distinct elements. There are 2^(n-1)*(n-1) number of reflexive and symmetric relations that can be formed. So, here the answer is 2^{(15-1)*(15-1)} = 2¹⁹⁶.

5. Suppose S is a finite set with 7 elements. How many elements are there in the largest equivalence relation on S?
a) 56
b) 78
c) 49
d) 100

Answer: c
Clarification: Let R is an equivalence relation on the set S and so it satisfies the reflexive, symmetric and transitive property. The largest equivalence relation means it should contain the largest number of ordered pairs. Since we can have n² ordered pairs in R x R where n belongs to S and all these ordered pairs are present in this relation; its the largest equivalence relation.So there are n² elements i.e 7² = 49 elements in the largest equivalence relation.

6. ________ is the rank of the largest equivalence relation on a set of 20 elements.
a) 3²⁰
b) 2⁴⁰⁰
c) 20
d) 1

Answer: d
Clarification: The rank of an equivalence relation is the number of an equivalence classes. If we have a₁, a₂, a₃, …, a_n elements then a₁ and a₂ will be in the same equivalence class because everything is related and so on. In this case, there is only one equivalence class.

7. How many elements are there in the smallest equivalence relation on a set with 8 elements?
a) 10²
b) 8
c) 48
d) 32

Answer: b
Clarification: Let R is an equivalence relation on the set S with n elements and so it satisfies reflexive, symmetric and transitive properties. The smallest equivalence relation means it should contain minimum number of ordered pairs i.e along with symmetric and transitive properties it must always satisfy reflexive property. So, the smallest equivalence relation will have n ordered pairs and so the answer is 8.

8. The rank of smallest equivalence relation on a set with 12 distinct elements is _______
a) 12
b) 144
c) 136
d) 79

Answer: a
Clarification: In the case of smallest equivalence relation, each element is in one equivalence class like {a₁}, {a₂}, … are equivalence classes. So, the rank or number of equivalence classes is n for a set with n elements and so the answer is 12.

9. If a set A has 8 elements and a set B has 10 elements, how many relations are there from A to B?
a) 2⁹⁰
b) 3⁸⁰
c) 164
d) 2⁸⁰

Answer: d
Clarification: Let, a relation R from A to B is a subset of A×B. As the maximum number of subsets (Elements in the powerset) is 2^mn, there are 2^mn number of relations from A to B and so the answer is 2⁸⁰.

10. Synonym for binary relation is _______
a) equivalence relation
b) dyadic relation
c) orthogonal relation
d) one to many relations

Answer: b
Clarification: A binary relation on a set S is a set of ordered pairs of elements of S. It is a subset of the cartesian product S² = S x S. The terms correspondence, dyadic relation and 2-place relation are synonyms for the binary relation.

Discrete Mathematics Multiple Choice Questions on “Trees – Cycles”.

1. If two cycle graphs Gm and Gn are joined together with a vertex, the number of spanning trees in the new graph is ______
a) m+n-1
b) m-n
c) m*n
d) m*n+1

Answer: c
Clarification: As there are n possible edges to be removed from G and m edges to be removed from G and the rest from a spanning tree so the number of spanning tree in the new graph is m*n.

2. For an n-vertex undirected graph, the time required to find a cycle is ____________
a) O(n)
b) O(n²)
c) O(n+1)
d) O(logn)

Answer: a
Clarification: The existence of a cycle in directed and undirected graphs can be determined by depth-first search (DFS) of the graph finds an edge that points to an ancestor of the current vertex. In an undirected graph, finding any already visited vertex will indicate a back edge. All the back edges which DFS skips over are part of cycles. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.

3. A binary cycle space forms a ______ over the two element field.
a) triangular graph
b) vector space
c) binary tree
d) hamiltonian graph

Answer: b
Clarification: The term cycle refers to an element of the cycle space of a graph. There are many cycle spaces. The most common is the binary cycle space, which contains the edge sets that have even degrees at every vertex and it forms a vector space over the two-element field.

4. If G is a simple graph with n-vertices and n>=3, the condition for G has a Hamiltonian circuit is __________
a) the degree of each vertex is at most n/2
b) the degree of each vertex is equal to n
c) the degree of every vertex is at least n+1/2
d) the degree of every vertex in G is at least n/2

Answer: d
Clarification: A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit. If there is a vertex of degree one in a graph then it is impossible for it to have a Hamiltonian circuit. If G is a simple graph with n-vertices and n>=3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit.

5. What is a separable graph?
a) A disconnected graph by deleting a vertex
b) A disconnected graph by removing an edge
c) A disconnected graph by removing one edge and a vertex
d) A simple graph which does not contain a cycle

Answer: a
Clarification: By deletion of a vertex the graph is disconnected and the graph is called separable graph and the vertex is called cut vertex.

6. How many edges are there in a complete graph of order 9?
a) 35
b) 36
c) 45
d) 19

Answer: b
Clarification: In a complete graph of order n, there are n*(n-1) number of edges and degree of each vertex is (n-1). Hence, for a graph of order 9 there should be 36 edges in total.

7. How many cycles are there in a wheel graph of order 5?
a) 6
b) 10
c) 25
d) 7

Answer: d
Clarification: In a cycle of a graph G if we join all the vertices to the centre point, then that graph is called a wheel graph. There is always a Hamiltonian cycle in a wheel graph and there are n²-3n+3 cycles. So, for order 5 the answer should be 7.

8. The time complexity to find a Eulerian path in a graph of vertex V and edge E is _____________
a) O(V²)
b) O(V+E-1)
c) O(V+E)
d) O(E+1)

Answer: c
Clarification: An undirected graph has Eulerian Path if the following two conditions are true: -a) All vertices with a non-zero degree are connected. A graph of vertices with zero degrees don’t belong to Eulerian Cycle or Path, b) If two vertices have odd degree and all other vertices have even degree. Thus, the time to find whether a graph has a Eulerian path or not is O(V+E) with V vertices and E edges.

9. The time complexity to find shortest distances by using Dijkstra’s algorithm is __________
a) O(E²)
b) O(V+1-E)
c) O(V+E)
d) O(E+VlogV)

Answer: d
Clarification: Time complexity of finding shortest distance can be O(E + VLogV) using Fibonacci Heap. The reason is that Fibonacci Heap takes O(1) time for decrease-key operation while Binary Heap takes O(logn) time.

10. Topological sorting of a graph represents _______ of a graph.
a) linear probing
b) linear ordering
c) quadrilateral ordering
d) insertion sorting

Answer: b
Clarification: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. If the graph is not a DAG, topological sorting for a graph is not possible.