Show that there is a subset of $A$ from $\{1,2, 3,... , 2014\}$ such that : (i) $|A| = 12$ (ii) for each coloring number in $A$ with red or white , we can always find some numbers colored in $A$ whose sum is $2015$.
Problem
Source: INAMO Shortlist 2015 C7
Tags: combinatorics, Sum, Subset
17.05.2019 07:25
Note that $2015 = 155 . 13$, so we simply prove the following: if $A = \{ 1, \dots, 12 \}$ and each element is colored red or white, there are numbers colored with a single color whose sum is $13$. Then we multiple everything by $155$ to achieve the desired result. In order to prove the above assertion, this is the best one I can come up with. Maybe you can find a more elegant proof. Define the majority color to be one that has the most member (pick arbitrary color if it's 6 and 6). WLOG majority color is red. Now let $k$ be the smallest red number. If $k = 7$ then 1,2,3,4,5,6 are all white, so $3+4+6 = 13$. If $k = 3,4,5,6$ then 1 and $k-1$ are white. Consider $13-k$. If it's red, then $k+(13-k) = 13$. If $13-k$ is white then $1 + (k-1) + (13-k) = 13$. Now we consider $k=2$. Suppose the above assertion is false. So 1 is white, 12 is red, 11 is white. Consider $m$ the second lowest red number. If $m = 7$ then 3,4,5,6 are all white then 3+4+6 = 13. It can't be more than 7 because red is majority. If $m=4,5,6$ then consider $13-m$. It has to be white. But then $1+(m-1)+(13-m) = 13$ are all white numbers. So $m=3$, which means we get the following chain of deductions (to avoid contradiction): 8 is white, 5 is red, 6 (13-5-2) is white, 7 is red, 4 (13-1-8) is red. But then 2+4+7 = 13 are all red numbers. Last case is for $k=1$. Again, let $m$ be the second lowest red number. If $m=7$ then 23456 are all white so 3+4+6 = 13. If $m=6$ then consider 7. If 7 is white then 2+4+7 are all white, but if 7 is red then 6+7 are all red. If $m=4,5$ then consider $12-m$. If it's red then $1 + m + (12-m) = 13$ are all red numbers. If it's white then $2 + (m-1) + (12-m)$ are all white numbers. If $m=2$ then we get the following chain of deductions: 10 (13-1-2) is white, 3 is red, 9(13-1-3) is white, 4 is red, and so on, we arrive with 123456 all red, which means 3+4+6 are all red numbers. If $m=3$ then we can still continue the same chain of deductions above to deduce 3,4,6 are all red.