Todos los emparejamientos de torneos posibles de manera que no obtengas pareja del mismo grupo.

Jan 03 2021

Pensé en este problema por un tiempo, pero no tengo idea de cómo abordarlo.

Tienes 8 grupos, 4 de los grupos tienen 6 personas y el resto de los 4 grupos tienen 3 personas. Entonces tienes 36 personas en total.

Ahora queremos elegir 18 parejas de 36 personas para formar un torneo.

Creo que hay $\frac{36!}{18! 2^{18}}$(Aunque realmente no entiendo cómo obtener este número) como se puede ver aquí: Número de formas en que puede formar parejas con un grupo de personas cuando ciertas personas no pueden emparejarse entre sí.

Ahora, quiero que los emparejamientos sean tales que ninguna persona del mismo grupo juegue entre sí. ¿Cuántos emparejamientos posibles existen bajo esta restricción?

Esta es una pregunta muy similar: sorteo de los cuartos de final de la UEFA Champions League 2018 - emparejamiento de equipos del mismo país

Sin embargo, no creo que el enfoque funcione.

¡Gracias!

EDITAR: La forma más general de esta pregunta sería dejar que el número de grupos y el número de personas en cada grupo varíe, y encontrar la fórmula para esto. Ahora me pregunto si existe tal fórmula. Entonces, por ejemplo, ¿qué pasa si tienes 11 grupos y 4 de ellos tienen 5 personas, 5 de ellos tienen 4 personas y 2 de ellos tienen 12 personas?

EDITAR:

Ejecuté una simulación, sigo obteniendo alrededor de 0.11 en lugar de 0.245 de Henry. Aquí está mi código.

team_list = c(rep(1:6, 4), rep(1:3,4))

for (i in 1:6){
  team_list[i] = paste("A", team_list[i], sep = "")
}

for (i in 7:12){
  team_list[i] = paste("B", team_list[i], sep = "")
}

for (i in 13:18){
  team_list[i] = paste("C", team_list[i], sep = "")
}

for (i in 19:24){
  team_list[i] = paste("D", team_list[i], sep = "")
}

for (i in 25:27){
  team_list[i] = paste("E", team_list[i], sep = "")
}

for (i in 28:30){
  team_list[i] = paste("F", team_list[i], sep = "")
}

for (i in 31:33){
  team_list[i] = paste("G", team_list[i], sep = "")
}

for (i in 34:36){
  team_list[i] = paste("H", team_list[i], sep = "")
}



check_pair = function(x){
  for (i in seq(from = 1, to = length(x), by = 2)){
    if (substr(x[i],1,1) == substr(x[i+1],1,1)){
      return (TRUE)
    }
  }
  return (FALSE)
}


count = 0

for (i in 1:10000){
  x = sample(team_list, size = 36)
  if (!check_pair(x)){
    count = count+1
  }
}

count/10000





team_list = c("A1", "A2", "B1", "B2", "C1", "C2")

pair_combn <- function(x) {
  Filter(function(e) all(unique(x) %in% unlist(e)),
         combn(as.data.frame(combn(x, 2)),
               length(x)/2, simplify = FALSE))
}

pair_combn(team_list)


check_pair = function(x){
  for (i in seq(from = 1, to = length(x), by = 2)){
    if (substr(x[i],1,1) == substr(x[i+1],1,1)){
      return (TRUE)
    }
  }
  return (FALSE)
}


count = 0

for (i in 1:10000){
  x = sample(team_list, size = 6)
  if (!check_pair(x)){
    count = count+1
  }
}

count/10000

team_list = c("A1", "A2", "B1", "B2", "C1", "D1")

pair_combn <- function(x) {
  Filter(function(e) all(unique(x) %in% unlist(e)),
         combn(as.data.frame(combn(x, 2)),
               length(x)/2, simplify = FALSE))
}

pair_combn(team_list)


check_pair = function(x){
  for (i in seq(from = 1, to = length(x), by = 2)){
    if (substr(x[i],1,1) == substr(x[i+1],1,1)){
      return (TRUE)
    }
  }
  return (FALSE)
}


count = 0

for (i in 1:10000){
  x = sample(team_list, size = 6)
  if (!check_pair(x)){
    count = count+1
  }
}

count/10000


z = pair_combn(team_list)




team_list = c("A1", "A2", "B1", "B2", "C1", "D1", "E1", "E2")

pair_combn <- function(x) {
  Filter(function(e) all(unique(x) %in% unlist(e)),
         combn(as.data.frame(combn(x, 2)),
               length(x)/2, simplify = FALSE))
}

combination = pair_combn(team_list)


check_pair = function(x){
  for (i in seq(from = 1, to = length(x), by = 2)){
    if (substr(x[i],1,1) == substr(x[i+1],1,1)){
      return (TRUE)
    }
  }
  return (FALSE)
}

count = 0
for (i in 1:105){
  to_check = as.vector(unlist(combination[[i]]))
  if (!check_pair(to_check)){
    count = count+1
  }
}

print (count)


count = 0

for (i in 1:10000){
  x = sample(team_list, size = 8)
  if (!check_pair(x)){
    count = count+1
  }
}

count/10000



team_list = c("A1", "A2", "A3", "A4", "B1", "B2", "C1", "C2")

pair_combn <- function(x) {
  Filter(function(e) all(unique(x) %in% unlist(e)),
         combn(as.data.frame(combn(x, 2)),
               length(x)/2, simplify = FALSE))
}

combination = pair_combn(team_list)


check_pair = function(x){
  for (i in seq(from = 1, to = length(x), by = 2)){
    if (substr(x[i],1,1) == substr(x[i+1],1,1)){
      return (TRUE)
    }
  }
  return (FALSE)
}

count = 0
for (i in 1:105){
  to_check = as.vector(unlist(combination[[i]]))
  if (!check_pair(to_check)){
    count = count+1
  }
}

print (count)


count = 0

for (i in 1:10000){
  x = sample(team_list, size = 8)
  if (!check_pair(x)){
    count = count+1
  }
}

count/10000



team_list = c("A1", "A2", "A3", "B1", "B2", "B3", "C1", "C2")

pair_combn <- function(x) {
  Filter(function(e) all(unique(x) %in% unlist(e)),
         combn(as.data.frame(combn(x, 2)),
               length(x)/2, simplify = FALSE))
}

combination = pair_combn(team_list)


check_pair = function(x){
  for (i in seq(from = 1, to = length(x), by = 2)){
    if (substr(x[i],1,1) == substr(x[i+1],1,1)){
      return (TRUE)
    }
  }
  return (FALSE)
}

count = 0
for (i in 1:105){
  to_check = as.vector(unlist(combination[[i]]))
  if (!check_pair(to_check)){
    count = count+1
  }
}

print (count)


count = 0

for (i in 1:10000){
  x = sample(team_list, size = 8)
  if (!check_pair(x)){
    count = count+1
  }
}

count/10000

Y algunos resultados obtengo:

Para 3 grupos de 4 personas, 2 personas y 2 personas, obtengo 24 de 105

Para 3 grupos de 3 personas, 3 personas y 2 personas, obtengo 36 de 105

Para 5 grupos de 2 personas, 2 personas, 2 personas, 1 persona y 1 persona, obtengo 68 de 105.

Respuestas

2 RickyTensor Jan 05 2021 at 12:47

El número es 24855678464505984000.

Supongamos que tenemos $k$ diferentes grupos, de tamaños $N_1, N_2 ... N_k$. Definir$F(N_1, N_2, ... N_k)$para ser el número de torneos posibles. Entonces la respuesta a su problema particular es$F(3, 3, 3, 3, 6, 6, 6, 6)$.

Cómo calcular $F$? Podemos llegar a una relación de recurrencia y, con suerte, una computadora debería calcularla. Aquí está la relación de recurrencia:

$$ F(N_1...N_k) = \frac{2}{\sum_l N_l}\sum_i\sum_{j < i} N_j \times N_i \times F(N_1, N_2\dots N_j-1 \dots N_i-1 \dots N_k) $$

La idea es que elegimos un par (de diferentes grupos), luego averiguamos el subproblema con ese par eliminado. El factor$2 / \sum_l N_l$ viene del hecho de que podemos elegir cualquiera de los pares para que sea el primero, lo que llevaría a contar en exceso sin dividir por el número de pares.

Para los casos base, tenemos $F(0, 0, \dots 0) = 1$y $F=0$ si alguno de sus argumentos es 0.

Usé el siguiente código, que tarda aproximadamente un minuto en ejecutarse.

from functools import lru_cache

@lru_cache(maxsize = 1000000)
def F(M, ntup, k):
    if M < 0: return 0
    for n in ntup:
        if n < 0: return 0
    if M == 0:
        return 1
    ans = 0
    for i in range(1, k):
        for j in range(0, i):
            ans += ntup[i] * ntup[j] * F(M-2, ntup[:j] + (ntup[j]-1,) + ntup[j+1:i] + (ntup[i]-1,) + (ntup[i+1:] if i+1 < k else ()), k)
    return (2 * ans) // M

print(F(36, (3, 3, 3, 3, 6, 6, 6, 6), 8))

Esto imprime 24855678464505984000. Eso significa que la probabilidad de encontrar un torneo exitoso (es decir, que no haya pares del mismo grupo) mediante un muestreo aleatorio de todos los emparejamientos posibles es de aproximadamente 0.11, como se esperaba.