AoPS Academy
and 
satisfy 
, then 
is an even number.
, not all equal to 
, the following inequality holds
for which the equality holds.
,
and 
are given, with 
. You play the following game against an evil wizard.
cards; for each 
, there are two cards labeled 
. Initially, the wizard places all cards face down in a row, in unknown order. of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the chosen cards and then turns them back face-down. Then, it is your turn again.
and some strategy that is guaranteed to win in at most moves, no matter how the wizard responds. and is the game winnable?
with real coefficients such that 
holds for all nonzero real numbers satisfying 
.
be the number of delegates that join both of them. Consider 
the number of committees that include delegate 
. Then the expected value of is![$\mathbb E [X]=\sum{d} \frac{\binom{a_{d}}{2}}{\binom{16000}{2}}\geq \frac{1600\binom{\frac{\sum{d} a_{d}}{1600}}{2}}{\binom{16000}{2}}=\frac{1600\binom{800}{2}}{\binom{16000}{2}}>3 $](http://latex.artofproblemsolving.com/5/a/7/5a79e5f2b8bbe8eb8eeedd33f2b8c99c424a7a29.png)
, and the conclusion follows.
committees, I think this inequality holds! If this is the case, why did they ask for 
when they could have asked for 
?
be the number of delegates that join both of them. Consider the number of committees that include delegate . Then the expected value of is, and the conclusion follows.![$\mathbb E [X]=\sum_{d} \frac{\binom{a_{d}}{2}}{\binom{16000}{2}}\geq \frac{1600\binom{\frac{\sum a_{d}}{1600}}{2}}{\binom{16000}{2}}= \frac{1600\binom{\frac{16000 \cdot 80}{1600}}{2}}{\binom{16000}{2}} = \frac{1600\binom{800}{2}}{\binom{16000}{2}}>3 $](http://latex.artofproblemsolving.com/d/6/9/d6914d987e87c6a030344f9af1de0d7c5adf4f8b.png)
, denote by 
the number of committees delegate belongs to. Thus we immediately have 
. We now count all triples of form 
, where is a delegate, and 
are two distinct committees such that 
. Clearly, there are 
such triples. In particular, using the convexity of 
, together with Jensen's we further get 
, where 
. Now the ratio
is larger than 
, using the estimate above. Thus by Pigeonhole principle, there is a pair of committees belonging to at least four triples, each with a distinct first coordinate, finishing the proof.
be the number of triples Suppose every two committees have 
people in common. Let be the number of triples , where person is part of both 
and 
. Choose the person . Suppose he is in 
committees. Then![\[ T = \binom{x_1}{2} + \cdots+\binom{x_{1600}}{2} \ge 1600\binom{\frac{x_1+\cdots+x_{1600}}{1600}}{2} = 1600 \binom{80\cdot 16000/1600}{2} = 1600\binom{800}{2}. \]](http://latex.artofproblemsolving.com/1/c/d/1cde2a986a964bba477a742312edc18d73c43024.png)
Choose in 
ways. These have at most 3 people in common, so![\[ T \le 3\binom{16000}{2}. \]](http://latex.artofproblemsolving.com/4/d/6/4d6ce58901aa347914f365f8350e76b436a2508a.png)
However, 
, contradiction.
to 
. Let 
be the number of committees person is in. Notice that 
., there exist 
pairs of conmittees both containing person , hence each pair of committees has a 
chance of containing person .![\begin{align*}
\mathbb{E} [\text{number of common members}] &= \sum_{k=1}^{1600} \mathbb{P} [\text{person } k \text{ is in both}] \\
&= \frac1{\binom{16000}{2}} \sum_{k=1}^{1600} \binom{a_k}{2} \\
&\ge \frac1{\binom{16000}{2}} \cdot 1600 \binom{800}{2} \\
&= 80 \cdot \frac{799}{15999} = 4 - \varepsilon,
\end{align*}](http://latex.artofproblemsolving.com/b/f/5/bf5cb39be67d55fe5aa995fbcb92acdc520dc269.png)
where the inequality is by Jensen's. Therefore there exist one pair of committees having at least four common members. 
random committees, and let ![$\mathbb{E}[X]$](http://latex.artofproblemsolving.com/9/6/b/96b30ae03a52fb0ed2422456fea6acc792c37cc1.png)
be the expected number of delegates on both the committees. We prove that ![$\mathbb{E}[X] >3$](http://latex.artofproblemsolving.com/7/7/4/77424eaa7d745a0dc5bba4a29dab600fc0b954be.png)
.
pairs of committees. Let 
be the number of committees delegate is on, for 
. Furthermore, the sum of all the must be equal to 
Now we have that
and computing , we find that![$$\mathbb{E}[X] = \frac{\sum_{i = 1}^{1600} \binom{a_i}{2}}{\binom{16000}{2}} \geq \frac{1600 \binom{800}{2}}{\binom{16000}{2}} = \frac{80 \cdot 799}{15999} > 3$$](http://latex.artofproblemsolving.com/c/8/1/c815f320c5fcedcd77e3f3a8221ee9f12cb31b40.png)
as desired.
delegate is on be 
We will calculate the expected number of committees that any two delegates are both on.
Let be the expected number of delegates on any two randomly chosen committees. Then, we can easily compute to get![$$\mathbb{E}[X]=\frac{\sum \tbinom{a_i}{2}}{\tbinom{16000}{2}} \ge \frac{1600\tbinom{800}{2}}{\tbinom{16000}{2}} = \frac{80 \times 799}{15999} > 3,$$](http://latex.artofproblemsolving.com/3/b/f/3bfb5b5902f53578e0b98313a77471ee42014b94.png)
Where we use Jensen's Inequality. Because the expected value is greater than , there must certainly exist two committees with at least 
coinciding members.
post!
, and let delegate be in committees. Clearly:
so on average each delegate is a member of 
committees. be the number of delegates that are members of both. Then:![\begin{align*}
\mathbb{E}[X]&=\sum_{i=1}^{1600} \frac{\binom{a_i}{2}}{\binom{16000}{2}}\\
&\geq \frac{1600 \binom{800}{2}}{\binom{16000}{2}}\\
&=\frac{80(799)}{15999}\\
&>3,
\end{align*}](http://latex.artofproblemsolving.com/6/4/2/642950014f5eb2049ed1ab871d0191909bc76fed.png)
hence there must be some pair of committees with at least common delegates, as desired.
.
for each member to be the set ![$[a_1,a_2,......,a_X]$](http://latex.artofproblemsolving.com/6/7/7/677ab56938c616436def71b32485c9cb27e28f0f.png)
as the committee's in which an member is in and denote 
,hence we are done.
delegates, who have formed 
committees of 
persons each. Prove that one can find two committees having no fewer than four common members.
. be the number of committees the 
is in.Then 
.Count triplets 
such that the delegate 
is in both 
and 
.Denote this sum .Then 
this gives that 
, a contradiction.
total appearances of any delegate in any committee, we expect to see each delegate in 800 committees. Thus, there are a total of 
delegates in the intersection of any two committees. As there are 
committees, the average size of intersection is 
As a result, there must exist two committees whose intersection contains four or more members
, but instead depends on the number of committees that specific delegate is in. The probability is different if they're in every committee or in only one.
is achievable, I wouldn't have batted an eye at the erroneous solutions.
be the number of people in the two chosen committees, and define 
to be if person is in both of the chosen committees and otherwise. Let denote the number of committees delegate is a member of. Then we have that 
, and also ![$\mathbb{E}[X_i] = \mathbb{P}(X_i = 1) = \frac{\binom{n_i}{2}}{\binom{16000}{2}}$](http://latex.artofproblemsolving.com/1/8/e/18ef486b41df560e6bb9a03988e227455e51cc2d.png)
. Finally we have that 
, and so the average amount of committees delegate is a member of is 
. Thus we have that
However must be an integer so ![$\mathbb{E}[X] \geq 4$](http://latex.artofproblemsolving.com/6/d/d/6ddd018c42875072282fe384a0f58a47789194de.png)
, and we are done 
and the committees be 
. In addition, we define 
as the number of triplets 
such that 
belongs to both 
and 
. belongs to committees, then we know ![\[ \sum_{i=1}^{1600} x_i = 16000 \cdot 80 \]](http://latex.artofproblemsolving.com/a/8/9/a89010e6e50a0a3f80ff12cce2321554e76935ff.png)
and ![\[ S = \sum_{i=1}^{1600} \binom{x_i}{2} = \frac{1}{2} \left(\sum_{i=1}^{1600} x_i(x_i - 1) \right) = \frac{1}{2} \left(\left( \sum_{i=1}^{1600} x_i^2 \right) - 16000 \cdot 80 \right) \]](http://latex.artofproblemsolving.com/c/6/5/c658b2ed5aec7220b88ea2410e099df84060f6ea.png)
![\[ \ge \frac{1}{2} \left( \frac{\left( x_1 + x_2 + \ldots + x_{1600} \right)^2}{1600} - 16000 \cdot 80 \right) \]](http://latex.artofproblemsolving.com/6/3/7/6375f2f0e745d46259c2f71ec79ff4cffaef6e54.png)
![\[ = \frac{1}{2} \left( 160000 \cdot 80^2 - 16000 \cdot 80 \right) = 8000 \cdot 80 \cdot 799 \]](http://latex.artofproblemsolving.com/c/e/9/ce9f420ec40370eb707c8082a73f17f1aabf084d.png)
where the inequality follows from Cauchy-Schwarz. Now, we have ![\[ \frac{S}{\binom{16000}{2}} \ge \frac{8000 \cdot 80 \cdot 799}{\binom{16000}{2}} = \frac{80 \cdot 799}{15999} > 3. \]](http://latex.artofproblemsolving.com/d/a/1/da1e4e5e338d9bb17a9c56a78d35a52b226ffcc6.png)
Thus, the average number of shared members between two committees is greater than . The desired result follows easily. 
such that 
is a person in both committees and 
. Suppose person is in 
committees, noting 
Counting by committees, this sum is 
. Counting by person, this sum is ![\[\sum_{i=1}^{1600}\binom{B_i}{2}\ge 1600\binom{\sum B_i/1600}{2}=1600\binom{800}{2}\]](http://latex.artofproblemsolving.com/e/d/d/edd6f186655ecb2d7c7ad7f218a82546c6867df3.png)
Hence, the expected value of 
is ![\[\frac{1600\binom{800}{2}}{\binom{16000}{2}}>3\]](http://latex.artofproblemsolving.com/9/2/e/92e673809e6b18a4e7339d597a9a45b8c086e967.png)
so at least one of is at least . 
th delegate be in 
committees. The total number of common members over all pairs of committees is 
and there are pairs of committees. Since 
, some pair of committees must have at least common members.
th delegate was in committees. We see that 
. For any two committees the expected value of the number of common members is ![\[ \frac{ \sum_{i=1}
^{1600} \binom{a_i}{2} }{\binom{16000}{2}} \ge \frac{1600 \cdot \binom{800}{2}}{\binom{16000}{2}} = \frac{1600 \cdot 800 \cdot 799}{16000 \cdot 15999} > \frac{48000}{15999} > 3 ,\]](http://latex.artofproblemsolving.com/0/6/a/06a2fcee19c5937451a1401676d48d2d16edd9ad.png)
by Jensen. The largest integer greater than this is , so we must have two committees having at least common members.
, and let 
be the number of committies is in. Then we have
Now, let be the number of (unordered) triplets 
, where 
, are two committees and belongs to both of them. Then if every two committees have at most common members, we have
But counting in terms of the , from Jensen we get
contradiction.
denote the number of committees the th person is in. Note that the average of all is . The expected value of delegates in the intersection of two random committees is 
where the last step is true by Jensen's. A quick computation confirms this is greater than 3, so there must exist two committees that have at least four delegates in common.
be the number of committees the th delegate is in. We have 
. For any two committees, the expected number of commmon members is 
.
. Clearly, 
is convex so we apply Jensen's to get![\[\sum \binom{a_i}{2}=\sum f(a_i) \ge 1600 f \left(\frac{\sum a_i}{1600} \right)=1600f(800)\]](http://latex.artofproblemsolving.com/4/3/1/431bb9bb912a5e2f5b51230bc0ef6beacc6c9b2e.png)
![\[\frac{\sum \binom{a_i}{2}}{\binom{16000}{2}} \ge \frac{1600 \cdot \binom{800}{2}}{\binom{16000}{2}}>3\]](http://latex.artofproblemsolving.com/5/1/d/51dbf5348dfedf5f53e162cc4f5d30015ae955a8.png)
common members. 
th person be in committees. If we choose two random distinct committees, the expected number of delegates in both committees is then 
However, we have that 
and by QM-AM we get 
Then we compute 
so there must be a pair with at least common members.
delegate be in committees. Note that the total number of intersections of committees is given by and by jensens is greater than
The average number of intersections between committees over all pairs is thus greater than
Hence there must exists committees with an intersection of at least people 
delegates, label them 
, 
, 
, 
, and let delegate 
for some integer 
be in different groups. Let 
of two delegate groups count how many delegates are in both 
and 
. Over all unordered pairs of different groups 
, let be the sum of all 's. Note that![\[S=\sum_{i=1}^{1600}\binom{a_i}{2},\]](http://latex.artofproblemsolving.com/5/4/8/548676fb006c6d6dd325f6e84f1b03328cdc5fb4.png)
and since there are groups with people each, we also know that 
. Therefore, by Jensen-Karamata's, we have that![\[S=\sum_{i=1}^{1600}\binom{a_i}{2}\geq 1600*\binom{\frac{16000(80)}{1600}}{2}=1600\binom{800}{2}.\]](http://latex.artofproblemsolving.com/3/4/3/343161dd5ba5d885b477a46380bdb43e512b8460.png)
Therefore the total average of the number of intersections between any two groups of delegates is![\[\frac{1600\binom{800}{2}}{\binom{16000}{2}}=\frac{1600(800)(799)}{16000(15999)}=\frac{80(799)}{15999}>\frac{80(600)}{15999}=\frac{48000}{15999}>3.\]](http://latex.artofproblemsolving.com/b/1/a/b1a327c0a95263202cbf3b8236d8419b3fda14af.png)
By probabilistic method, this gives us that there must be at least one pair of two different groups such that there are at least different delegates that are members of both groups.
be denoted by and committee be denoted by . Now assume that person appears in committees. Then let us count groups of the form 
such that appears in and where 
. Clearly this quantity is just,
Now note that in total there are pairs of committees 
. Thus if we find that, 
then we would be done by pigeonhole as then at least one committee pair, would have triples of the form for distinct values of . However this is true so we are done.
committees on average(by global counting (delegate,committee) pairs), so by Jensen the number of these pairs is at least 
. Therefore, some pair of committees has![\[\left\lceil \frac{1600\cdot\binom{800}{2}}{\binom{16000}{2}} \right\rceil=4\]](http://latex.artofproblemsolving.com/0/1/9/0191d7185ec0b1734297b7820f434b8b6f57f47e.png)
common members. 
be the th delegate. Then is the number of committees that delegate is in.![\[\frac{\sum_{i=1}^{1600}\binom{x_i}{2}}{\binom{16000}{2}}\]](http://latex.artofproblemsolving.com/f/8/a/f8ad6ac6d1e3016e6812cdd348452d88e873e75c.png)
.
is convex, by Jensen's we have![\[\frac{\sum_{i=1}^{1600}\binom{x_i}{2}}{\binom{16000}{2}} \geq \frac{1600 \cdot \binom{800}{2}}{\binom{16000}{2}} = \frac{1600\cdot800\cdot799}{16000\cdot15999}\]](http://latex.artofproblemsolving.com/9/a/1/9a17b57ceeb9915988aa6e2c7745d7259c503b41.png)
. This is approximately less than ![\[80 \cdot \frac{1}{20} = 4\]](http://latex.artofproblemsolving.com/6/2/8/62829a9b5156b48aeb26c34ba29aab31ccc36310.png)
Since the expected value is less than , and the number of common committee members is whole, there has to be at least one pair of committees that has common members.
.
be the number of committees each delegate is a part of. Consider counting pairs 
of committees and delegates. Counting by committees then delegates we find![\[d_1+d_2+\dots+d_{1600}=16000\cdot 80.\]](http://latex.artofproblemsolving.com/f/c/0/fc032db0c70b30ff26311722e54e3be0df28da64.png)
of two committees and one delegate. Counting by delegates, we have![\[\binom{d_1}{2}+\binom{d_2}{2}+\dots+\binom{d_{1600}}{2}\ge 1600\binom{16000\cdot 80\div 1600}{2}=A\]](http://latex.artofproblemsolving.com/7/b/d/7bd328b711a57a564cd5e83c4fd6f5f5a8fc5bd7.png)
and there are also 
pairs of committees. Hence it suffices to show that 
to finish by Pigeonhole.![\[A=1600\cdot 400\cdot 799\]](http://latex.artofproblemsolving.com/c/1/b/c1b56185a6cf7f0dcf1d020ff6bf93c2cee7b904.png)
![\[B=8000\cdot 15999\]](http://latex.artofproblemsolving.com/d/7/a/d7a31ae1d1d887080936542b8d6396544aa9277a.png)
![\[\frac{A}{B}=\frac{80\cdot 799}{15999}>3\iff 80\cdot 799>3\cdot 15999\]](http://latex.artofproblemsolving.com/5/4/e/54ecd4848a86cadec31b1aa7cbfd6c14849dcd0f.png)
which is obviously true.
be the set of delegates, and 
be the number of committees the delegate is in. Note that![\[\sum_{d \in S} c(d) = 16000 \cdot 80 \quad \text{and} \sum_{d \in S} \quad \binom{c(d)}{2}\]](http://latex.artofproblemsolving.com/1/9/0/1905789452902f22649257e989e93284097511af.png)
![\[\sum_{d \in S} \frac{\binom{c(d)}{2}}{\binom{16000}{2}} \ge 1600 \cdot \frac{\binom{800}{2}}{\binom{16000}{2}} = 80 \cdot \frac{799}{15999} > 3.\]](http://latex.artofproblemsolving.com/7/1/7/71750f2cb4d0cdaad6b1d0a744b00eda2f84c323.png)
belongs to commitees. We will choose two commitees at random, the expected number of common members by linearity of expectation is
Now it is easy to see that 
. Therefore it is sufficient to show that
which implies that two commitees can be chosen with at least common members, as wanted.
be in 
committes, respectively. The key is to count the number of common members by each member then divide by . The expected number of common members from an arbitrary pair of committes is then 
and also 
. By Jensens we have 
, so one pair of committes must have at least four members. This really is the epitome of an easy global problem.
Then for some pair of committees, we count the expected number of delegates that joined both of them.
Thus by Jensen's the expected value is 
QED
be the number of committees that the -th delegate is in. The probability that a delegate is in two arbitrarily selected committees is 
. Summing over all gives us the expected number of people in both of the committees: 
. Because 
, Jensen allows us to determine the lower bound on the expression to be 
. 
. We will count the number of unordered pairs of 
where person 
is in committees 
. Suppose for sake of contradiction all pairs of committees have at most common members. Then 
be the number of commitees person is in. Then by Jensen's 
which is untrue.
be the number of committees the member is in. Thus, we have that 
We also have that
Thus, we are done.
.
.
![\[\sum_{i=0}^{1600}c_i=16000\cdot80\]](http://latex.artofproblemsolving.com/7/7/e/77ef5b2591b73edc4e252aa14dda7c4fd42e1b32.png)
But Jensens tells us![\[\frac{\sum \binom{c_i}{2}}{\binom{16000}{2}}\geq \frac{1600\cdot \binom{80}{2}}{\binom{16000}{2}}\]](http://latex.artofproblemsolving.com/8/8/d/88de94c427e04e8efa86b57c6e46c890ce3864f2.png)
A simple calculation tells us the RHS is greater than 3, so there exist two committees with at least four common members, as desired.
in some order, and call the delegates 
.
.
with probability 
.
members in the 
Also, let candidate 
Then, note that 
pairs of committees will both have member 
so it follows that the total number of triples 
of positive integers such that committees 
and 
both have delegate 
Thus, the expected number of common members been two arbitrary committees is 
It suffices to prove that the minimum possible value of this expression is greater than 
Note that the function 
is convex for 
Therefore, since we have
it follows by Jensen's Inequality that
Hence, since the smallest possible expected value is greater than 
there must be at least one pair of committees with at least four common members, as desired.