سوال ۱۱۶ کنکور ارشد علوم کامپیوتر ۱۳۹۹

Translating the conditions into bounds on the number of classes

Group people by age. The condition “among every $5$ people, two are the same age” means there is no set of $5$ people all of distinct ages — otherwise those $5$ would violate the condition. So the number of distinct ages is at most $4$:

$\#\text{age-classes} \le 4.$

Similarly, “among every $4$ people, two share a birthplace” means there is no set of $4$ people all from distinct cities, so the number of distinct birthplaces is at most $3$:

$\#\text{city-classes} \le 3.$

Combine the two attributes

Each person is labeled by a pair $(\text{age},\,\text{city})$. The number of possible distinct pairs is at most

$4 \times 3 = 12.$

We have $99$ people distributed among at most $12$ pairwise classes. By the generalized pigeonhole principle, some class contains at least

$\left\lceil \frac{99}{12} \right\rceil = \lceil 8.25 \rceil = 9$

people — i.e. at least $9$ people share both the same age and the same birthplace. So the statement is always true for $K = 9$.

Why $K$ cannot be larger (the bound is tight)

We must exhibit a valid configuration in which no class exceeds $9$, so $K = 10$ can fail. Take exactly $4$ ages and $3$ cities, giving $12$ classes, and split $99 = 12\cdot 8 + 3$ as: three classes of $9$ people and nine classes of $8$ people.

• Every age appears (each age-class is nonempty), and only $4$ ages exist, so any $5$ people include two of the same age. ✓
• Every city appears, and only $3$ cities exist, so any $4$ people include two from the same city. ✓
• The largest $(\text{age},\text{city})$ class has exactly $9$ people, so “at least $10$” is false here.

Hence $K = 10$ is not guaranteed, while $K = 9$ always holds. The largest such $K$ is $\boxed{9}$.

Exam trick: “Among every $m$ people, two share property $P$” is just a disguised cap on the number of classes of $P$: at most $m-1$ classes. Multiply the caps for the two attributes to get the number of joint boxes, then apply $\lceil n/\text{boxes}\rceil$.