4
$\begingroup$

I thought about this problem for a while, but I have no idea how to approach it.

You have 8 groups, with 4 of the groups having 6 people and rest of the 4 groups having 3 people. So you have 36 people in total.

Now we want to pick 18 pairs from 36 people to form a tournament.

I believe there are $\frac{36!}{18! 2^{18}}$(I don't really understand how to get this number though) as can be seen here: Number of ways you can form pairs with a group of people when certain people cannot be paired with each other.

Now, I want pairings to be such that no people from the same group play against each other. How many possible pairings exist under this constraint?

This is a very similar question: UEFA Champions League quarterfinals 2018 draw - pairing of same country teams

However, I don't think the approach there would work.

Thanks!

EDIT: The most general form of this question would be to let the number of groups and number of people in each group vary, and to find the formula for this. I am now wondering if such a formula exists. So for example, what if you have 11 groups, and 4 of them have 5 people, 5 of them have 4 people, and 2 of them have 12 people.

EDIT:

I ran some simulation, I keep getting about 0.11 instead of Henry's 0.245. Here is my code.

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

And some results I get:

For 3 group of 4 people, 2 people, and 2 people, I get 24 out of 105

For 3 group of 3 people, 3 people and 2 people, I get 36 out of 105

For 5 group of 2 people, 2 people, 2 people, 1 person and 1 person, I get 68 out of 105.

$\endgroup$
4
  • 2
    $\begingroup$ Your $\frac{36!}{18! 2^{18}}$ is just a way of writing $35 \times 33 \times \cdots \times 3 \times 1$ which might be seen to be "the first in the alphabet plays any of the other $35$, then the next unpaired in the alphabet plays any of the other $33$ unpaired, etc." $\endgroup$
    – Henry
    Jan 3, 2021 at 2:03
  • $\begingroup$ @Henry That makes sense, thanks! $\endgroup$
    – Phil
    Jan 3, 2021 at 2:15
  • $\begingroup$ Simulation suggests that the number meeting your constraint may be something like around $0.244$ or $0.245$ times the original number $\endgroup$
    – Henry
    Jan 3, 2021 at 2:25
  • 1
    $\begingroup$ @Henry, good to know thanks! I might run a few simulation with different numbers to see some pattern. $\endgroup$
    – Phil
    Jan 3, 2021 at 2:26

1 Answer 1

2
$\begingroup$

The number is 24855678464505984000.

Suppose we have $k$ different groups, of sizes $N_1, N_2 ... N_k$. Define $F(N_1, N_2, ... N_k)$ to be the number of possible tournaments. So the answer to your particular problem is $F(3, 3, 3, 3, 6, 6, 6, 6)$.

How to compute $F$? We can come up with a recurrence relation, and hopefully a computer should be compute it. Here's the recurrence relation:

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

The idea is that we choose a pair (from different groups), then figure out the subproblem with that pair removed. The factor $2 / \sum_l N_l$ comes from the fact that we can choose any of the pairs to be the first one, which would lead to over-counting without dividing by the number of pairs.

For the base cases, we have $F(0, 0, \dots 0) = 1$, and $F=0$ if any of its arguments are 0.

I used the following code, which takes about a minute to run.

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

This prints 24855678464505984000. That means the probability of finding a successful tournament (meaning no pairs from the same group) by randomly sampling from all possible pairings is about 0.11, as expected.

$\endgroup$
1
  • $\begingroup$ Oh my god,thanks so much! $\endgroup$
    – Phil
    Jan 5, 2021 at 16:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .