Todos os pares de torneios possíveis de forma que você não obtenha nenhum par do mesmo grupo.

Jan 03 2021

Pensei um pouco nesse problema, mas não tenho ideia de como abordá-lo.

Você tem 8 grupos, com 4 dos grupos tendo 6 pessoas e o resto dos 4 grupos tendo 3 pessoas. Portanto, você tem 36 pessoas no total.

Agora queremos escolher 18 pares de 36 pessoas para formar um torneio.

Eu acredito que tem $\frac{36!}{18! 2^{18}}$(Eu realmente não entendo como obter este número) como pode ser visto aqui: Número de maneiras pelas quais você pode formar pares com um grupo de pessoas quando certas pessoas não podem ser emparelhadas entre si.

Agora, eu quero que os pares sejam tais que nenhuma pessoa do mesmo grupo jogue uma contra a outra. Quantos pares possíveis existem sob esta restrição?

Esta é uma questão muito semelhante: empate nas quartas de final da UEFA Champions League de 2018 - emparelhamento de times do mesmo país

No entanto, não acho que essa abordagem funcionaria.

Obrigado!

EDITAR: A forma mais geral desta pergunta seria deixar o número de grupos e o número de pessoas em cada grupo variar e encontrar a fórmula para isso. Agora estou me perguntando se essa fórmula existe. Então, por exemplo, e se você tiver 11 grupos e 4 deles tiverem 5 pessoas, 5 deles tiverem 4 pessoas e 2 deles tiverem 12 pessoas.

EDITAR:

Fiz algumas simulações, continuo obtendo cerca de 0,11 em vez dos 0,245 de Henry. Aqui está meu 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

E alguns resultados que obtenho:

Para 3 grupos de 4 pessoas, 2 pessoas e 2 pessoas, recebo 24 de 105

Para 3 grupos de 3 pessoas, 3 pessoas e 2 pessoas, recebo 36 de 105

Para 5 grupos de 2 pessoas, 2 pessoas, 2 pessoas, 1 pessoa e 1 pessoa, recebo 68 de 105.

Respostas

2 RickyTensor Jan 05 2021 at 12:47

O número é 24855678464505984000.

Suponha que temos $k$ grupos diferentes, de tamanhos $N_1, N_2 ... N_k$. Definir$F(N_1, N_2, ... N_k)$para ser o número de torneios possíveis. Portanto, a resposta para o seu problema específico é$F(3, 3, 3, 3, 6, 6, 6, 6)$.

Como calcular $F$? Podemos criar uma relação de recorrência e, com sorte, um computador deve computá-la. Aqui está a relação de recorrência:

$$ 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) $$

A ideia é escolhermos um par (de grupos diferentes) e, em seguida, descobrirmos o subproblema com esse par removido. O fator$2 / \sum_l N_l$ vem do fato de que podemos escolher qualquer um dos pares para ser o primeiro, o que levaria a uma contagem excessiva sem dividir pelo número de pares.

Para os casos básicos, temos $F(0, 0, \dots 0) = 1$, e $F=0$ se algum de seus argumentos for 0.

Usei o código a seguir, que leva cerca de um minuto para ser executado.

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))

Isso imprime 24855678464505984000. Isso significa que a probabilidade de encontrar um torneio bem-sucedido (ou seja, nenhum par do mesmo grupo) por amostragem aleatória de todos os pares possíveis é de cerca de 0,11, como esperado.