Fix $k\ge5$. For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$. We would like this labelling to satisfy the following property: there is a set $S$ of integers, s.t.
- If $k$ subsets of size $n/k$ don't intersect (i.e. the union of these sets form all the set $\{1..n\}$), then the sum of their labels is in $S$.
- Otherwise, the sum of their labels isn't in $S$.
Does there exist a $k\ge5$ and a labelling, s.t. $T\cdot|S|=O(1.99^n)$?
For example, for any $k$ we can label subsets in the following way. $T=2^n$, each subset has $n$ bits in their number: first bit is equal $1$ iff the subset contains $1$, the second bit is equal $1$ iff the subset contains $2$ e.t.c. It's easy to see, that $S$ contains only one element $2^n-1$. But here $T\cdot|S|=\Theta(2^n)$. Can we do it better?