Question

Russia 1996/4) In the Duma there are 1600 delegates, who have formed 16000 committees of 80 persons each. Prove that one can find two committees having at least four common members.

Answer 1

Explanation:

This problem can be solved using a technique called the Pigeonhole Principle. The Pigeonhole Principle states that if n+1 or more objects are placed into n pigeonholes, then at least one pigeonhole will contain two or more objects.

In this problem, we have 1600 delegates divided into 16000 committees of 80 persons each. We can think of each delegate as an object and each committee as a pigeonhole. Since 1600 delegates are placed into 16000 pigeonholes, we know that by the Pigeonhole Principle, at least one pigeonhole will contain two or more delegates.

In other words, there must be at least one committee that has at least two delegates in common with another committee. We can prove that there will be at least four common members by assuming the worse scenario where each committee is formed by different people, and noting that there are more delegates than the number of committees, so it's impossible that all committees have different members, and therefore there will be at least four common members.

Therefore, it is possible to find two committees having at least four common members.