Difference between revisions of "2001 OIM Problems/Problem 3"
(Created page with "== Problem == Let <math>S</math> be a set of <math>n</math> elements and <math>S_1, S_2, \cdots , S_k</math> subsets of <math>S</math> (<math>k \ge 2</math>), such that each...") |
|||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Let <math>S</math> be a set of <math>n</math> elements and <math>S_1, S_2, \cdots , S_k</math> subsets of <math>S</math> (<math>k \ge 2</math>), such that each of them has at least <math>r</math> elements. Show that <math>i</math> and <math>j</math> exist, with <math>1 \le i < j \le k such that the number of common elements of < | + | Let <math>S</math> be a set of <math>n</math> elements and <math>S_1, S_2, \cdots , S_k</math> subsets of <math>S</math> (<math>k \ge 2</math>), such that each of them has at least <math>r</math> elements. Show that <math>i</math> and <math>j</math> exist, with <math>1 \le i < j \le k</math> such that the number of common elements of <math>S_i</math> and <math>S_j</math> is greater than or equal to |
<cmath>r-\frac{nk}{4(k-1)}</cmath> | <cmath>r-\frac{nk}{4(k-1)}</cmath> | ||
Latest revision as of 04:12, 14 December 2023
Problem
Let 
be a set of 
elements and 
subsets of (
), such that each of them has at least 
elements. Show that 
and 
exist, with 
such that the number of common elements of 
and 
is greater than or equal to
![\[r-\frac{nk}{4(k-1)}\]](http://latex.artofproblemsolving.com/7/1/8/7186b9862ddea51503def6f463aecca38bab5edb.png)
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
This problem needs a solution. If you have a solution for it, please help us out by adding it.
