Aynı gruptan hiçbir çift alamayacağınız tüm olası turnuva eşleşmeleri.
Bir süre bu problemi düşündüm ama nasıl yaklaşacağımı bilmiyorum.
8 grubunuz var, 4 grubun 6 kişi, 4 grubun geri kalanı 3 kişi. Yani toplamda 36 kişiniz var.
Şimdi bir turnuva oluşturmak için 36 kişiden 18 çift seçmek istiyoruz.
Olduğuna inanıyorum $\frac{36!}{18! 2^{18}}$(Gerçi bu sayıyı nasıl elde edeceğimi gerçekten anlamıyorum) burada görülebileceği gibi: Bazı insanlar birbirleriyle eşleştirilemediğinde bir grup insanla çift oluşturmanın yollarının sayısı.
Şimdi, eşleşmelerin aynı gruptan hiç kimsenin birbirine karşı oynamayacağı şekilde olmasını istiyorum. Bu kısıtlama altında kaç olası eşleşme vardır?
Bu çok benzer bir soru: 2018 UEFA Şampiyonlar Ligi çeyrek finalleri çekilişi - aynı ülke takımlarının eşleşmesi
Ancak, oradaki yaklaşımın işe yarayacağını sanmıyorum.
Teşekkürler!
DÜZENLEME: Bu sorunun en genel şekli, her gruptaki grup sayısı ve kişi sayısının değişmesine izin vermek ve bunun formülünü bulmak olacaktır. Şimdi böyle bir formülün var olup olmadığını merak ediyorum. Örneğin, 11 grubunuz varsa ve bunların 4'ünde 5 kişi, 5'inde 4 kişi ve 2'sinde 12 kişi varsa.
DÜZENLE:
Biraz simülasyon yaptım, Henry'nin 0.245'i yerine yaklaşık 0.11 alıyorum. İşte kodum.
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
Ve aldığım bazı sonuçlar:
4 kişilik, 2 kişilik ve 2 kişilik 3 grup için 105 kişiden 24'ünü alıyorum
3 kişilik, 3 kişilik ve 2 kişilik 3 grup için 105 kişiden 36'sını alıyorum
2 kişilik, 2 kişilik, 1 kişilik ve 1 kişilik 5 grup için 105 kişiden 68'ini alıyorum.
Yanıtlar
Numara 24855678464505984000'dir.
Varsayalım ki bizde $k$ farklı gruplar, boyutlar $N_1, N_2 ... N_k$. Tanımlamak$F(N_1, N_2, ... N_k)$olası turnuva sayısı olacak. Dolayısıyla, probleminizin cevabı şudur:$F(3, 3, 3, 3, 6, 6, 6, 6)$.
Nasıl hesaplanır $F$? Bir tekrarlama ilişkisi bulabiliriz ve umarım bir bilgisayar bunu hesaplamalı. İşte tekrarlama ilişkisi:
$$ 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) $$
Fikir, bir çift seçmemizdir (farklı gruplardan), sonra bu çifti kaldırarak alt problemi çözeriz. Faktör$2 / \sum_l N_l$ Çiftlerden herhangi birini ilk olarak seçebilmemizden gelir, bu da çiftlerin sayısına bölünmeden fazla saymaya yol açar.
Temel durumlar için bizde $F(0, 0, \dots 0) = 1$, ve $F=0$ argümanlarından herhangi biri 0 ise.
Çalıştırması yaklaşık bir dakika süren aşağıdaki kodu kullandım.
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))
Bu, 24855678464505984000'i yazdırır. Bu, tüm olası eşleşmelerden rastgele örnekleme yaparak başarılı bir turnuva (aynı gruptan hiçbir çift olmaması anlamına gelir) bulma olasılığının beklendiği gibi yaklaşık 0.11 olduğu anlamına gelir.