¿Cuántos conjuntos de cardinalidad $k$ necesito para cubrir un conjunto de cardinalidad $n$ "bonito"?

Question

Sean $n$ y $k$ enteros positivos con $k<n$. Sea $A$ un conjunto de cardinalidad $n$. Decimos que una buena $k$-cubierta de $A$ es una colección de subconjuntos de $A$ todos con cardinalidad $k$ tales que todo $x$ en $A$ está en la misma cantidad de elementos de $\mathcal{B}$ y esta cantidad es mayor que 0.

Lo que quiero es calcular $f(n,k)$ definido como la mínima cardinalidad de una buena $k$-cubierta de un conjunto con cardinalidad $n$. Podemos notar que $f(n,k)\leq {{n}\choose{k}}$, pero quisiera calcular el valor exacto.

Comments

Si $k$ divide a $n$, $f(n,k)=n/k$, cierto?

---

Sí. También me interesa en cuántos conjuntos queda cada elemento de $A$ (1 si $k $ divide a $n$). Con cualquiera de los números se puede calcular el otro.

Answer 1

Supongamos que $\mathcal{B}$ es una buena $k$-cubierta de $A=\{a_0,\dots,a_{n-1}\}$. Dado que cada elemento de $A$ está en la misma cantidad de conjuntos en la colección $\mathcal{B}=\{B_1,\dots,B_m\}$, tenemos que $n$ divide a $|B_1|+\dots+|B_m|$. También, como cada conjunto tiene cardinalidad $k$, tenemos que $|B_1|+\dots+|B_m|=k|\mathcal{B}|$, de donde $n$ divide a $k|\mathcal{B}|$. Como esto es cierto para toda buena $k$-cubierta de $A$, en particular tenemos que $n$ divide a $f(n,k)k$. Como $f(n,k)k$ es múltiplo de $k$ y de $n$, entonces $f(n,k)k\geq$mcm$(n,k)$, de donde $f(n,k)\geq\frac{mcm(n,k)}{k}$.

Ahora, consideremos los conjuntos $B_j=\{a_{(j-1)k+1},\dots,a_{jk}\}$, donde las operaciones en cada subíndice son evaluadas mod $n$. Por ejemplo, $B_1=\{a_1,\dots,a_k\}$, $B_2=\{a_{k+1},\dots,a_{2k}\}$, etc. Analicemos las colecciones de conjuntos $\mathcal{B}_j=\{B_1,\dots,B_j\}$. Para cada $j$ se cumple lo siguiente:
 

1.- Los elementos $a_1,\dots,a_{jk}$ están cada uno en la misma cantidad, digamos $p$, de conjuntos en $\mathcal{B}_j$.

2.- El resto de los elementos de $A$ están cada uno en $p-1$ de los conjuntos en $\mathcal{B}_j$.

Claramente, todos los elementos de $A$ estarán en el mismo número de elementos de $\mathcal{B_j}$ si $jk$ es congruente con 0 mod $n$. En particular, si $j=\frac{mcm(n,k)}{k}$, $jk=mcm(n,k)$, y entonces $\mathcal{B_j}$ es una buena $k$-cubierta de $A$. En conclusión, $f(n,k)\leq\frac{mcm(n,k)}{k}$.

En conclusión, $f(n,k)=\frac{mcm(n,k)}{k}$.