Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Set Operations”.

1. The union of the sets {1, 2, 5} and {1, 2, 6} is the set _______________
a) {1, 2, 6, 1}
b) {1, 2, 5, 6}
c) {1, 2, 1, 2}
d) {1, 5, 6, 3}

Answer: b
Clarification: The union of the sets A and B, is the set that contains those elements that are either in A or in B.

2. The intersection of the sets {1, 2, 5} and {1, 2, 6} is the set _____________
a) {1, 2}
b) {5, 6}
c) {2, 5}
d) {1, 6}

Answer: a
Clarification: The intersection of the sets A and B, is the set containing those elements that are in both A and B.

3. Two sets are called disjoint if there _____________ is the empty set.
a) Union
b) Difference
c) Intersection
d) Complement

Answer: c
Clarification: By the definition of the disjoint set.

4. Which of the following two sets are disjoint?
a) {1, 3, 5} and {1, 3, 6}
b) {1, 2, 3} and {1, 2, 3}
c) {1, 3, 5} and {2, 3, 4}
d) {1, 3, 5} and {2, 4, 6}

Answer: d
Clarification: Two sets are disjoint if the intersection of two sets is the empty set.

5. The difference of {1, 2, 3} and {1, 2, 5} is the set ____________
a) {1}
b) {5}
c) {3}
d) {2}

Answer: c
Clarification: The difference of the sets A and B denoted by A-B, is the set containing those elements that are in A not in B.

6. The complement of the set A is _____________
a) A – B
b) U – A
c) A – U
d) B – A

Answer: b
Clarification: The complement of the set A is the complement of A with respect to U.

7. The bit string for the set {2, 4, 6, 8, 10} (with universal set of natural numbers less than or equal to 10) is ____________________
a) 0101010101
b) 1010101010
c) 1010010101
d) 0010010101

Answer: a
Clarification: The bit string for the set has a one bit in second, fourth, sixth, eighth, tenth positions, and a zero elsewhere.

8. Let Ai = {i, i+1, i+2, …..}. Then set {n, n+1, n+2, n+3, …..} is the _________ of the set Ai.
a) Union
b) Intersection
c) Set Difference
d) Disjoint

Answer: b
Clarification: By the definition of the generalized intersection of the set.

9. The bit strings for the sets are 1111100000 and 1010101010. The union of these sets is ___________
a) 1010100000
b) 1010101101
c) 1111111100
d) 1111101010

Answer: d
Clarification: The bit string for the union is the bitwise OR of the bit strings.

10. The set difference of the set A with null set is __________
a) A
b) null
c) U
d) B

Answer: a
Clarification: The set difference of the set A by the null set denoted by A – {null} is A.

Discrete Mathematics Questions and Answers for Aptitude test on “Cardinality of Sets”.

1. The cardinality of the set A = {1, 2, 3, 4, 6} is?
a) 5
b) 6
c) Integer
d) None of the mentioned

Answer: a
Clarification: 5, it is a number of elements in the sets.

2. For two equal sets there ___________
a) Cardinality is same
b) Cardinality is different
c) May be same or different
d) None of the mentioned

Answer: a
Clarification: Two equal sets should have the same number of elements.

3. If A is a subset of B then _______
a) The cardinality of A is greater than B
b) The cardinality of B is greater than A
c) Can’t say
d) None of the mentioned

Answer: b
Clarification: B contains all the elements of A, as well as other elements.

4. If there is a bijection between two sets A and B then _______
a) Cardinality of A is greater than B
b) Cardinality of B is greater than A
c) Cardinality of B is equal to A
d) None of the mentioned

Answer: c
Clarification: If there is bijection then two sets A and B will be equinumerous and thus will have same cardinality.

5. Let a set E ={0,2,4,6,8….} of non-negative even numbers and O = {1, 3, 5, 7, 9,…..} of non-negative odd numbers then?
a) Cardinality of set E is greater than that of O
b) Cardinality of set O is greater than that of E
c) Cardinality of set E is equal to that of O
d) None of the mentioned

Answer: c
Clarification: There is bijection then two sets E and O and they will be equinumerous and thus will have same cardinality.

6. Cardinality of the set of lower letter english alphabets is 26.
a) True
b) False

Answer: a
Clarification: From a, b, c…z there will be 26 elements.

7. Cardinality of the set of even prime number under 10 is 4.
a) True
b) False

Answer: b
Clarification: Since 2 is only even prime thus cardinality should be 1.

8. If for sets A and B there exists an injective function but not bijective function from A to B then?
a) Cardinality of A is strictly greater than B
b) Cardinality of B is strictly greater than A
c) Cardinality of B is equal to A
d) None of the mentioned

Answer: b
Clarification: If there doesnot exist a bijective function from A to B that means there are some elements in B whose preimage is not in A, thus cardinality of B is strictly greater than A.

9. If cardinality of (A U B) = cardinality of A+ cardinality of B. This means ____________
a) A is a subset of B
b) B is a subset of A
c) A and B are disjoint
d) None of the mentioned

Answer: c
Clarification: Thus if the cardinality of (A U B) = cardinality of A+ cardinality of B, it means they don’t have any element in common, n(A∩B) = 0.

10. If A is a subset of B and B is a subset of C, then cardinality of A U B U C is equal to ____________
a) Cardinality of C
b) Cardinality of B
c) Cardinality of A
d) None of the mentioned

Answer: a
Clarification: A U B U C = C, since a, b are subsets to C.

Discrete Mathematics Questions and Answers for Campus interviews on “Number Theory – Highest Common Factors”.

1. A Highest Common Factor of a, b is defined as ___________
a) It is the smallest integer divisible by both a and b
b) It is the greatest integer divisor of both a and b
c) It is the sum of the number a and b
d) None of the mentioned

Answer: b
Clarification: Defination of HCF(a, b)-greatest integer divisor of both a and b.

2. The HCF of two number 1, b(integer) are _________
a) b + 2
b) 1
c) b
d) None of the mentioned

Answer: b
Clarification: Since 1 is the greatest integer divisor of both 1 and b.

3. If a,b are integers such that a > b then hcf(a, b) lies in _________
a) a> hcf(a, b)>b
b) a>b> = hcf(a, b)
c) hcf(a, b)> = a>b
d) None of the mentioned

Answer: b
Clarification: Hcf of number is either equal to smallest number or is least among all.

4. HCF of 6, 10 is?
a) 60
b) 30
c) 10
d) 2

Answer: d
Clarification: Since 2 is the greatest integer divisor of both 6 and 10.

5. The product of two numbers are 12 and there LCM is 6 then HCF is?
a) 12
b) 2
c) 6
d) None of the mentioned

Answer: b
Clarification: The hcf of two number a and b is given by
(hcf(a, b)) = ab/ lcm(a, b).

6. If LCM of two number is 10 and GCD is 5 then the product of two numbers is?
a) 45
b) 50
c) 7
d) 49

Answer: b
Clarification: The lcm of two number a and b is given by
lcm(a,b) = ab/(GCD(a, b)), this implies ab = lcm(a, b) * gcd(a, b).

7. If a number is 2² x 3¹ x 5⁰ and b is 2² x 3¹ x 5¹ then hcf of a, b is?
a) 2² x 3¹ x 5¹
b) 2² x 3² x 5²
c) 2¹ x 3¹ x 5⁰
d) 2² x 3² x 5⁰

Answer: c
Clarification: Hcf is the product of sets having least exponent value among a and b.

8. State whether the given statement is True or False.

HCF (a, b, c, d) = HCF(a,(HCF(b,(HCF(c, d)))).

a) True
b) False

Answer: a
Clarification: HCF function can be reursively defined.

9. HCF(a, b) is equals to _________
a) ab/(LCM(a, b))
b) (a + b)/(LCM(a, b))
c) (LCM(a, b))/ab
d) None of the mentioned

Answer: a
Clarification: ab = lcm(a, b)*hcf(a, b), which implies
HCF(a,b) = ab/(LCM(a, b)).

10. The HCF of two prime numbers a and b is _________
a) ^a⁄_b
b) ab
c) a + b
d) 1

Answer: d
Clarification: Since they doesnot have any factor in common other than 1.

Discrete Mathematics Multiple Choice Questions on “Counting – Circular Permutations”.

1. In a playground, 3 sisters and 8 other girls are playing together. In a particular game, how many ways can all the girls be seated in a circular order so that the three sisters are not seated together?
a) 457993
b) 3386880
c) 6544873
d) 56549

Answer: b
Clarification: There are 3 sisters and 8 other girls in total of 11 girls. The number of ways to arrange these 11 girls in a circular manner = (11– 1)! = 10!. These three sisters can now rearrange themselves in 3! ways. By the multiplication theorem, the number of ways so that 3 sisters always come together in the arrangement = 8! × 3!. Hence, the required number of ways in which the arrangement can take place if none of the 3 sisters is seated together: 10! – (8! × 3!) = 3628800 – (40320 * 6) = 3628800 – 241920 = 3386880.

2. How many numbers of three digits can be formed with digits 1, 3, 5, 7 and 9?
a) 983
b) 120
c) 345
d) 5430

Answer: b
Clarification: Here number of digits, n = 5 and number of places to be filled-up r = 3. Hence, the required number is ⁵P₃ = 5!/2!*3! = 120.

3. The size of a multiset is 6 which is equal to the number of elements in it with counting repetitions (a multiset is an unordered collection of elements where the elements may repeat any number of times). Determine the number of multisets can be grouped from n distinct elements so that at least one element occurs exactly twice?
a) 326
b) 28
c) 45
d) 62

Answer: c
Clarification: There are six places to be filled in the multiset using the n distinct elements. At least one element has to occur exactly twice and that would leave 4 more places in the multiset means that at most four elements can occur exactly once. Thus there are two mutually exclusive cases as follows: 1) Exactly one element occurs exactly twice and select this element in n ways. Fill up the remaining four spots using 5 distinct elements from the remaining n−1 elements in ^n-1C₄ ways. 2) Exactly four elements that occur at least once each. Hence, the total number of ways to form the multiset is
ⁿC₂ + n * ^n-1C₄ = ⁶C₂ + 6 * ^6-1C₄ = 45.

4. How many words can be formed with the letters of the word ‘CASTLE’ when ‘O’ and ‘A’ occupying end places.
a) 217
b) 48
c) 75
d) 186

Answer: b
Clarification: When ‘O’ and ‘A’ are occupying end-places => A.S.T.L. (CE). We can see that (CE) are fixed, hence A, S, T, L can be arranged in 4! Ways and (C, E) can be arranged themselves is 2! ways. So, the number of words formed = 4! x 2! = 48 ways.

5. Determine the number of ways of choosing a cricket team (consists of 11 players) out of 18 players if a particular player is never chosen.
a) 12798
b) 22800
c) 31824
d) 43290

Answer: c
Clarification: If a particular player is never chosen that would mean 11 players are selected out of 18 players. Hence, required number of ways = ¹⁸C₁₁ = 31824.

6. How many different choices can be made from 5 roses, 4 marigold and 8 sunflowers if at least one flower is to be chosen for making of garland?
a) 269
b) 270
c) 281
d) 320

Answer: a
Clarification: Number of ways of selecting roses = (5+1) = 6 ways, number of ways of selecting marigold = (4+1) = 5 ways, and the number of ways of selecting sunflowers = (8+1) = 9 ways. Total number of ways of selecting flowers= 6 * 5 * 9 = 270. But this includes when no flowers or zero flowers is selected (There is no flowers of a different type, hence n=0 => 2ⁿ = 2⁰ = 1). Hence, the number of ways of selecting at least one fruit = 270 – 1 = 269.

7. In how many ways 6 pens can be selected from 15 identical black pens?
a) 9*3!
b) 21
c) 14!
d) 1

Answer: d
Clarification: Here the pens are identical, the total number of ways of selecting 6 pens is 1.

8. Determine the number of ways of selecting one or more letters from the letters BBBBBB?
a) 6
b) 73
c) 23
d) 56

Answer: a
Clarification: The number of ways of selecting one ‘B’s = 1, selecting two ‘B’s = 1, selecting three ‘B’s = 1, selecting four ‘B’s = 1, selecting five ‘B’s = 1 and selecting six ‘B’s = 1. Hence, the required number of ways = 6.

9. Determine the number of ways such that 5 men and 5 women be seated at a round table if no two women are seated together.
a) 654870
b) 144521
c) 362160
d) 5634

Answer: c
Clarification: The men and women can be seated alternately so that no two women will sit together. Hence, 4 women can be seated on alternate seats at a round table in (4 – 1)! or 6
ways. Now, the 5 men can be seated in the remaining seats in 5! or 120 ways. Therefore the total number of ways in this case will be (10-1)! – (120 * 6) = 362160.

10. Find the number of ways in which 4 people E, F, G, H, A, C can be seated at a round table, such that E and F must always sit together.
a) 32
b) 290
c) 124
d) 48

Answer: d
Clarification: E and F can sit together in all arrangements in 2! Ways. Now, the arrangement of the 5 people in a circle can be done in (5 – 1)! or 24 ways. Therefore, the total number of ways will be 24 x 2 = 48.

Discrete Mathematics Multiple Choice Questions on “Discrete Probability – Principle of Inclusion Exclusion”.

1. There are 70 patients admitted in a hospital in which 29 are diagnosed with typhoid, 32 with malaria, and 14 with both typhoid and malaria. Find the number of patients diagnosed with typhoid or malaria or both.
a) 39
b) 17
c) 47
d) 53

Answer: c
Clarification: By using the inclusion-exclusion principle: |T ∪ M| = |T| + |M| – |T ∩ M| = (29 + 32) – (14) = 47. Thus 47 patients are diagnosed with either typhoid or malaria.

2. At a software company, skilled workers have been hired for a project. Out of 75 candidates, 48 of them were software engineer; 35 of them were hardware engineer; 42 of them were network engineer; 18 of them had skills in all three jobs and all of them had skills in at least one of these jobs. How many candidates were hired who were skilled in exactly 2 jobs?
a) 69
b) 14
c) 32
d) 8

Answer: b
Clarification: Since 18 are skilled in all 3. Subtract 18 from all three to get a total with single skilled and double skilled workers including the duplicates. Software engineers = 48 – 18 = 30, Hardware engineers = 35 – 18 = 17, Network engineers = 42 – 18 = 24 making a total of 71 and this is a total set of single and double skilled workers including duplicates. Out of 75 candidates, 18 were skilled in three areas. So, 75 – 18 = 57 (actual no of workers skilled with single and both skills) Now the difference between the number without duplicates (57) and with duplicates (71), 71 – 57 = 14. So, 14 are skilled in exactly two jobs.

3. The numbers between 1 and 520, including both, are divisible by 2 or 6 is _______
a) 349
b) 54
c) 213
d) 303

Answer: d
Clarification: We add the number of numbers that are divisible by 2 and 6 and subtract the numbers which are divisible by 12. Hence, the required probability is
(frac{520}{2} + frac{520}{6} – frac{520}{12}) = 303.3 = 303(Approximately).

4. In a renowned software development company of 240 computer programmers 102 employees are proficient in Java, 86 in C#, 126 in Python, 41 in C# and Java, 37 in Java and Python, 23 in C# and Python, and just 10 programmers are proficient in all three languages. How many computer programmers are there those are not proficient in any of these three languages?
a) 138
b) 17
c) 65
d) 49

Answer: b
Clarification: Let U denote the set of all employed computer programmers and let J, C and P denote the set of programmers proficient in Java, C# and Python, respectively. So, |U| = 240, |J| = 102, |C| = 86, |P| = 126, |J ∩ C| = 41, |J ∩ P| = 37, |C ∩ P| = 23 and |J ∩ C ∩ P| = 10. The number of computer programmers that are not proficient in any of these three languages is said to be same as the cardinality of the complement of the set J ∪ C ∪ P. First, we have to calculate |J ∪ C ∪ P| = 102 + 86 + 126 – 41 – 37 – 23 + 10 = 223. Now calculate |(J ∪ C ∪ P)’ | = |U| – |J ∪ C ∪ P| = 240 – 223 = 17. 17 programmers are not proficient in any of the three languages.

5. In class, students want to join sports. 15 people will join football, 24 people will join basketball, and 7 people will join both. How many people are there in the class?
a) 19
b) 82
c) 64
d) 30

Answer: d
Clarification: There are 15 people who wish to join football, but 9 of those people also join basketball. By using the principle of inclusion and exclusion, we have: 15 people joining football + 24 people joining basketball – 9 people who will join both = 30 people total.

6. The sum of all integers from 1 to 520 that are multiples of 4 or 5?
a) 187
b) 208
c) 421
d) 52

Answer: b
Clarification: PIE is used to count the elements of a set and stated as the sum of elements in A or B is equal to the sum of elements in A plus the sum of elements in B minus the sum of elements in A and B. Let A be the set of multiples of 4 and B be the set of multiples of 5, then A ⋂ B is the set of multiples of 20, and hence
(frac{520}{4} + frac{520}{5} – frac{520}{20}) = 208.

7. There are 9 letters having different colors (red, orange, yellow, green, blue, indigo, violet) and 4 boxes each of different shapes (tetrahedron, cube, polyhedron, dodecahedron). How many ways are there to place these 9 letters into the 4 boxes such that each box contains at least 1 letter?
a) 260100
b) 878760
c) 437102
d) 256850

Answer: a
Clarification: Let N be the total number of ways we can distribute the letters. Each letter can be placed into any one of the 4 boxes, so |N| = 4⁹. Let T be the set of ways such that the tetrahedron box has no letters, C be the set of ways such that the cube box has no letters, P be the set of ways such that the cube box has no letters, and D be the set of ways such that the dodecahedron box has no letters. Now, to find |N| – |T U C U P U D|. We have |T|=|C|=|P|=|D|=2⁷ and since the letters can be placed into one of the two other boxes, and |TUC| = |C U P| = |P U D| = |D U T| = 1⁷, since all the letters must be placed in the remaining box, and T ⋂ C ⋂ P ⋂ D| = 0. Hence, PIE implies |N| – |T U C U P U D| = 4⁹ – 4 x 2⁹ + 4 x 1⁹ – 0 = 260100.

8. A card is drawn randomly from a standard deck of cards. Determine the probability that the card drawn is a queen or a heart.
a) (frac{1}{4})
b) (frac{13}{56})
c) (frac{4}{13})
d) (frac{5}{52})

Answer: c
Clarification: Let M be the event that the card is a queen, and let N be the event that the card is a heart. Then Since there are 13 different ranks of cards in the deck, P(M) = (frac{1}{13}) and since there are 4 suits in the deck, P(N) = (frac{1}{4}). There is only one card that is both a queen and a heart, so P(M ⋂ N) = (frac{1}{52}). Therefore, P(M U N) = (frac{1}{4} + frac{1}{13} – frac{1}{52} = frac{16}{52} = frac{4}{13}).

9. An integer from 300 through 780, inclusive is to be chosen at random. Find the probability that the number is chosen will have 1 as at least one digit.
a) (frac{171}{900})
b) (frac{43}{860})
c) (frac{231}{546})
d) (frac{31}{701})

Answer: a
Clarification: The number of numbers that don’t have one anywhere 9³ = 729 is (9 possibilities for each individual digit), and there are 9*10² = 900 numbers overall (9 possibilities for hundreds, 10 for the tens and units), so there are 900 – 729 = 171 numbers with at least a one and thus (frac{171}{900}) probability.

10. From 1, 2, 3, …, 320 one number is selected at random. Find the probability that it is either a multiple of 7 or a multiple of 3.
a) 72%
b) 42.5%
c) 12.8%
d) 63.8%

Answer: b
Clarification: Number of multiples of 7=45 and number of multiples of 3=10⁶ and number of numbers which are multiples of both 7 and 3 = 15 Thus, P (selecting either a multiple of 7 or a multiple of 3) = (frac{45}{320} + frac{106}{320} – frac{15}{320} = frac{136}{320} = frac{2}{5}) = 0.425 or 42.5%.

Discrete Mathematics Multiple Choice Questions on “Planarity, Degree and Coloring of Graph”.

1. The chromatic number of a graph is the property of ____________
a) graph coloring
b) graph ordering
c) group ordering
d) group coloring

Answer: b
Clarification: A graph coloring is an assignment of labels to the vertices of a graph such that no two adjacent vertices share the same labels is called the colors of the graph. Now, the chromatic number of any graph is the minimal number of colors for which such an assignment is possible.

2. If a graph G is k-colorable and k<n, for any integer n then it is ___________
a) n-colorable
b) n² nodes
c) (k+n)-colorable
d) (k³+n³+1) nodes

Answer: a
Clarification: The chromatic number of a graph is the minimal number of colors for which a graph coloring is possible. A graph G is termed as k-colorable if there exists a graph coloring on G with k colors. If a graph is k-colorable, then it is n-colorable for any n>k.

3. If Cn is the nth cyclic graph, where n>3 and n is odd. Determine the value of X(C_n).
a) 32572
b) 16631
c) 3
d) 310

Answer: c
Clarification: Here n is odd and X(C_n)! = 2. Since there are two adjacent edges in C_n. Now, a graph coloring for Cn exists where vertices are colored red and blue alternatively and another edge is with a different colour say orange, then the value of X(C_n) becomes 3.

4. Determine the density of a planar graph with 34 edges and 13 nodes.
a) 22/21
b) 12/23
c) 328
d) 576

Answer: a
Clarification: The density of a planar graph or network is described as the ratio of the number of edges(E) to the number of possible edges in a network with(N) nodes. So, D = E − N + 1/ 2 N − 5. Hence, the required answer is: D=(34-13+1)/(2*13-5) = 22/21. A completely sparse planar graph has density 0 and a completely dense planar graph has degree 1.

5. If the number of vertices of a chromatic polynomial P_G is 56, what is the degree of P_G?
a) 344
b) 73
c) 265
d) 56

Answer: d
Clarification: The chromatic polynomial PG of a graph G is a polynomial in which every natural number k returns the number P_G(k) of k-colorings of G. Since, the degree of P_G is equal to the number of vertices of G, the required answer is 56.

6. For a connected planar simple graph G=(V, E) with e=|E|=16 and v=|V|=9, then find the number of regions that are created when drawing a planar representation of the graph?
a) 321
b) 9
c) 1024
d) 596

Answer: b
Clarification: We know that the number of regions in a planar representation of the graph is r=e-v+2, then the required answer is r=16-9+2=9.

7. For a connected planar simple graph G=(V, E) with e=|E|=16 and v=|V|=9, then find the number of regions that are created when drawing a planar representation of the graph?
a) 321
b) 9
c) 1024
d) 596

Answer: b
Clarification: Note that K_3,3 and K₅ are the “smallest” non-planar graphs because in that every non-planar graph contains them. According to Kuratowski’s theorem, a graph is defined as non-planar if and only if it contains a subgraph homomorphic to K_3,3 or K₅.

8. Suppose G be a connected planar graph of order n≥5 and size m. If the length of the smallest cycle in G is 5, then which of the following is true?
a) (m+n)⁴>=mn
b) m≤5/3(n−2)
c) (m²+n)/3
d) n>=(6/5)(n+1)

Answer: b
Clarification: Because G is connected and planar, Euler’s theorem is bound to be involved. Let f denote the number of faces so that n−m+f=2. Because the length of the smallest cycle in G is 5, every face has at least 5 edges adjacent to it. This means 2m≥5f because every edge is adjacent to two faces. Plugging this in yields 2=n−m+f≤n−m+2/5m=n−3/5m, and hence m≤5/3(n−2).

9. What is the number of edges of the greatest planar subgraph of K_3,2 where m,n≤3?
a) 18
b) 6
c) 128
d) 702

Answer: b
Clarification: The plane graph with an edge at most 6+2(m−3) is the greatest planar graph. So, in this case the number of edges is 6.

10. A non-planar graph can have ____________
a) complete graph
b) subgraph
c) line graph
d) bar graph

Answer: b
Clarification: A non-planar graph can have removed edges and vertices so that it contains subgraphs. However, non-planar graphs cannot be drawn in a plane and so no edge of the graph can cross it.