2

We want to place $2012$ pockets, including variously colored balls, into $k$ boxes such that either

  • For all boxes, all pockets in a box must include a ball with the same color

or

  • For all boxes, all pockets in a box must include a ball having a color which is not included in any other pockets 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 will show that $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 first condition, you should put all pockets with color $c_i$ into $k_i$. So there should be $45$ boxes.

If you want to satisfy the second condition, 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 proved that $k=45$.

I think the problem is related with Dilworth's Lemma or something similar to it. 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.

Explanation:

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$, it should be that $\bigcap\limits_{p \in b_i}p \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$

user706071
  • 247
  • The interaction of "must" and "or" is confusing (to me). Is the intended meaning the one that would result by deleting both instances of "must"? If so, I think that change would make the question clearer. – joriki Mar 19 '13 at 08:38
  • The statement is really not clear at all. Does "any" mean "all" or "some"? Can pockets be empty? Can boxes remain empty? – Marc van Leeuwen Mar 19 '13 at 09:07
  • I have edited the question. The $k$ boxes will be formed according to either the first condition or the second condition. – user706071 Mar 19 '13 at 09:38
  • "all pockets in a box must include a ball with the same color" means $\bigcap_{p\in b_i} p\neq\emptyset$, but it's not what you wrote in your explanation section. So what do you really want ? – Xoff Nov 08 '13 at 13:54
  • The statement written in plain English is true. I have edited the mathematical notation. – user706071 Nov 10 '13 at 23:36

1 Answers1

1

I will show that $k\ge1006$. We note $c_i$ the color $i\in\mathbb N$ and if $i\neq j$, $c_i$ and $c_j$ are different colors.

Consider the 1006 pockets $p_i$ ($1\le i\le 1006$) such that $p_i$ contains only one ball of color $c_i$. Under the first condition, we need at least 1006 boxes for those pockets, because no boxes can contain two different $p_i$.

Consider the 1006 pockets $u_i$ ($1\le i\le 1006$) such that $u_i$ contains only $i$ balls of color $c_k$ for $1\le k\le i$. Under the second condition, we need at least 1006 boxes for those pockets, because no boxes can contain two different $u_i$.

Then the set $\{p_i\}\cup\{u_i\}$ (with 2012 pockets) needs at least 1006 boxes under both conditions.

In fact k=1006 (but I wait for your answer to my question)

Xoff
  • 10,310
  • The problem was taken from here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2875074&sid=64f42cd15b8e4083bf7bfae875e3d595#p2875074 – user706071 Feb 14 '15 at 17:31