Discrete Math Quiz: Pigeonhole Principle
7 questions · exam conditions
0:00
Pigeonhole PrincipleQuestion 1 of 7

A university dining hall serves lunch to 1000 students daily. Each student chooses exactly 3 items from a menu of 15 available items. If the dining hall wants to guarantee that some combination of 3 items is chosen by multiple students, what is the minimum number of students needed?

At least 456 students are needed to guarantee duplicate combinations
At least 457 students are needed to guarantee duplicate combinations
At least 466 students are needed to guarantee duplicate combinations
All 1000 students could potentially choose different combinations
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Pigeonhole Principle

Practice Pigeonhole Principle in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Pigeonhole Principle, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

A university dining hall serves lunch to 1000 students daily. Each student chooses exactly 3 items from a menu of 15 available items. If the dining hall wants to guarantee that some combination of 3 items is chosen by multiple students, what is the minimum number of students needed?

  1. At least 456 students are needed to guarantee duplicate combinations
  2. At least 457 students are needed to guarantee duplicate combinations (correct answer)
  3. At least 466 students are needed to guarantee duplicate combinations
  4. All 1000 students could potentially choose different combinations
Explanation: The number of ways to choose 3 items from 15 available items is C(15,3) = 15!/(3!×12!) = (15×14×13)/(3×2×1) = 455. By the pigeonhole principle, if 456 students each choose 3 items, it's possible (though unlikely) that all choose different combinations. However, with 457 students, at least two must choose the same combination since 457 > 455. Choice A is wrong because 456 = 455 + 1 but we need strict inequality. Choice C overestimates. Choice D is impossible since 1000 >> 455.

Question 2

A mathematics conference has 200 attendees, each of whom speaks at least 2 and at most 5 of the following languages: English, French, German, Spanish, Italian, Russian. Each attendee's language combination must include English. What is the minimum number of attendees who must share the exact same set of languages?

  1. At least 8 attendees must share the same language combination
  2. At least 7 attendees must share the same language combination (correct answer)
  3. At least 6 attendees must share the same language combination
  4. At least 9 attendees must share the same language combination
Explanation: Since English is required, we choose additional languages from {French, German, Spanish, Italian, Russian} (5 options). For k total languages: C(5,k-1) combinations. For 2 languages: C(5,1)=5. For 3: C(5,2)=10. For 4: C(5,3)=10. For 5: C(5,4)=5. For 6: C(5,5)=1. Total combinations = 5+10+10+5+1 = 31. With 200 attendees and 31 possible combinations, by pigeonhole principle, at least ⌈200/31⌉ = ⌈6.45⌉ = 7 attendees must share the same combination. The other choices are either too high or too low.

Question 3

A game show has 30 contestants, each of whom selects a subset of exactly 4 prizes from a collection of 10 available prizes. The show's rules state that if any two contestants select the exact same subset of prizes, both are eliminated. What is the maximum number of contestants who can remain in the game?

  1. At most 20 contestants can remain due to elimination rules
  2. At most 25 contestants can remain due to subset limitations
  3. All 30 contestants can remain since there are enough distinct subsets (correct answer)
  4. All 30 contestants can remain, but only if they coordinate perfectly
Explanation: When you encounter problems about selecting distinct subsets, you need to determine how many different ways items can be chosen and compare that to the number of people making selections. This is a combinations problem. Each contestant selects exactly 4 prizes from 10 available prizes, and we need all selections to be unique to avoid elimination. The key question is: are there enough distinct 4-prize subsets to accommodate all 30 contestants? The number of ways to choose 4 prizes from 10 is (104)=10!4!(10−4)!=10×9×8×74×3×2×1=504024=210\binom{10}{4} = \frac{10!}{4!(10-4)!} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = \frac{5040}{24} = 210 Since there are 210 possible distinct subsets and only 30 contestants, there are more than enough unique combinations available. All 30 contestants can theoretically remain without any eliminations. Answer A incorrectly assumes eliminations are inevitable, missing that sufficient distinct subsets exist. Answer B arbitrarily limits contestants to 25 without mathematical justification - there's no subset limitation that would create this specific number. Answer D suggests coordination is required, but coordination isn't necessary for the mathematical possibility to exist; the abundance of available subsets (210 vs 30 needed) makes overlap avoidable even with random selection. Study tip: In combinatorics problems involving uniqueness constraints, always calculate the total number of possible combinations first. If this number exceeds the number of participants, then theoretically everyone can have a unique selection. Remember that (nr)\binom{n}{r} often yields surprisingly large numbers even for modest values.

Question 4

A library organizes books using a classification system where each book gets a code consisting of 2 letters followed by 3 digits, but codes cannot contain the letter combinations 'XX', 'YY', or 'ZZ' as the two-letter prefix. If the library has 15,000 books to classify, what can be concluded about the classification codes?

  1. All 15,000 books can receive distinct classification codes under this system (correct answer)
  2. At least two books must share the same classification code
  3. The system needs modification to accommodate all books uniquely
  4. Exactly 15,000 valid codes exist under the given constraints
Explanation: Valid codes have form [LL][DDD] where LL ≠ XX, YY, ZZ and D is any digit. Total letter pairs: 26² = 676. Forbidden pairs: 3 (XX, YY, ZZ). Valid letter pairs: 676 - 3 = 673. Digit combinations: 10³ = 1000. Total valid codes: 673 × 1000 = 673,000. Since 673,000 > 15,000, all books can have distinct codes. B is wrong because sufficient codes exist. C is wrong because no modification needed. D is wrong because 673,000 ≠ 15,000.

Question 5

A computer network has 50 nodes, each assigned a unique 3-digit binary address (000, 001, 010, etc.). During a routing protocol update, each node must communicate with exactly 3 other nodes that differ from its address in exactly 2 bit positions. What can be concluded about the communication patterns?

  1. Every node can successfully establish its required 3 connections
  2. At least 10 nodes cannot establish all their required connections
  3. The network requires additional addressing bits to function properly
  4. At least 42 nodes cannot establish any of their required connections (correct answer)
Explanation: Each 3-bit address has exactly C(3,2) = 3 addresses that differ in exactly 2 positions. For example, 000 connects to 011, 101, 110. Since there are only 8 possible 3-bit addresses (000-111) but 50 nodes, by pigeonhole principle, many nodes must share addresses. Only 8 nodes can have unique addresses and establish their connections. The remaining 50-8 = 42 nodes cannot have valid 3-bit addresses and thus cannot establish any connections. A is wrong because insufficient unique addresses exist. B underestimates the problem. C suggests a solution but doesn't describe what 'can be concluded.'

Question 6

A digital art gallery displays artwork using a grid-based coordinate system where each artwork occupies a unit square. The gallery wall is a 15×20 grid, and currently has 47 artworks displayed. Each artwork is tagged with metadata indicating its primary color (red, blue, green, yellow, orange, purple) and style era (classical, modern, contemporary). If the curator wants to create a themed section by selecting artworks that share both the same primary color AND the same style era, what is guaranteed about the largest possible themed section?

  1. The largest themed section must contain at least 2 artworks with matching color and era
  2. The largest themed section must contain at least 3 artworks with matching color and era (correct answer)
  3. The largest themed section must contain at least 4 artworks with matching color and era
  4. The largest themed section must contain at least 5 artworks with matching color and era
Explanation: There are 6 colors × 3 eras = 18 possible combinations of color and era. With 47 artworks distributed among these 18 combinations, by the pigeonhole principle, at least ⌈47/18⌉ = ⌈2.61⌉ = 3 artworks must share the same color-era combination. Therefore, the largest themed section must contain at least 3 artworks. Choice A (2 artworks) is too weak a conclusion, while choices C (4 artworks) and D (5 artworks) would require 55+ and 73+ artworks respectively. The grid size (15×20 = 300 positions) is irrelevant since only 47 positions are occupied.

Question 7

A library organizes books using a classification system with 4-digit codes where each digit can be 0-9, but codes cannot start with 0 and cannot contain three consecutive identical digits. If the library acquires 3847 new books, what is the minimum number of books that must share the same first two digits in their classification codes?

  1. At least 39 books must share the same first two digits in their codes
  2. At least 43 books must share the same first two digits in their codes (correct answer)
  3. At least 47 books must share the same first two digits in their codes
  4. At least 35 books must share the same first two digits in their codes
Explanation: The first digit can be 1-9 (9 choices), and the second digit can be 0-9 (10 choices), giving 9×10 = 90 possible combinations for the first two digits. The constraint about three consecutive identical digits doesn't affect the first two digits. With 3847 books distributed among 90 possible first-two-digit combinations, by the pigeonhole principle, at least ⌈3847/90⌉ = ⌈42.74⌉ = 43 books must share the same first two digits. Choice A (39) is too small, while C (47) and D (35) represent common calculation errors in applying the ceiling function or miscounting the possible combinations.