सभी संभावित टूर्नामेंट ऐसे जोड़े जाते हैं कि आपको एक ही समूह से कोई जोड़ी नहीं मिलती है।
मैंने कुछ समय के लिए इस समस्या के बारे में सोचा, लेकिन मुझे नहीं पता कि इसे कैसे अपनाया जाए।
आपके 8 समूह हैं, जिनमें से 4 समूह में 6 लोग हैं और शेष 4 समूह हैं जिनमें 3 लोग हैं। तो आपके पास कुल 36 लोग हैं।
अब हम एक टूर्नामेंट बनाने के लिए 36 लोगों में से 18 जोड़े चुनना चाहते हैं।
मेरा मानना है कि वहाँ हैं $\frac{36!}{18! 2^{18}}$(मुझे वास्तव में समझ में नहीं आता है कि इस संख्या को कैसे प्राप्त किया जा सकता है) जैसा कि यहाँ देखा जा सकता है: ऐसे तरीकों की संख्या जिनसे आप लोगों के समूह के साथ जोड़े बना सकते हैं जब कुछ लोगों को एक दूसरे के साथ जोड़ा नहीं जा सकता।
अब, मैं चाहता हूं कि जोड़ी ऐसी हो कि एक ही समूह के लोग एक-दूसरे के खिलाफ न खेलें। इस बाधा के तहत कितनी संभव जोड़ियाँ मौजूद हैं?
यह एक बहुत ही समान प्रश्न है: यूईएफए चैंपियंस लीग क्वार्टर फाइनल 2018 ड्रा - एक ही देश की टीमों की जोड़ी
हालाँकि, मुझे नहीं लगता कि वहाँ दृष्टिकोण काम करेगा।
धन्यवाद!
EDIT: इस प्रश्न का सबसे सामान्य रूप यह होगा कि प्रत्येक समूह के समूहों की संख्या और प्रत्येक समूह के लोगों की संख्या अलग-अलग हो, और इसके लिए सूत्र का पता लगाएं। मैं अब सोच रहा हूं कि क्या ऐसा कोई फार्मूला मौजूद है। उदाहरण के लिए, यदि आपके पास 11 समूह हैं, और उनमें से 4 में 5 लोग हैं, उनमें से 5 के पास 4 लोग हैं, और उनमें से 2 12 लोग हैं।
संपादित करें:
मैंने कुछ सिमुलेशन चलाए, मुझे हेनरी के 0.245 के बजाय 0.11 मिलते रहे। यहाँ मेरा कोड है
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
और कुछ परिणाम मुझे मिले:
4 लोगों के 3 समूह, 2 लोगों और 2 लोगों के लिए, मुझे 105 में से 24 मिलते हैं
3 लोगों के 3 समूह, 3 लोगों और 2 लोगों के लिए, मुझे 105 में से 36 मिलते हैं
2 लोगों के 5 समूह के लिए, 2 लोग, 2 लोग, 1 व्यक्ति और 1 व्यक्ति, मुझे 105 में से 68 मिलते हैं।
जवाब
संख्या 24855678464505984000 है।
मान लीजिए हमारे पास है $k$ विभिन्न समूहों, आकार में $N_1, N_2 ... N_k$। परिभाषित करें$F(N_1, N_2, ... N_k)$संभावित टूर्नामेंटों की संख्या होना। तो आपकी विशेष समस्या का जवाब है$F(3, 3, 3, 3, 6, 6, 6, 6)$।
गणना कैसे करें $F$? हम पुनरावृत्ति संबंध के साथ आ सकते हैं, और उम्मीद है कि कंप्यूटर को इसकी गणना करनी चाहिए। यहाँ पुनरावृत्ति संबंध है:
$$ 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) $$
विचार यह है कि हम एक जोड़ी चुनते हैं (विभिन्न समूहों से), फिर हटाए गए उस जोड़े के साथ उपप्रोमा का पता लगाएं। कारण$2 / \sum_l N_l$ इस तथ्य से आता है कि हम किसी भी जोड़े को पहले एक के रूप में चुन सकते हैं, जो जोड़े की संख्या से विभाजित किए बिना ओवर-काउंटिंग की ओर ले जाएगा।
आधार मामलों के लिए, हमारे पास है $F(0, 0, \dots 0) = 1$, तथा $F=0$ यदि इसका कोई तर्क 0 है।
मैंने निम्नलिखित कोड का उपयोग किया, जिसे चलाने में लगभग एक मिनट लगता है।
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))
यह 24855678464505984000000 प्रिंट करता है। इसका मतलब है कि सभी संभावित जोड़ियों से बेतरतीब ढंग से नमूना लेकर एक सफल टूर्नामेंट (एक ही समूह से कोई जोड़ नहीं) की संभावना लगभग 0.11 है।