I think the problem is related with Dilworth's Lemma. It looks like the anwser is the smallest $k$ satisfying the inequality $k^2 + 1 \geq 2012$. But I couldn't manage to set a proper (reflexive, transitive, and antisymmetric) relation to get a partially ordered set to simulate the chains and the anti-chains. Comment: In fact, the problem is proposed in a Junior Level Exam. And nobody got a full credit.

crazyfehmy wrote: We want to place $2012$ pockets, including variously colored balls, into $k$ boxes such that i) For any box, all pockets in this box must include a ball with the same color or ii) For any box, all pockets in this box must include a ball having a color which is not included in any other pocket in this box Find the smallest value of $k$ for which we can always do this placement whatever the number of balls in the pockets and whatever the colors of balls. We can always do this for $k=1$. So the problem must be "Find the biggest value of $k$ ..."

yunxiu wrote: crazyfehmy wrote: We want to place $2012$ pockets, including variously colored balls, into $k$ boxes such that i) For any box, all pockets in this box must include a ball with the same color or ii) For any box, all pockets in this box must include a ball having a color which is not included in any other pocket in this box Find the smallest value of $k$ for which we can always do this placement whatever the number of balls in the pockets and whatever the colors of balls. We can always do this for $k=1$. So the problem must be "Find the biggest value of $k$ ..." You cannot. Think $2011$ pockets containing only red ones. And $1$ pocket containing only blue ones. In that case, there should be $2$ boxes. We want to guarantee that kind of partitioning. Suppose there are $k=2012$ boxes. In that case, after placing each pocket into a box, we guarantee to satisfy the conditions given. But this $k$ is not least. Suppose there are $k=2011$ boxes. Pick $2$ of $2012$ pockets, and put them into a box. And the other $2010$ pockets will put into separate boxes. If the two put into a box have a common color, we satisfy the condition $i$. Else, they are disjoint, so $ii$ is satisfied. So if there are $k=2011$ boxes, we can guarantee that such kind of partitioning. But is that minimum? The problem asks you to minimize $k$.

I will prove $k > 44$. Let all pockets be monochrome. Let $p_1, p_2, \dots , p_{45}$ have color $c_1$. Similarly, $p_{46}, p_{47}, \dots , p_{90}$ have color $c_2$. $\vdots$ And, $p_{1981}, p_{1982}, \dots, p_{2012}$ have color $c_{45}$. If you want to satisfy the condition $i$, you should put all pockets with color $c_i$ into $k_i$. So there should be $45$ boxes. If you want to satisfy the condition $ii$, you should put each pocket with color $c_i$ into a separate box. So there should be $45$ boxes. So $k > 44$. But I didn't prove that $k=45$.

The answer is 62. We can assume no pocket has two same color ball. It does not change the problem at all. We will use induction, assume the answer is k for k(k+1)/2 ≤ n < (k+1)(k+2)/2. Let 1,2,…,s be different colors. Let a1,a2,…,as be number of balls of different colors. Assume a1≥a2≥…≥as If a pocket has color-p ball, we will say this pocket is type-p.(A type-p pocket can also type-q.) If a1 ≥ k + 1 we will put type-1 pockets into same box. Now we have (k+1)(k+2)/2 – a1 ≤ (k)(k+1)/2 and by induction we can put the other pockets into k-1 boxes. So assume a1 < k + 1. Put all type-1 pockets in different boxes. Now start to put remaining type-2 pockets with (ii) statement. If we cannot put all type-2 pockets, this means a2≥a1. Because if we cant add type-2 to a box, it means existing type-1 is also type-2, it means every box has color-2 ball. So we conclude we can place all type-2 pockets. Same strategy for type-3,…,type-m and we are done. The example for 62: a1 = 63, a2 = 62, … a59 = 5, a60 = 3, a61 = 2, a62 = 1. (All pockets contain only one ball) Proof: Assume we can place pockets into 61 boxes. We have 63 type-1 pocket by pigeonhole principle we have 2 type-1 pocket in the same box. This box cannot contain another type pocket. After that we have 60 boxes and 62 type-2 pockets. Similarly we can find another box which only has type-2… We need at least 62 boxes, contradiction.

From what I understand, the conditions i) and ii) are exclusive, meaning either all boxes must obey i), or else all boxes must obey ii) (not that each box most obey one of i) or ii)). Then the above does not work when assuming $a_1\geq k+1$, since after putting all type-$1$ pockets into a same box we are forced into a type i) situation, and the following attempt at induction does not guarantee the induction step provide the situation i); it might as well be ii). The following example should make it clearer. Say $1007$ pockets contain each one ball of colour $a$, and each of the remaining $1006$ pockets contains one ball, of colours different from $a$ and different among themselves. Try to put them in $1006$ boxes. By pigeonhole principle one box will contain two pockets with ball colour $a$, so situation ii) is excluded. To save boxes for situation i), put all $1007$ pockets containing balls of colour $a$ into one box; but the the remaining $1005$ boxes cannot accomodate the remaining $1006$ pockets.

I think (i) and (ii) are not exclusive, if you have 4 pocket like this: (a,b),(a),(a),(b). Then you can put (a,b) and (a) into same box (i). After that you can use (ii) to put the other (a) and (b) into same box.

That is a matter of interpretation, and not the way xeroxia seems to have understood it. Best is if someone could provide an accurate translation of the original problem.

A friend of mine wrote 62 as answer and got point(s) for that. I'm pretty sure the answer is 62.

This is the Turkish version: Quote: İçlerinde çeşitli renklerde toplar bulunan $2012$ torbayı $k$ kutuya herhangi bir kutudaki (for any box) tüm torbalar aynı renkte bir top içerecek veya (or) herhangi bir kutudaki (for any box) her torba, bu kutudaki diğer torbalardan hiçbirinin içermediği renkte bir top içerecek biçimde yerleştirmek istiyoruz. Torbalardaki topların sayıları ve renkleri ne olursa olsun, böyle bir yerleştirmeyi olanaklı kılan en küçük $k$ sayısını belirleyiniz. If the expression "for any box" is repeated in each sentence, i think the "or" should be interpretted as either. Otherwise, it should be Quote: İçlerinde çeşitli renklerde toplar bulunan $2012$ torbayı $k$ kutuya, herhangi bir kutudaki (for any box) tüm torbalar aynı renkte bir top içerecek veya (or) her torba, bu kutudaki diğer torbalardan hiçbirinin içermediği renkte bir top içerecek biçimde yerleştirmek istiyoruz. Torbalardaki topların sayıları ve renkleri ne olursa olsun, böyle bir yerleştirmeyi olanaklı kılan en küçük $k$ sayısını belirleyiniz. And that would be the English version: crazyfehmy wrote: We want to place $2012$ pockets, including variously colored balls, into $k$ boxes such that for any box, i) all pockets in this box must include a ball with the same color or ii)all pockets in this box must include a ball having a color which is not included in any other pocket in this box Find the smallest value of $k$ for which we can always do this placement whatever the number of balls in the pockets and whatever the colors of balls. I think, you understand what I mean. Also I have formulated the "either" version as: Quote: Thinking pockets as sets ($p$), colors as elements ($c$), and boxes as sets of sets ($b$) $p_i = \{c_{i1}, c_{i2}, \dots \}$ $b_i = \{p_{i1}, p_{i2}, \dots \}$ The problems asks for the least $k$ such that $b_1 \cup b_2 \cup \dots \cup b_k = \{p_1, p_2, \dots, p_{2012}\}$ where $b_i \cap b_j = \emptyset$, for any $i \neq j$. and all $b_i$s (all together) should satisfy one of the statements below: - For each $i$, and each $j\neq k$ where $p_j \in b_i$ and $p_k\in b_i$, it should be that $p_j\cap p_k \neq \emptyset$ - For each $i$, and each $j$ where $p_j \in b_i$, it should be that $p_j - \bigcup\limits_{p\in (b_i-p_j)}^{}p \neq \emptyset$ If "fmcpro" were right, I think the proposer would have been stated the problem wrongly. PS: Also, this is the result table of the exam (The contestants are 8th grade students ): http://www.tubitak.gov.tr/sites/default/files/ilkogretim_mateamatik_ikinciasama_puantablosu_2012.pdf The maximum score is 4 out of 7.

Now i see what you mean. Thank you for clearing that for me.

This is the official translation of the problem. Could a moderator replace the first post with the problem below: Find the smallest value of $k$ for which $2012$ bags each containing finite number of colored balls no matter how the contents of bags are arranged can be distributed into $k$ boxes so that for each box at least one of the following two conditions is held: $i.$ all bags of a box contain a ball of the same color $ii.$ each bag of a box contains a ball colored differently from all balls of all other bags of this box.