Set $S$ to be a subset of size $68$ of $\{1,2,...,2015\}$. Prove that there exist $3$ pairwise disjoint, non-empty subsets $A,B,C$ such that $|A|=|B|=|C|$ and $\sum_{a\in A}a=\sum_{b\in B}b=\sum_{c\in C}c$
Problem
Source: 2015 China TST 2 Day 2 Q2
Tags: combinatorics, combinatorics proposed
23.03.2015 06:11
05.06.2018 15:33
mad to see the extreme beauty of the problem! However I avoid details ! Note that in any 68 element subset atleast 9 '3-element' subsets have same sum . Left to show atleast 3 of them are pairwise disjoint . Take that 9 subsets . Now set a graph as follows - The vertices are the subsets and two vertex have a edge between them iff their corresponding sets are disjoint ! If we have a triangle then done unless by turan's th. the graph has atmost 20 edges .So avg deg. 4 . Take a vertex having deg. 4 [such a vertex readilly exists by php] There are 4 pts disconnected to it so the corresponding sets have a element common with the set.[Note that any 2 such 3-subsets have atmost 1 element common unless 2 sets are same]Take 3 sets and through out the common element to get 3 sets with cardinality 2 fulfilling the property !