# Number bag riddle — minimal solution?

### The riddle:

Consider $N$ different bags $B_1$ to $B_N$. Each bag may be filled with numbers. Can you fill these bags with numbers from $1$ to $N$ so that the following conditions hold?

• 1) $n \in B_n$ (The $n$-th bag contains $n$.)
• 2) $B_i \cap B_j \neq \{\}$ (All bags must share numbers.)
• 3) Each number is element of the same number of bags.
• 4) $|B_i| = |B_j|$ (All bags have the same size)

### (Weak): Obvious solution

You could just fill all bags $B_1$ to $B_N$ with all numbers from $1$ to $N$.

So, assuming $N = 6$:

$$B_1 = (1, 2, 3, 4, 5, 6)$$ $$B_2 = (1, 2, 3, 4, 5, 6)$$ $$B_3 = (1, 2, 3, 4, 5, 6)$$ $$B_4 = (1, 2, 3, 4, 5, 6)$$ $$B_5 = (1, 2, 3, 4, 5, 6)$$ $$B_6 = (1, 2, 3, 4, 5, 6)$$

Complexity: $N$ numbers per bag.

### (Easy) Cyclic solution

Fill every bag with the next $N - 1$ numbers (with each number modulo $N + 1$).

I'll demonstrate the general idea with $N = 6$:

$$B_1 = (1, 2, 3, 4, 5)$$ $$B_2 = (2, 3, 4, 5, 6)$$ $$B_3 = (3, 4, 5, 6, 1)$$ $$B_4 = (4, 5, 6, 1, 2)$$ $$B_5 = (5, 6, 1, 2, 3)$$ $$B_6 = (6, 1, 2, 3, 4)$$

Complexity: $N - 1$ numbers per bag.

### (Medium) Short cyclic solution

Fill every bag with the next $\lfloor \frac{N}{2} \rfloor + 1$ numbers (with each number modulo $N + 1$).

I'll demonstrate the general idea with $N = 6$:

$$B_1 = (1, 2, 3, 4)$$ $$B_2 = (2, 3, 4, 5)$$ $$B_3 = (3, 4, 5, 6)$$ $$B_4 = (4, 5, 6, 1)$$ $$B_5 = (5, 6, 1, 2)$$ $$B_6 = (6, 1, 2, 3)$$

Complexity: $\lfloor \frac{N}{2} \rfloor + 1$ numbers per bag.

### (Hard) Minimal solution?

Is there a way to determine a minimal solution to this problem?

A minimal solution is a solution for which the number of elements per bag is minimal.

• @MichaelChirico No, a bag size of $\lfloor \frac{N}{2} \rfloor + 1$ is not minimal; consider $N = 7$.Then $\lfloor \frac{N}{2} \rfloor + 1 = 4$, but one minimal solution would be $(\{1, 2, 3\}, \{2, 4, 6\}, \{3, 5, 6\}, \{1, 4, 5\}, \{2, 5, 7\}, \{1, 6, 7\}, \{3, 4, 7\})$. – chiru Feb 8 '16 at 0:17
• how come (3) implicites all bags are equi-sized ? isnt {123},{243},{1234},{14} a solution ? – Abr001am Feb 9 '16 at 19:25
• @Idle001 That's indeed true. I've added (4) so we have a simple way to speak of a "minimum", invalidating your tuple. – chiru Feb 9 '16 at 23:53

$$B_1 = \{1,2\}, B_2=\{1,2\},$$ and all $i \in [N]\setminus \{1,2\},$
$$B_i = \{i\} \cup \{1\}.$$ To show this is a minimal solution, you must show that that you cannot satisfy the four logical constraints where each bag's size is 1 unless $N = 1.$ This particular proof should be rather trivial given the fact that there must be a non-empty intersection between all pairs of sets (and so each set must share something with any other set). Hence $B_1 \cap B_2 \neq \emptyset.$ This either implies that $2 \in B_1 \cap B_2 \vee 1 \in B_1 \cap B_2.$ In the former case, this implies that because $1 \in B_1 \wedge 2 \in B_2 \implies |B_1| \geq 2,$ which contradicts $|B_1| = 1.$ The other case proves a similar contradiction for $B_2.$
• This setup contradicts $(3)$, since $\forall i \in [N]: 1 \in B_i$, but $\not \forall i \in [N]: i \in B_i$. – chiru Feb 10 '16 at 3:05