• Registro
Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






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

+1 voto

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.

preguntado por EliasMochan (7,700 puntos) Abr 18 en Preguntas
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.

1 Respuesta

+2 votos
 
Mejor respuesta

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

respondido por Yarza (3,380 puntos) May 10
seleccionada por EliasMochan May 11
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...