Estoy investigando sobre el sentido del olfato y tengo un problema de combinatoria: Tengo 128 olores diferentes (n) y los mezclo en mezclas de 10 (r). Hay 2,26846154e+14 mezclas diferentes. Lo que quiero saber es Cuál es el tamaño del grupo de mezclas tal que ninguna mezcla del grupo comparta más de 5 (k) olores con cualquier otra mezcla del grupo. Espero que esto tenga sentido. Agradezco mucho vuestra ayuda.
Respuesta
¿Demasiados anuncios?
azimut
Puntos
13457
En primer lugar, este tipo de preguntas son muy difíciles de responder con exactitud, sobre todo si el conjunto de posibilidades es tan enorme como en su caso. Sin embargo, existe un método estándar para obtener un límite superior del tamaño máximo. Lo calcularé en esta respuesta.
Su pregunta puede reformularse: ¿Cuál es el tamaño máximo de un conjunto $X$ de mezclas, tal que cada conjunto de $6$ olores está contenida como máximo en una mezcla en $X$ ?
Contamos dos veces el conjunto $Y$ de pares $(T,B)$ donde $T$ es un conjunto de $6$ olores, y $B\in X$ .
Existen $\binom{128}{6}$ posibilidades de $T$ y cada $T$ está contenida como máximo en una $B$ . Así que $\#Y \leq \binom{128}{6}$ . Por otra parte, existen $\#X$ posibilidades de $B$ y cada $B$ contiene $\binom{10}{6}$ elementos $T$ . Así que $\#Y = \#X\cdot\binom{10}{6}$ .
El resultado es $$ \#X \leq \frac{\binom{128}{6}}{\binom{10}{6}} \approx 1080219781813,33$$ por lo que su grupo de mezclas no puede contener más de $1080219781813$ mezclas.
