Een luie manier om twee dobbelstenen van velen te maken

Onlangs struikelde ik over de puzzel: Maak twee dobbelstenen van de drie , waarin wordt gevraagd om een ​​oplossing voor een geval van de volgende vraag:

Stel dat ik $ n $ ononderscheidbare dobbelstenen rol. Van puur de $ n $ -nummers die verschijnen, en geen informatie over de volgorde van de dobbelstenen, welk algoritme kan ik gebruiken, een ongeordend paar getallen $ a $ en $ b $ uitspugen zodat de distributie van het ongeordende paar $ (a , b) $ is hetzelfde als de verdeling van een worp van twee ongeordende dobbelstenen?

Nadat ik de oplossingen had gelezen die op de vraag waren gesteld, waarvan geen enkele bijzonder gemakkelijk te onthouden leek, stuurde ik de vraag door naar een van mijn wiskundige vrienden, Cassandra. Ze stelde de volgende algemene vorm voor voor een elegantere strategie:

Nou, natuurlijk, als je iemand van veel wilt laten sterven, kun je dat doen door de som van de dobbelstenen mod $ 6 $ te nemen. Dat wil zeggen, als de dobbelstenen omhoog komen als $ x_1, x_2, \ ldots, x_n $ combineer je ze in één waarde als   $$ x_1 + x_2 + \ ldots + x_n \ pmod6. $$   In plaats van een ingewikkeld schema aan te nemen om twee rollen te krijgen, zou het logischer zijn om te proberen deze strategie te redden. Kies in het bijzonder twee functies $ f $ en $ g $ en zeg dan dat als de dobbelstenen omhoog komen als $ x_1, x_2, \ ldots, x_n $, je de twee rollen als volgt leest:   $$ f (x_1) + f (x_2) + \ ldots + f (x_n) \ pmod6 $$   $$ g (x_1) + g (x_2) + \ ldots + g (x_n) \ pmod6. $$   Ik weet zeker dat dit mogelijk is voor groot genoeg $ n $ en wat $ f $ en $ g $.

Ik vind dit een goed idee, omdat je maar twee functies op een domein en in een reeks van zes elementen hoeft te onthouden en geen zaken hoeft te doen. Om mijn werk een beetje te vergemakkelijken, heb ik besloten om alleen te overwegen of dit mogelijk is voor zelfs $ n $ . Na veel proberen heb ik dergelijke functies niet kunnen vinden. Ik weet zeker dat ik terug kan gaan en haar om opheldering kan vragen, maar ik ben te beschaamd - dus ik zal jullie allemaal vragen: kan de voorspelling van Cassandra waar zijn voor elke $ n $?

Als een paar antwoorden hieronder de vraag anders interpreteren dan bedoeld, laat ik de voorwaarde formeel noteren: Laat $$ F = f (x_1) + \ ldots + f (x_n) \ pmod 6 $$ $$ G = g (x_1) + \ ldots + g (x_n) \ pmod 6. $$ We willen dat voor elke geschikte $ a $ en $ b $ we die $$ P hebben (F = a \ text {en} G = b) + P (F = b \ tekst {en} G = a) = \ frac {1} {18}. $$ waar $ P $ de kans is dat een gebeurtenis plaatsvindt. Dit is wat wordt bedoeld door te zeggen dat $ (F, G) $ dezelfde verdeling heeft als een worp van twee ongeordende dobbelstenen.

Laat me als een hint zeggen dat de bedoelde oplossing geen tel argument is en ook niet te zorgvuldig onderzoekt naar waarschijnlijkheden; het is eerder analytisch van aard.

 10
toegevoegd bewerkt
Bekeken: 2
de bron
Waar staat 'Van puur de drie cijfers die tonen ...', zou dat $ n $ moeten zijn in plaats van drie? Of misschien moet het in de eerste zin drie zijn in plaats van $ n $?
toegevoegd de auteur hexomino, de bron
@hexomino Bedankt voor het wijzen van dat; Ik heb het op beide plaatsen opgelost als $ n $.
toegevoegd de auteur Milo Brandt, de bron
Ik denk dat de vraag hier ook zou moeten zijn math.stackexchange.com
toegevoegd de auteur Adit Kirtani, de bron

8 antwoord

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

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

Omdat de dobbelsteen niet te onderscheiden is door het ontwerp, is $ x_i $ een willekeurige toewijzing. Gebruik de opdracht die het OP heeft gebruikt bij het inkaderen van de puzzel. De formules voldoen aan het probleem. Het is geen tel-argument, en het onderzoekt de kansen niet te zorgvuldig.

4
toegevoegd
de bron
U mag F = x1 niet instellen. Je moet F indirect kiezen door op te geven wat f is, wat samen met de vergelijking F = f (x1) + ... + f (xn) F definieert.
toegevoegd de auteur Matt Obee, de bron
Graag uitleggen. En gebruik spoiler-prijsvermindering.
toegevoegd de auteur Silent-Bob, de bron

[Dit antwoord beweerde eerder te bewijzen dat het niet mogelijk is voor $ n $, oneven of zelfs, maar er waren minstens twee grote gaten in het bewijs. Het volgende beweert nu niet meer te zijn dan wat ooit het begin van een bewijs zou kunnen zijn. Ik denk er nog steeds over na.]

Schrijf $ p = x ^ {f (1)} y ^ {g (1)} + \ cdots + x ^ {f (6)} y ^ {g (6)} $. Vervolgens wordt de kans om $ i, j $ te krijgen na het gooien van $ n $ dobbelstenen gegeven door de coëfficiënt van $ x ^ iy ^ j $ in $ (p/6) ^ n $. Om de sommen mod 6 te verminderen, moeten we werken in polynomen mod $ (x ^ 6-1, y ^ 6-1) $. En de vraag is dan of we die $ p ^ n/6 ^ {n-2} = (1+ \ cdots + x ^ 5) (1+ \ cdots + y ^ 5) $ mod $ (x ^ 6) kunnen regelen -1, y ^ 6-1) $ of, equivalent, $ p ^ n/6 ^ {n-2} = (1+ \ cdots + x ^ 5) (1+ \ cdots + y ^ 5) + ( 1-x ^ 6) a + (1-y ^ 6) b $ waarbij $ a, b $ polynomen zijn.

... Behalve dat we naar ongeordende paren van resultaten moeten kijken, wat betekent dat we willen dat een overeenkomstig ding niet geldt voor $ p (x, y) ^ n $ maar voor $ p (x, y) ^ n + p (y, x) ^ n $. Als we $ x = y $ plaatsen, is dit slechts $ 2p (x, x) ^ n $.

Stel dat $ x $ een zesde wortel is van een eenheid anders dan 1. Dan is de RHS duidelijk nul, dus de LHS is dat ook. Dus $ p (x, x) ^ n = 0 $ voor elke dergelijke keuze van $ x $; dus $ p (x, x) = 0 $ voor elke dergelijke keuze van $ x $. In het bijzonder, wanneer $ \ omega ^ 6 = 1 $, $ (x- \ omega) $ is een factor van $ p (x, x) $ en dus is het product van al deze factoren, namelijk $ (x ^ 6 -1)/(x-1) = 1 + \ cdots + x ^ 5 $.

Wat is nu precies $ p (x, x) $? Het is $ \ sum x ^ {f (i) + g (i)} $; en onthoud dat we alleen om $ f, g $ mod 6 geven. Dus wat dit ons vertelt is dat elke residu mod 6 precies één keer voorkomt uit de $ f (i) + g (i) $. Dus we kunnen $ p = \ sum x ^ i (y/x) ^ {h (i)} $ schrijven met de gebruikelijke kanttekeningen dat exponenten mod 6. zijn. (Als je niet tevreden bent over niet-polynomen, zeg dan $ x ^ 5y $ in plaats van $ y/x $.)

2
toegevoegd
de bron
Als een beetje een hint, is dit het begin van de oplossing die ik van plan was *, hoewel een deel van het materiaal dat je gebruikte om $ p (x, y) ^ n $ te analyseren in de eerste versie van je bericht voordat je het hebt bewerkt, relevant is om ook $ p (x, y) ^ n + p (y, x) ^ n $ te analyseren. (* Ik bedacht me om enigszins verschillende tools te gebruiken, maar ik heb dingen uitgewerkt met behulp van deze polynomen, en alles is ongeveer hetzelfde)
toegevoegd de auteur Milo Brandt, de bron

Misschien ben ik te lui ... misschien begrijp ik de vraag verkeerd.

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$

Voor elke even n wordt een gelijk aantal dobbelstenen gecombineerd voor F en voor G, maar omdat elke kans op een enkele worp gelijk is, kunt u de opgerolde dobbelstenen eenvoudig in twee willekeurige stapels splitsen en de som modulo 6 van elke stapel afzonderlijk nemen .

Wat overblijft is triviaal equivalent aan twee enkele rollen.

1
toegevoegd
de bron
Ja, ik denk dat je de vraag verkeerd begrijpt. Het idee is dat je functies f, g hebt die uniform op alle matrijsrollen worden toegepast en worden opgeteld.
toegevoegd de auteur Pankaj, de bron

Levert het volgende niet de normale verdeling op, voor $ n $, een onbeperkt aantal uitgangen en elk type dobbelsteen?

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}) \ text {} [Mod \ text {} s] $$ $$ x'_2 = f (x_2) + ... + f (x_ {n-d + 1}) \ text {} [Mod \ text {} s] $$ $$ x'_3 = f (x_3) + ... + f (x_ {n-d + 2}) \ text {} [Mod \ text {} s] $$ $$ \ cdot $$ $$ \ cdot $$ $$ \ cdot $$ $$ x'_d = f (x_d) + ... + f (x_ {n}) \ text {} [Mod \ text {} s] $$

1
toegevoegd
de bron
Je kunt de dobbelstenen niet onderscheiden (dat wil zeggen dat je niet weet welke $ x_1 $ is en welke $ x_ {n-d + 1} $), dus je kunt $ x_1 '$ of $ x_2' niet afleiden $ van wat je weet met behulp van deze formules.
toegevoegd de auteur jns, de bron
Ik begrijp wat je bedoelt en daarom kan ik me geen mogelijke manier voorstellen om 16 mogelijke invoerstatussen $ \ Sigma n $ in de 21 benodigde uitvoertoestanden te plaatsen om de normale verdeling te behouden.
toegevoegd de auteur Aswin P J, de bron

Laat $ x_i $ het $ i $ e-element van de volgorde van resultaten zijn, gesorteerd in oplopende volgorde.

Laat $ k $ de roll-iteratie zijn.

Laat $ E = \ Sigma x_i \ (mod ~ 6) \ $ voor zelfs $ i $

Laat $ O = \ Sigma x_i \ (mod ~ 6) \ $ voor oneven $ i $

Laat $ F = E $ als $ k $ gelijk is, anders $ F = O $

Laat $ G = O $ als $ k $ oneven is, anders $ G = E $

1
toegevoegd
de bron
Deze oplossing is niet van het formulier dat is opgegeven in de vraag.
toegevoegd de auteur Pankaj, de bron

Als de instructie geldt voor elke even $ n $, geldt dit voor $ n = 2 $.

$ 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
toegevoegd
de bron
Zoals Milo zegt, toont dit antwoord het resultaat voor besteld paren, niet ongeordend. Bijv. veronderstel (vergeet het som-a-functie ding) we namen $ x'_1 = \ min (x_1, x_2) $, en $ x'_2 = \ max (x_1, x_2) $. Dan simuleert dit nauwkeurig de verdeling van een ongeordend paar dobbelstenen, hoewel het (om dezelfde redenen als uw voorbeeld) slechts 21 mogelijke uitgangen geeft. Het geeft nooit $ (4,3) $, maar het geeft $ (3,4) $ (wat hetzelfde ongeordende paar oplevert) twee keer zo vaak, dus op het niveau van de geïnduceerde kansverdeling op ongeordende paren, komt het uit correct.
toegevoegd de auteur dreeves, de bron
Ik zie niet in waarom het houdt voor een even $ n $ impliceert dat het geldt voor $ n = 2 $. Ook is het idee dat het resultaat $ (x_1 ', x_2') $ ook als ongeordend wordt beschouwd - dus er komen net zoveel ongeordende paren $ (x_1, x_2) $ binnen als er uitgaan. (Dat gezegd hebbende, je kan bewijzen dat niet elk ongeordend paar $ (x_1 ', x_2') $ voor twee dobbelstenen verschijnt, maar dit is niet triviaal)
toegevoegd de auteur Milo Brandt, de bron
@MiloBrandt: u gebruikt "besteld" in een andere betekenis dan Fons is. Je moet kunnen zeggen "de rode dobbelsteen kwam op 3, en de blauwe dobbelsteen kwam 4" in de uitvoer voor als een duidelijke gebeurtenis van "de rode dobbelsteen kwam 4 en de blauwe dobbelsteen kwam 3", maar jij die informatie over de invoer niet.
toegevoegd de auteur pcsnyder, de bron
Ik denk dat Fons "P houdt voor elke even n" kan betekenen "voor alle even n, P houdt" terwijl je de vraag stelt "is er een even n waarvoor P in het spel is?".
toegevoegd de auteur Pankaj, de bron

Laat $ x_i $ het $ i $ e-element van de volgorde van resultaten zijn, gesorteerd in oplopende volgorde.

Laat $ k $ de roll-iteratie zijn.

Iverson-beugelnotatie gebruiken:

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

$ G = \ Big ({\ large {\ scriptsize [k \ in \ {2j-1: j \ in \ mathbb N \}]} \ sum_ {i = 1} ^ n {\ scriptsize [i \ in \ { 2j-1: j \ in \ mathbb N \}]} ~ x_i} \ Big) (mod ~ 6) + \ Big ({\ scriptsize [k \ in \ {2j: j \ in \ mathbb N \}]} \ sum_ {i = 1} ^ n {\ scriptsize [i \ in \ {2j: j \ in \ mathbb N \}]} ~ x_i \ Big) (mod ~ 6) $

Hier kan $ n $ oneven of even zijn. $ (mod ~ 6) $ maakt het niet relevant.

0
toegevoegd
de bron
Dus je hebt $ f (x, i, k) $ en $ g (x, i, k) $ ik vraag me af of dat acceptabel is?
toegevoegd de auteur Jonathan Allan, de bron

(Controleer de bewerkingsgeschiedenis van dit bericht om mijn oude antwoord te bekijken, dat het punt ontbrak.)

Nu ik zie wat er aan de hand is, heb ik er geen vertrouwen in dat zo'n functie bestaat uit de beschreven vorm.

Dat wil zeggen, we hebben het nodig dat er tenminste zes $ \ bf {x} $ vectoren zijn, zodanig dat $ \ sum f (x_i) \ mod 6 = 0 $, die ook voldoen aan de eigenschap dat $ \ sum g (x_i) \ mod 6 $ wordt uniform verdeeld van 0 tot 5.

Het aantal invoer- en uitvoerstatussen komt overeen - voor in principe een willekeurig aantal dobbelstenen - maar ik denk dat de functionele beperking die de functie toepast op individuele rollen, en vervolgens wordt opgeteld, je vermogen vernietigt om voldoende onderscheid te maken tussen toestanden. Het is niet duidelijk hoe je de correlatie tussen de som van $ f $ en de som van $ g $ kwijt raakt, maar het is ook niet meteen duidelijk hoe te bewijzen dat ze altijd gekoppeld zijn. Misschien is hier een argument voor een groepentheorie dat het netjes is?

0
toegevoegd
de bron
Het idee van "ongeordende" uitvoer is dat $ (a, b) $ en $ (b, a) $ gelijk worden genomen - en dat probeerde ik onder Fons 'antwoord te krijgen. Dus voor twee dobbelstenen zijn er 21 ingangen en 21 uitgangen. Bovendien suggereert uw antwoord dat het noodzakelijk is dat het aantal mogelijke inputs het aantal mogelijke outputs verdeelt. Dit is het geval wanneer zowel de invoer als de uitvoer gelijkmatig worden verdeeld, maar de invoer, wanneer deze als combinaties wordt genomen, is zeker niet uniform verdeeld, dus de conditie mislukt. (bijvoorbeeld $ (6,6,6,6) $ komt $ 24 $ keer minder vaak voor dan $ (1,2,3,4) $)
toegevoegd de auteur Milo Brandt, de bron
@MiloBrandt Je hebt gelijk, ik heb de toelichting op de andere vraag verkeerd gelezen, waarbij (3,6) en (6,3) hetzelfde resultaat mogen hebben. Mijn indruk was dat je het verschil tussen hen kon zien. Mijn intuïtie is dat een indeling nodig is om elke vorm van handige mapping te krijgen, maar dat hoeft niet het geval te zijn.
toegevoegd de auteur pcsnyder, de bron