Test: Pigeon Hole Principle - Computer Science Engineering (CSE) MCQ

Concept:
The pigeonhole principle states that if items are put into containers, then at least one container must contain more than one item.

Pigeonhole Principle:
If n pigeonholes are occupied by n+1 or more pigeons, then at least one pigeonhole is occupied by greater than one pigeon. Generalized pigeonhole principle is: - If n pigeonholes are occupied by kn+1 or more pigeons, where k is a positive integer, then at least one pigeonhole is occupied by k+1 or more pigeons.
The given data,
A professor gives five grades {A, B, C, D, F} n = 5
Get the same grade k+1 =4
k = 3
The minimum number of students = ?
The minimum number of students = Kn+1
The minimum number of students = 3 x 5+1
The minimum number of students = 16
Hence the correct answer is 16.

• Suppose we have fixed that 4 students got the same grade which is A then for B there are two options whether professor will give to someone or not similarly for C there are two options whether professor will give C to someone or not.
• One grade is fixed for 4 students hence for remaining we have two option whether to include or not.
• Minimum number of students so that four of them are guaranteed to get the same grade = 2 × 2 × 2 × 2 = 16, option 3 is the correct answer.

73/12 ≈ 6.08 [6.08] = 7

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.

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.

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.

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 ⁸C₂ ways, another 2 out of the remaining 6 can be selected in ⁶C₂ ways, another 2 out of the remaining 4 can be selected in ⁴C₂ ways and the last two dolls can be selected in ¹C₁ 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 = (⁸C₂ * ⁶C₂ * ⁴C₂ * ¹C₁ * ¹C₁) / 2 = 1260.

Let the total number of persons present at the party be m, Then, [{x *(x−1)}/2] = 90.
x = 14.

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 ⁴C₀ = 1 outcome. The number of outcomes in which 1 coin turns head is ⁴C₁ = 6 outcomes. The number of outcomes in which 2 coins turn heads is,
⁴C₂ = 15 outcomes. Therefore, total number of outcomes = 1 + 4 + 6 = 11 outcomes.

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.