2
$\begingroup$

In the Duma there are $1600$ delegates, who have formed $16000$ committees of $80$ persons each. Prove that one can find two committees having no fewer than four common members.

Source: All-Russian Olympiad 1996

I am especially interested in an answer that would describe the right kind of strategy to attack this type of problem, because it looks like a probabilistic method problem, but seems not to be solvable with the most common strategies.

$\endgroup$
2
$\begingroup$

Let's do this problem in two different ways. First, this question screams pigeon-hole principle to me, so we'll start with that.

There are 16000 committees, each with 80 people. So there are 1280000 different committee members across all the committees. Since there are only 1600 people, and 1280000 memberships, at least one committee member (call him Bob) is in at least 800 committees. (Bob's an overachiever).

Now, as is classic, we'll finish with contradiction. Suppose that no pair of committees have four common members, and thus have at most 3. Look at the 800+ committees that Bob is in. Aside from Bob, each of Bob's committees have at most 2 people in common.

So how many people must there be? In Bob's first committee, there are 79 more people. In his second committee, there are at least 77 more people (since maybe 2 have already been counted). In his third, at least 75, and so on. By Bob's 40th committee, we claim there are at least $79 + 77 + 75 + \ldots + 1$ people, aside from Bob.

But $1 + 2 + 3 + \ldots + 79 = 80\cdot79/2 = 40\cdot79$, and $2 + 4 + 6 + \ldots + 78 = 2(1 + 2 + 3 + \ldots + 39) = 2(39\cdot40/2) = 39\cdot40$.

So $1 + 3 + 5 + \ldots + 79 = 40\cdot79 - 40\cdot39 = 40\cdot40 = 1600$, so there are at least 1600 people aside from Bob in Bob's committees! That's impossible, as there are only 1600 people! So we've reached our contradiction, and finished the proof. (And we see Bob only needed to be in 40 committees for this fallacy to hold, not 800).


Now, method 2 - probabilistic, as you ask for. For probabilistic solutions, you often just go immediately after exactly what you want.

So let's take two uniformly random committees and find their expected common membership. There are ${16000 \choose 2}$ possible pairs of committees. If $X$ is the number of people who serve on both committees, then $X$ can be written as $X = X_1 + X_2 + \ldots X_{1600}$, where $X_i$ is a random variable corresponding to whether the $i$th person is in both committees (thus meaning $X_i = 1$) or not ($X_i = 0$).

Expected values are linear, so $E(X) = E(\sum X_i) = \sum E(X_i)$. So it would be great it we could calculate or approximate or bound $E(X_i)$. Perhaps surprisingly, we can.

If the $i$th person is in $c_i$ committees, then $E(X_i) = {c_i \choose 2}/{16000 \choose 2}$. We know that $\sum n_i = 16000\cdot 80$, so that $\bar n = 16000\cdot 80 / 1600 = 800$, where I use $\bar n$ to denote the average. By Jensen's inequality (or a common probability fact about convex functions/sums of expectations), $E(X)$ is at least as much as what would be given by the average $\bar n$, which is $1600 \cdot {800 \choose 2}/{16000\choose 2} = 1600\dfrac{800\cdot799}{16000\cdot15999} = 3.995$.

On the one hand, this is less than $4$. On the other hand, since it's greater than $3$ and the values are always integers, this means that there are pairs of committees that contain at least $4$ members. And so we have our second proof.

$\endgroup$
  • $\begingroup$ I don't get how you conclude that Bob's second comittee has at least 77 new people. Bob's second committee could very well be made up of Bob and a fresh batch of 79 others, and so on for some time (up to 20 committees made of Bob and 79 underwhelming underachievers in one committee each are possible). $\endgroup$ – vonbrand Jun 20 '14 at 13:12
  • $\begingroup$ @vonbrand "At least". $77 < 79$, so I'm not disagreeing with you at all. $\endgroup$ – davidlowryduda Jun 20 '14 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.