MathDB

2

Part of 2008 Miklós Schweitzer

Problems(1)

Miklós Schweitzer 2008, Problem 2

Source: Miklós Schweitzer 2008

7/30/2016
Let t≥3t\ge 3 be an integer, and for 1≤i<j≤t1\le i <j\le t let Aij=AjiA_{ij}=A_{ji} be an arbitrary subset of an nn-element set XX. Prove that there exist 1≤i<j≤t1\le i < j\le t for which ∣(X \ Aij)∪⋃k≠i,j(Aik∩Ajk)∣≥t−22t−2n\left| \left( X\,\backslash\, A_{ij}\right) \cup \bigcup_{k\neq i,j}\left( A_{ik}\cap A_{jk}\right) \right| \ge \frac{t-2}{2t-2}n
(translated by Miklós Maróti)
Miklos Schweitzercollege contestsset theory