Birçoğundan İki Zar Yapmanın Tembel Bir Yolu

Son zamanlarda, bulmacanın üstüne tökezledi: Üçte İki Zar Yapın , aşağıdaki soruya bir çözüm bulmak ister:

Diyelim ki $ n $ ayırt edilemez zar atarım. Tamamen $ n $ sayılarını gösteren ve zarların sırası hakkında hiçbir bilgi göstermeyen, hangi algoritmayı kullanabilirim, sıralanmamış bir çift sayısının $ a $ ve $ b $ 'ı dağıtarak sıralanmamış çiftin dağılımı $ (a , b) $ iki sıralanmamış zar rulosunun dağılımı ile aynı mıdır?

Hiçbiri hatırlaması kolay görünen soru üzerine ortaya konan çözümleri okuduktan sonra soruyu matematikçi arkadaşlarım Cassandra'ya gönderdim. Daha şık bir strateji için aşağıdaki genel formu önerdi:

Belli ki birinden birinden ölmek istemeniz durumunda, $ 6 $ 'lık zarın toplamını alarak bunu yapabilirsiniz. Yani, eğer zar $ x_1, x_2, \ ldots, x_n $ olarak gelirse, onları bir değerde birleştirirsiniz.   $$ x_1 + x_2 + \ noktalar + x_n \ pmod6. $$   İki rulo almak için karmaşık bir şema benimsemek yerine, bu stratejiyi denemek ve kurtarmak bana daha mantıklı gelecektir. Özellikle, $ f $ ve $ g $ iki işlevini seçip, zarın $ x_1, x_2, \ ldots, x_n $ olarak gelmesi durumunda, iki ruloyu aşağıdaki gibi okuduğunuzu söyleyin:   $$ f (x_1) + f (x_2) + \ nokta + f (x_n) \ pmod6 $$   $$ g (x_1) + g (x_2) + \ nokta + g (x_n) \ pmod6. $$   Bunun yeterince büyük $ n $ ve biraz $ f $ ve $ g $ karşılığında mümkün olduğuna eminim.

Bu fikri sevdim, çünkü yalnızca bir alandaki ve altı element arasındaki iki fonksiyonu ezberlemek zorunda kalacaktı ve herhangi bir tahrifattan kaçınacaktı. Çalışmamı biraz kolaylaştırmak için, bunun yalnızca n $ 'lık için mümkün olup olmadığını düşünmeye karar verdim. Çok denemeden sonra, bu işlevleri bulamadım. Geri dönüp netleşmesini isteyebileceğime eminim, ama çok utanıyorum - bu yüzden hepinize soracağım: Cassandra'nın öngörüsü herhangi bir $ n için bile doğru olabilir mi?


Aşağıdaki birkaç cevap, soruyu amaçlanandan farklı şekilde yorumlayabildiği için, durumu resmi olarak yazmama izin verin: $ F = f (x_1) + \ ldots + f (x_n) \ pmod 6 $$ $$ G = g (x_1) + \ ldots + g (x_n) \ pmod 6. $$ $$ $ 'a uygun bir $ ve $ b $' a sahip olmak istiyoruz. $$ P (F = a \ text {ve} G = b) + P (F = b \ metin {ve} G = a) = \ frac {1} {18}. $$ $ P $ olan bir olayın gerçekleşmesi olasılığıdır. $ (F, G) $ 'in iki sıralanmamış zar rulosuyla aynı dağılıma sahip olduğunu söyleyerek kastedilen budur.

Bir ipucu olarak, amaçlanan çözümün sayma argümanı olmadığını ve olasılıkları dikkatlice incelemekle de ilgisi olmadığını söyleyeyim; doğada daha analitiktir.

10
"Tamamen üç rakam gösteriliyor ..." yazıyorsa, bu üç yerine $ n $ olmalı mı? Ya da belki, ilk cümlede, $ n $ yerine üç olmalı mı?
katma yazar hexomino, kaynak
@hexomino Buna dikkat çektiğiniz için teşekkürler; Her iki yerde de $ n $ olması düzeltildi.
katma yazar Milo Brandt, kaynak
Sorunun da burada olması gerektiğini düşünüyorum math.stackexchange.com
katma yazar Adit Kirtani, kaynak

8 cevap

$ F = f (x_1) +… + f (x_n) = x_1 $

 $ G = g (x_1) +… + g (x_n) = x_2 $

Kalıp tasarımla ayırt edilemez olduğundan, $ x_i $ rastgele bir ödevdir. Bulmacayı çerçevelemek için kullanılan OP ne olursa olsun ödevi kullanın. Formüller sorunu giderir. Bu sayma bir argüman değil ve olasılıkları çok dikkatli bir şekilde incelemiyor.

4
katma
F = x1 olarak ayarlanma izniniz yok. F'nin ne olduğunu, bununla birlikte F = f (x1) + ... + f (xn) F denklemini tanımlayan F'yi dolaylı olarak seçmelisiniz.
katma yazar Matt Obee, kaynak
Lütfen açıkla. Ve spoiler markdown kullanın.
katma yazar Silent-Bob, kaynak

[Bu cevap daha önce herhangi bir $ n $ 'lık, tek başına ya da hatta hiçbir şeyin yapılamayacağını kanıtladığını iddia etti, ancak ispatta en az iki büyük delik vardı. Aşağıdaki, bir gün ispat başlangıcında olabileceğinden daha fazla olmadığını iddia ediyor. Hala düşünüyorum.]

$ P = x ^ {f (1)} y ^ {g (1)} + \ cdots + x ^ {f (6)} y ^ {g (6)} $ yazın. Daha sonra $ i, $ n $ zar attıktan sonra $ i, j $ kazanma olasılığı $ x ^ iy ^ j $ $ (p/6) ^ n $ katsayısı ile verilir. Mod 6 toplamlarını azaltmak için mod $ (x ^ 6-1, y ^ 6-1) $ polinomlarında çalışmamız gerekir. Ve soru şu ki, $ p ^ n/6 ^ {n-2} = (1+ \ cdots + x ^ 5) (1+ \ cdots + y ^ 5) $ mod $ (x ^ 6 ayarını yapıp yapamayacağımızdır. -1, y ^ 6-1) $ veya, eşit olarak, $ p ^ n/6 ^ {n-2} = (1+ \ cdots + x ^ 5) (1+ \ cdots + y ^ 5) + ( 1-x ^ 6) a + (1-y ^ 6) b $, burada $ a, b $, polinomlardır.

... sırasız sonuç çiftlerine bakmamız gerekiyorsa, sonuçta istediğimiz, karşılık gelen bir şeyin $ p (x, y) ^ n $ için değil, $, p (x, y), ^ n + p (y, x) ^ n $. $ X = y $ koyarsak bu sadece $ 2p (x, x) ^ n $ olur.

$ X $ 'ın 1 dışındaki birliğin 6. kökü olduğunu varsayalım. O zaman açıkça RHS sıfırdır, yani LHS de öyle. Öyleyse $ p (x, x) ^ n = $ $ gibi her seçenek için 0 $; bu yüzden $ p (x, x) = 0 $ 'a her bir seçim için 0 $. Özellikle, $ \ omega ^ 6 = 1 $ olduğunda, $ (x- \ omega) $, $ p (x, x) $ 'nin bir faktörüdür ve bu nedenle, tüm bu faktörlerin, yani $ (x ^ 6' in ürünüdür. -1)/(x-1), 1 + \ cdots + x ^ 5 $ =.

Şimdi, tam olarak $ p (x, x) $ nedir? $ \ Sum x ^ {f (i) + g (i)} $; ve sadece f $ g, g $ mod 6 değerine dikkat ettiğimizi unutmayın. Yani bize söylenen şey, her bir kalıntı mod 6'nın $ f (i) + g (i) $ arasında bir kez göründüğü. Öyleyse $ p = \ sum x ^ i (y/x) ^ {h (i)} $ yazıp üslupları mod 6 olan normal uyarılarla yazabiliriz. $ Y/x $ yerine 5y $.)

2
katma
Bir ipucu olarak, bu benim hedeflediğim çözümün başlangıcıdır *, düzenlemeden önce yayınlamanızın ilk taslağında $ p (x, y) ^ n $ analizinde kullandığınız materyallerden bazıları alakalı $ p (x, y) ^ n + p (y, x) ^ n $ analizinin yapılması. (* Biraz farklı araçlar kullanmayı düşünüyordum, ama bu polinomları kullanarak her şeyi yaptım ve her şey aynıydı)
katma yazar Milo Brandt, kaynak

Belki de çok tembel oluyorum ... belki de soruyu yanlış anlıyorum.

Let f(x) be the sum of rolls modulo 6 of all the dice i <= n/2: $f(x) = \sum_0^{n/2} x_i \ ,mod ~6$

Let g(x) be the sum of rolls modulo 6 of all the dice i > n/2: $g(x) = \sum_{(n/2)+1}^n x_i \ ,mod ~6$

Herhangi bir n için, F ve G için eşit sayıda zar birleştirilir, ancak tek bir silindirdeki her olasılık eşit olduğundan, rulo zarını iki rasgele kazıklara bölebilir ve her bir kazık için toplam modülo 6'yı ayrı ayrı alabilirsiniz .

Geriye kalanlar trivally iki tek ruloya eşdeğerdir.

1
katma
Evet, sanırım soruyu yanlış anladın. Buradaki fikir, f, g fonksiyonlarına sahip olmanızdır; kalıp silindirlerine tümüyle eşit uygulanır ve toplanır.
katma yazar Pankaj, kaynak

Aşağıdakiler normal dağılım, herhangi bir $ n $, herhangi bir sıralanmamış sonuç ve herhangi bir tür zar için uygun değil mi?

Let $d$ = number of virtual output dice
Let $s$ = number of honest die sides
Given $n>d$

$$ x'_1 = f (x_1) + ... + f (x_ {n-d}) \ metin {} [Mod \ metin {} s] $$ $$ x'_2 = f (x_2) + ... + f (x_ {n-d + 1}) \ metin {} [Mod \ metin {} s] $$ $$ x'_3 = f (x_3) + ... + f (x_ {n-d + 2}) \ metin {} [Mod \ metin {} s] $$ $$ \ cdot $$ $$ \ cdot $$ $$ \ cdot $$ $$ x'_d = f (x_d) + ... + f (x_ {n}) \ metin {} [Mod \ metin {} s] $$


1
katma
Zarları ayırt edemezsiniz (hangisinin $ x_1 $ ve hangisinin $ x_ {n-d + 1} $ olduğunu bilmiyorsunuz), bu yüzden $ x_1 '$ veya $ x_2' Bu formülleri kullanarak bildiklerinizden $.
katma yazar jns, kaynak
Ne demek istediğinizi anlıyorum ve bu nedenle normal dağılımın korunması için 16 olası giriş durumunu $ \ Sigma n $ ile 21 gerekli çıkış durumuna eşlemenin mümkün olmadığını hayal edebiliyorum.
katma yazar Aswin P J, kaynak

$ X_i $, artan sıraya göre sıralanan sonuç dizisinin $ i $ th elemanı olsun.

$ K $ rulo yineleme olsun.

$ E = $ $ bile $ E = \ Sigma x_i \ (mod ~ 6) \ $ olsun

$ O = \ Sigma x_i \ (mod ~ 6) \ $ tek $ i $ olsun

$ F $ eşitse $ F = E $, aksi halde $ F = O $

$ K $ tek ise $ G = O $ olsun, aksi halde $ G = E $

1
katma
Bu çözüm, soruda belirtilen biçimde değildir.
katma yazar Pankaj, kaynak

Eğer ifade herhangi bir $ n $ için bile geçerliyse, $ n = 2 $ için de geçerlidir.

$ x_1 '= f (x_1) + f (x_2) \ mod 6 \ x_2 '= g (x_1) + g (x_2) \ mod 6 $

Since $+$ is commutative, the order of the two input dice is not important (e.g. $(3, 5)$ will give the same result as $(5,3)$). This means that the number of unique ordered pairs $(x_1',x_2')$ is at most $21$ (the number of unique inputs). However, the number of unique ordered pairs of two dice roll results is $36>21$, which means that not every result can be produced, and the statement is false.

1
katma
Milo'nun dediği gibi, bu cevap sırasız değil, sipariş edilen çiftlerin sonucunu gösterir. Örneğin. varsayalım (toplamı işlevini unutmak için) $ x'_1 = \ min (x_1, x_2) $ ve $ x'_2 = \ max (x_1, x_2) $ aldık. O zaman bu sıralanmamış bir zar çiftinin dağılımını doğru bir şekilde simüle eder, ancak (örneğinizle aynı nedenlerle) sadece 21 olası çıktı verir. Asla $ (4,3) $ verir (ancak aynı sırasız çifti veren) $ (3,4) $ verir (bu iki kez aynı sıklıkta çift), bu nedenle sıralanmamış çiftlerde indüklenen olasılık dağılımı düzeyinde, gelir. doğru değil.
katma yazar dreeves, kaynak
Neden herhangi bir $ n $ için tutulduğunu anlamıyorum, $ n = 2 $ için tuttuğu anlamına geliyor. Ayrıca, fikir $ (x_1 ', x_2') $ sonucunun da sırasız olarak alındığı şeklindedir - yani eşit miktarda sıralanmamış çift gelirken $ (x_1, x_2) $ çıkıyor. (Söyleyeceğiniz , , sıralanmamış her bir çiftin $ (x_1 ', x_2') $ 'nın iki zar rulosu için görünmediğini kanıtlayabilir, ancak bu önemsiz değildir)
katma yazar Milo Brandt, kaynak
@MiloBrandt: "Sipariş edilenleri" Fons'tan farklı bir anlamda kullanıyorsunuz. Çıktıda "kırmızı kalıp 4 geldi ve mavi kalıp 3 geldi" den farklı bir olay olarak şunu söyleyebilmeniz gerekir: giriş hakkında bu bilgiyi alamadım.
katma yazar pcsnyder, kaynak
Bence Fons, "P bile" tutar, "n bile olsa, P tutar" anlamına gelirken, "P'nin tuttuğu n var mı?" Sorusunu soruyorsun.
katma yazar Pankaj, kaynak

$ X_i $, artan sıraya göre sıralanan sonuç dizisinin $ i $ th elemanı olsun.

$ K $ rulo yineleme olsun.

Iverson braketi notasyonu kullanarak:

$ F = \ Büyük ({\ large {\ scriptsize [k \ in \ {2j: j \ in \ mathbb N \}]} \ sum_ {i = 1} ^ n {\ komut dizisi [i \ in \ {2j− 1: j \ in \ mathbb N \}]} ~ x_i} \ Büyük) (mod ~ 6) + \ Büyük ({\ scriptsize [k \ in \ {2j-1: j \ in \ mathbb N \}]} \ sum_ {i = 1} ^ n {\ scriptsize [i \ in \ {2j: j \ in \ mathbb N \}]} ~ x_i \ Büyük) (mod ~ 6) $

$ G = \ Büyük ({\ large {\ scriptsize [k \ in \ {2j-1: j \ in \ mathbb N \}]} \ toplam_ {i = 1} ^ n {\ scriptsize [i \ in \ { 2j − 1: j \ in \ mathbb N \}]} ~ x_i} \ Büyük) (mod ~ 6) + \ Büyük ({\ komut dosyası [k \ in \ {2j: j \ in \ mathbb N \}]} \ sum_ {i = 1} ^ n {\ scriptsize [i \ in \ {2j: j \ in \ mathbb N \}]} ~ x_i \ Büyük) (mod ~ 6) $

Burada $ n $ tuhaf veya hatta olabilir. $ (mod ~ 6) $ ilgisiz yapar.

0
katma
Yani $ f (x, i, k) $ ve $ g (x, i, k) $ var mı Acaba bu kabul edilebilir mi?
katma yazar Jonathan Allan, kaynak

(Noktayı eksik olan eski cevabımı görmek için bu gönderinin düzenleme geçmişini kontrol edin.)

Şimdi neler olduğunu anladığım için, böyle bir işlevin açıklanan biçimde bulunduğundan emin değilim.

Yani, $ \ sum f (x_i) \ mod 6 = 0 $ 'ı sağlayacak şekilde $ \ bf {x} $ vektörlerinin olduğu durumda olması gerekir; (x_i) \ mod 6 $ düzgün bir şekilde 0 ila 5 arasında dağıtılır.

Giriş ve çıkış durumlarının sayısı sıralanır - temelde herhangi bir sayıda zar için - ancak fonksiyonun bireysel rulolara uygulandığı ve daha sonra toplandığı için durumları yeterince ayırt edebilme yeteneğinizi tahrip ettiğini düşünüyorum. $ F $ 'nın toplamı ile $ g $' ın toplamı arasındaki korelasyondan nasıl kurtulacağınız belli değil, ama aynı zamanda her zaman birbirleriyle nasıl bağlantılı olduklarını kanıtlayacağımı da hemen anlayamadım. Belki de temiz bir grup teorisi argümanı var?

0
katma
"Sırasız" çıktısı fikri, $ (a, b) $ ve $ (b, a) $ 'ın aynı olduğu anlamına gelir - bu da Fons' un cevabını almaya çalıştığım şeydi. Böylece, iki zar için, 21 giriş ve 21 çıkış vardır. Ek olarak, cevabınız, olası giriş sayısının olası çıkış sayısını bölmesinin gerekli olduğunu göstermektedir. Bu, hem girdi hem de çıktı düzgün bir şekilde dağıtıldığında geçerlidir, ancak kombinasyon olarak alındığında girdi kesinlikle düzgün olarak dağıtılmaz, bu nedenle koşul başarısız olur. (örneğin, $ (6,6,6,6) $, $ (1,2,3,4) $ 'dan daha düşük, 24 $ $ daha az gelir.
katma yazar Milo Brandt, kaynak
@MiloBrandt Haklısın, (3,6) ve (6,3) 'ün aynı sonuç olmasına izin verilen diğer soruya dair açıklamayı yanlış anladım. Benim izlenimim, aralarındaki farkı anlayabilmeniz gerektiği idi. Benim sezgim, bölünmenin her türlü uygun haritalamayı elde etmek için gerekli olduğudur, ancak böyle olması gerekmez.
katma yazar pcsnyder, kaynak