Number bag riddle — minimal solution?

Question

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.

Answer 1

My best recommendation would be to try to get each bag to contain 2 items where

$$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.$