Tất cả các cặp đấu có thể có để bạn không nhận được cặp nào từ cùng một nhóm.
Tôi đã suy nghĩ về vấn đề này một lúc, nhưng tôi không biết làm thế nào để tiếp cận nó.
Bạn có 8 nhóm, với 4 trong số các nhóm có 6 người và phần còn lại của 4 nhóm có 3 người. Vậy tổng cộng bạn có 36 người.
Bây giờ chúng tôi muốn chọn 18 cặp từ 36 người để tạo thành một giải đấu.
Tôi tin rằng có $\frac{36!}{18! 2^{18}}$(Tôi thực sự không hiểu làm thế nào để có được con số này) như có thể thấy ở đây: Số cách bạn có thể tạo thành cặp với một nhóm người khi một số người nhất định không thể được ghép nối với nhau.
Bây giờ, tôi muốn các cặp sao cho không có người nào trong cùng một nhóm đấu với nhau. Có bao nhiêu cặp có thể tồn tại dưới ràng buộc này?
Đây là một câu hỏi rất giống nhau: bốc thăm tứ kết UEFA Champions League 2018 - ghép các đội cùng quốc gia
Tuy nhiên, tôi không nghĩ rằng cách tiếp cận ở đó sẽ hiệu quả.
Cảm ơn!
CHỈNH SỬA: Dạng tổng quát nhất của câu hỏi này là để cho số nhóm và số người trong mỗi nhóm khác nhau, và tìm công thức cho điều này. Bây giờ tôi đang tự hỏi nếu một công thức như vậy tồn tại. Vì vậy, ví dụ, điều gì sẽ xảy ra nếu bạn có 11 nhóm, và 4 trong số họ có 5 người, 5 trong số họ có 4 người và 2 trong số họ có 12 người.
BIÊN TẬP:
Tôi đã chạy một số mô phỏng, tôi tiếp tục nhận được khoảng 0,11 thay vì 0,245 của Henry. Đây là mã của tôi.
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
Và một số kết quả tôi nhận được:
Đối với 3 nhóm 4 người, 2 người và 2 người, tôi nhận được 24 trên 105
Cho 3 nhóm 3 người, 3 người và 2 người, tôi nhận được 36 trên 105
Cho 5 nhóm gồm 2 người, 2 người, 2 người, 1 người và 1 người, tôi lấy 68 trên 105.
Trả lời
Số là 24855678464505984000.
Giả sử chúng ta có $k$ các nhóm khác nhau, có kích thước $N_1, N_2 ... N_k$. Định nghĩa$F(N_1, N_2, ... N_k)$là số lượng các giải đấu có thể. Vì vậy, câu trả lời cho vấn đề cụ thể của bạn là$F(3, 3, 3, 3, 6, 6, 6, 6)$.
Cách tính toán $F$? Chúng tôi có thể đưa ra một quan hệ lặp lại và hy vọng rằng một máy tính sẽ tính toán được nó. Đây là mối quan hệ lặp lại:
$$ 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) $$
Ý tưởng là chúng ta chọn một cặp (từ các nhóm khác nhau), sau đó tìm ra vấn đề con với cặp đó bị loại bỏ. Nhân tố$2 / \sum_l N_l$ xuất phát từ thực tế là chúng ta có thể chọn bất kỳ cặp nào làm cặp đầu tiên, dẫn đến việc đếm quá nhiều mà không chia cho số cặp.
Đối với các trường hợp cơ sở, chúng tôi có $F(0, 0, \dots 0) = 1$và $F=0$ nếu bất kỳ đối số nào của nó là 0.
Tôi đã sử dụng mã sau, mất khoảng một phút để chạy.
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))
Điều này in ra 24855678464505984000. Điều đó có nghĩa là xác suất tìm thấy một giải đấu thành công (có nghĩa là không có cặp nào từ cùng một nhóm) bằng cách lấy mẫu ngẫu nhiên từ tất cả các cặp có thể là khoảng 0,11, như dự kiến.