A set of balls contains $ n$ balls which are labeled with numbers $ 1,2,3,\ldots,n.$ We are given $ k > 1$ such sets. We want to colour the balls with two colours, black and white in such a way, that (a) the balls labeled with the same number are of the same colour, (b) any subset of $ k+1$ balls with (not necessarily different) labels $ a_{1},a_{2},\ldots,a_{k+1}$ satisfying the condition $ a_{1}+a_{2}+\ldots+a_{k}= a_{k+1}$, contains at least one ball of each colour. Find, depending on $ k$ the greatest possible number $ n$ which admits such a colouring.
Problem
Source: MEMO Individual Competition, Question 2
Tags: combinatorics proposed, combinatorics
26.09.2007 12:26
The answer is $ n=k^{2}+k-2$. =============================================== Lower bound: $ n=k^{2}+k-2$ is possible. Use color white for the numbers $ 1,\ldots,k-1$ and for $ k^{2},\ldots,k^{2}+k-2$ . Use color black for the numbers $ k,\ldots,k^{2}-1$. If there was a monochromatic black solution to the equation, then $ a_{1},\ldots,a_{k}$ all are $ \ge k$. Hence $ a_{k+1}\ge k^{2}$; contradiction. If there was a monochromatic white solution to the equation, then $ a_{k+1}\ge k^{2}$; hence one of $ a_{1},\ldots,a_{k}$ must be strictly greater than $ k-1$. Hence one of $ a_{1},\ldots,a_{k}$ must be at least $ k^{2}$, and the others are all at least 1. Hence their sum is at least $ k^{2}+k-1$; contradiction. =============================================== Upper bound: $ n=k^{2}+k-1$ is not possible. For the sake of contradiction assume that there is a solution with $ n=k^{2}+k-1$. Assume w.l.o.g. that 1 is colored white. Then $ k$ must be black. Then $ k^{2}=k+\cdots+k$ must be white. Then $ x=k^{2}+k-1=k^{2}+(1+1+\cdots+1)$ must be black. And $ y=k^{2}-k+1$ must be black, since $ y+(1+\cdots+1)=k^{2}$. Furthermore 2 must be white, since $ y+(2+\cdots+2)=x$. Since 1 and 2 are white, $ k,\ldots,2k$ must be black. Since $ k,\ldots,2k$ are black, $ k^{2},\ldots,k^{2}+k-1$ must be white. Hence $ x=k^{2}+k-1$ must be white. Contradiction. ===============================================