Search problems

13 problems match “pigeonhole principle”. Clear

Guaranteeing a shared birthday ●○○○○ 10 ptsWhat is the smallest number of people needed in a group to guarantee that two of them share the same birthday? Assume there are 366 possible birthdays, including 29 February.
Guaranteeing a red ball in draws ●○○○○ 10 ptsA bag contains 10 red balls, 8 white balls and 7 black balls. The balls are drawn one by one at random, without replacement. Find the minimum value of $k$ such that a red ball is guaranteed to have been drawn by the $k$ -th draw (on the $k$ -th draw or earlier).
Pigeonhole for shared birthdays ●○○○○ 10 ptsWhat is the smallest number of people needed to be certain that at least two of them have the same birthday? Assume there are 366 possible birthdays (including February 29).
Maximum months with five Sundays ●●○○○ 20 ptsA month can have at most 5 Sundays. In a year of 12 months, what is the maximum number of months that can have 5 Sundays?
Passwords with equal lowercase counts ●●○○○ 20 ptsComputer passwords are between 6 and 8 characters long. Each character is an upper case letter, a lower case letter or a digit. Each password has at least one upper case letter, at least one lower case letter and at most one digit. Let $S$ be a set of such passwords. What is the minimum size of $S$ that guarantees at least two passwords in $S$ have the same number of lower case letters?
Guaranteed shared birthday count ●●○○○ 20 ptsAmong 10,000 people, what is the largest number of people who are guaranteed to share the same birthday (ignoring the year)? Count February 29 as a possible birthday; the answer is the same with or without it.
Smallest group with matching last four digits ●●●○○ 50 ptsAssume each person's last four digits are equally likely to be any of 0000 to 9999, independently. What is the smallest number of people needed so that the probability that at least two of them have the same last four digits is at least 99.9%?
Maximum red beads on a string ●●●○○ 50 ptsA string is threaded with 150 beads, each red, blue or green. Among any six consecutive beads there is at least one green bead, and among any eleven consecutive beads there is at least one blue bead. What is the maximum number of red beads on the string?
Minimum distinct values in a ratio chain ●●●○○ 50 ptsLet $a_{1}, a_{2}, \ldots, a_{2006}$ be positive integers (not necessarily distinct) such that the 2005 ratios $\frac{a_{1}}{a_{2}}, \frac{a_{2}}{a_{3}}, \ldots, \frac{a_{2005}}{a_{2006}}$ are all distinct. What is the least possible number of different values among $a_{1}, a_{2}, \ldots, a_{2006}$ ?
Matches played in a football tournament ●●●●○ 100 ptsA football invitational tournament involves sixteen cities, each sending two teams, Team A and Team B. Each pair of teams plays at most one match, and teams from the same city do not play each other. After several days, every team except Team A from City A has played a different number of matches. How many matches has Team B from City A played?