Combinations Question about the construction of some special sets [closed]

Question

Let $n$ and $k$ be two given numbers. The goal is to choose $n$ subsets from $\{1,2,...,n\}$ such that the union of any $k$ of these subsets is the set $\{1,2,...,n\}$ and the union of any $m < k$ of these subsets is not the entire set $\{1,2,...,n\}$.

If $n$ and $k$ are given numbers, then how many ways are there to choose $n$ subsets from $\{1,2,...,n\}$ satisfying the given conditions?

For example, if $n=3$ and $k=2$, there is only one case $(\{1,2\} , \{2,3\} , \{3,1\})$ to choose three subsets from $\{1,2,3\}$ such that every two of these subsets construct $\{1,2,3\}$ and every one of these subsets do not construct the set $\{1,2,3\}$.

It is a kind of secret sharing in the cryptography that we want to distribute $n$ key between $n$ people such that at least we need $k$ people to decrypt.

Answer 1

Suppose that $\mathscr{F} := \lbrace F_1, \ldots, F_m\rbrace$ is a family of subsets of $X := \lbrace 1, 2, \ldots, n\rbrace$ with the property that the union of any $k$ members of $\mathscr{F}$ is all of $X$ but the union of any $k-1$ members of $\mathscr{F}$ is not all of $X$.

Consider the $m\times n$ 0-1 matrix $M$ whose columns are indexed by the elements of $X$ and whose rows are indexed by members of $\mathscr{F}$ and whose $(i,j)$th entry $M_{i,j}$ is 1 if and only if $j\in F_i$. Then every column has at most $k-1$ zeros, or else taking the union of the $F_i$ corresponding to the zeros in that column would fail to be all of $X$. Similarly, given any $k-1$ rows, there must be a column with zeros in precisely those $k-1$ rows, or else the union of the corresponding $F_i$ would be all of $X$. Thus the only way to construct a matrix with the desired property is to construct one column for each of the $m \choose k-1$ ways to put zeros, and then repeat some columns. In particular, $n\ge {m\choose k-1}$.

You want $m=n$. The only way to achieve $n\ge {m\choose k-1}$ when $m=n$ is if $k=1$, $k=2$, $k=n$, or $k=n+1$. Even if you allow $\mathscr{F}$ to have repeated elements, the case $k=1$ produces only the trivial example in which every $F_i = X$. The case $k=n+1$ does not produce any solutions. The case $k=2$ produces the unique solution that you have already described. Finally, the case $k=n$ produces the unique solution in which each $F_i$ is a distinct singleton set.