3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @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\})$. $\endgroup$ – chiru Feb 8 '16 at 0:17
  • $\begingroup$ how come (3) implicites all bags are equi-sized ? isnt {123},{243},{1234},{14} a solution ? $\endgroup$ – Abr001am Feb 9 '16 at 19:25
  • $\begingroup$ @Idle001 That's indeed true. I've added (4) so we have a simple way to speak of a "minimum", invalidating your tuple. $\endgroup$ – chiru Feb 9 '16 at 23:53
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This setup contradicts $(3)$, since $\forall i \in [N]: 1 \in B_i$, but $\not \forall i \in [N]: i \in B_i$. $\endgroup$ – chiru Feb 10 '16 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.