This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Counting – Pigeonhole Principle”.
1. A drawer contains 12 red and 12 blue socks, all unmatched. A person takes socks out at random in the dark. How many socks must he take out to be sure that he has at least two blue socks?
a) 18
b) 35
c) 28
d) 14
View Answer
Explanation: Given 12 red and 12 blue socks so, in order to take out at least 2 blue socks, first we need to take out 12 shocks (which might end up red in worst case) and then take out 2 socks (which would be definitely blue). Thus we need to take out total 14 socks.
2. The least number of computers required to connect 10 computers to 5 routers to guarantee 5 computers can directly access 5 routers is ______
a) 74
b) 104
c) 30
d) 67
View Answer
Explanation: Since each 5 computer need directly connected with each router. So 25 connections + now remaining 5 computer, each connected to 5 different routers, so 5 connections = 30 connections. Hence,
c1->r1, r2, r3, r4, r5 c2->r1, r2, r3, r4, r5 c3->r1, r2, r3, r4, r5 c4->r1, r2, r3, r4, r5 c5->r1, r2, r3, r4, r5 c6->r1 c7->r2 c8->r3 c9->r4 c10->r5
Now, any pick of 5 computers will have a direct connection to all the 5 routers.
3. In a group of 267 people how many friends are there who have an identical number of friends in that group?
a) 266
b) 2
c) 138
d) 202
View Answer
Explanation: Suppose each of the 267 members of the group has at least 1 friend. In this case, each of the 267 members of the group will have 1 to 267-1=266 friends. Now, consider the numbers from 1 to n-1 as holes and the n members as pigeons. Since there is n-1 holes and n pigeons there must exist a hole which must contain more than one pigeon. That means there must exist a number from 1 to n-1 which would contain more than 1 member. So, in a group of n members there must exist at least two persons having equal number of friends. A similar case occurs when there exist a person having no friends.
4. When four coins are tossed simultaneously, in _______ number of the outcomes at most two of the coins will turn up as heads.
a) 17
b) 28
c) 11
d) 43
View Answer
Explanation: The question requires you to find number of the outcomes in which at most 2 coins turn up as heads i.e., 0 coins turn heads or 1 coin turns head or 2 coins turn heads. The number of outcomes in which 0 coins turn heads is 4C0 = 1 outcome. The number of outcomes in which 1 coin turns head is 4C1 = 6 outcomes. The number of outcomes in which 2 coins turn heads is,
4C2 = 15 outcomes. Therefore, total number of outcomes = 1 + 4 + 6 = 11 outcomes.
5. How many numbers must be selected from the set {1, 2, 3, 4} to guarantee that at least one pair of these numbers add up to 7?
a) 14
b) 5
c) 9
d) 24
View Answer
Explanation: With 2 elements pairs which give sum as 7 = {(1,6), (2,5), (3,4), (4,3)}. So choosing 1 element from each group = 4 elements (in worst case 4 elements will be either {1,2,3,4} or {6,5,4,3}). Now using pigeonhole principle = we need to choose 1 more element so that sum will definitely be 7. So Number of elements must be 4 + 1 = 5.
6. During a month with 30 days, a cricket team plays at least one game a day, but no more than 45 games. There must be a period of some number of consecutive days during which the team must play exactly ______ number of games.
a) 17
b) 46
c) 124
d) 24
View Answer
Explanation: Let a1 be the number of games played until day 1, and so on, ai be the no games played until i. Consider a sequence like a1,a2,…a30 where 1≤ai≤45, ∀ai. Add 14 to each element of the sequence we get a new sequence a1+14, a2+14, … a30+14 where, 15 ≤ ai+14 ≤ 59, ∀ai. Now we have two sequences 1. a1, a2, …, a30 and 2. a1+14, a2+14, …, a30+14. having 60 elements in total with each elements taking a value ≤ 59. So according to pigeon hole principle, there must be at least two elements taking the same value ≤59 i.e., ai = aj + 14 for some i and j. Therefore, there exists at least a period such as aj to ai, in which 14 matches are played.
7. In how many ways can 8 different dolls be packed in 5 identical gift boxes such that no box is empty if any of the boxes hold all of the toys?
a) 2351
b) 365
c) 2740
d) 1260
View Answer
Explanation: Dolls are different but the boxes are identical. If none of the boxes is to remain empty, then we can pack the dolls in one of the following ways:
Case i. 2, 2, 2, 1, 1
Case ii. 3, 3, 1, 1
Case i: Number of ways of achieving the first option 2, 2, 2, 1, 1. Two dolls out of the 8 can be selected in 8C2 ways, another 2 out of the remaining 6 can be selected in 6C2 ways, another 2 out of the remaining 4 can be selected in 4C2 ways and the last two dolls can be selected in 1C1 ways each. However, as the boxes are identical, the two different ways of selecting which box holds the first two dolls and which one holds the second set of two dolls will look the same. Hence, we need to divide the result by 2. Therefore, total number of ways of achieving the 2, 2, 2, 1, 1 is = (8C2 * 6C2 * 4C2 * 1C1 * 1C1) / 2 = 1260.
8. A group of 20 girls plucked a total of 200 oranges. How many oranges can be plucked one of them?
a) 24
b) 10
c) 32
d) 7
View Answer
Explanation: Suppose all of them plucked the different number of oranges. A girl can pluck at least 0 oranges and the number of oranges plucks by each student is distinct. So, total number of plucked oranges should be less than 100. But 0+1+2…..+19+20 = 210>200 a contradiction.
Thus there exist two girls who plucked the same number of oranges. If thus there exist two girls who plucked the same number of oranges. It means each girl of remaining 18 students plucked different number of oranges. Number of oranges Plucked by 18 students = 0+1+2+3…+17 = 153 oranges. Number of oranges plucked by remaining 2 student = 200 – 153 = 47. Both students plucked same number of oranges. So, Number of oranges plucked by one of them = 47/2=24.
9. In a get-together party, every person present shakes the hand of every other person. If there were 90 handshakes in all, how many persons were present at the party?
a) 15
b) 14
c) 16
d) 17
View Answer
Explanation: Let the total number of persons present at the party be m, Then, [{x *(x−1)}/2] = 90.
x = 14.
10. A bag contains 25 balls such as 10 balls are red, 7 are white and 8 are blue. What is the minimum number of balls that must be picked up from the bag blindfolded (without replacing any of it) to be assured of picking at least one ball of each colour?
a) 10
b) 18
c) 63
d) 35
View Answer
Explanation: Consider three buckets red, white and blue and we want the total number of balls such that each bucket contain at least one ball. Now consider the state of picking up a ball without replacement : (normally you consider the worst case scenario in these cases) Starting 10 balls all are red and thus goes to bucket name Red. Now again picking up the ball gives 7 balls which are of same colour and put all of them in a bucket named White. The next pick will definitely be of different colour thus: we picked 10 + 7 + 1 = 18.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check BCA Books
- Practice Computer Science MCQs
- Practice BCA MCQs
- Apply for Computer Science Internship
- Check Discrete Mathematics Books
