Легкий спосіб зробити дві кубики від багатьох

Нещодавно я наткнувся на головоломку: Зробіть дві кубики з трьох , в якому пропонується вирішити справу наступного питання:

Припустимо, я скину $ n $ нерозрізнені кістки. Який алгоритм можна використовувати, видавши суто $ n $ -численні, і жодних відомостей про упорядкування кісток, випрямляючи невпорядковану пару чисел $ a $ і $ b $ така, що розподіл неупорядкованої пари $ (a , b) $ така ж, як розподіл рулону двох неупорядкованих кісток?

Прочитавши рішення, поставлене на запитання, жоден з яких не здавався особливо легко запам'ятати, я направив запитання разом з одним з моїх друзів математики Кассандри. Вона запропонувала наступну загальну форму для більш елегантної стратегії:

Ну, очевидно, якщо б ви хотіли померти від багатьох, можна зробити це, взявши суму в кінець моду $ 6 $. Тобто, якщо кістки виходять у вигляді $ x_1, x_2, \ ldots, x_n $, ви об'єднаєте їх в одне значення, як   $$ x_1 + x_2 + \ ldots + x_n \ pmod6. $$   Замість того, щоб прийняти якусь складну схему для отримання двох рулонів, мені було б більше сенсу спробувати і врятувати цю стратегію. Зокрема, виділіть дві функції $ f $ і $ g $, а потім скажіть, що якщо кістки вийдуть як $ x_1, x_2, \ ldots, x_n $, ви читаєте два рулону наступним чином:   $ $ f (x_1) + f (x_2) + \ ldots + f (x_n) \ pmod6 $$   $ $ g (x_1) + g (x_2) + \ ldots + g (x_n) \ pmod6. $$   Я впевнений, що це можливо для досить великих $ n $ та деяких $ f $ і $ g $.

Мені подобається така ідея, оскільки треба лише запам'ятовувати дві функції на домені та ряд шести елементів, а також уникнути будь-яких справ у справах. Щоб трохи полегшити мою роботу, я вирішив лише розглянути, чи це можливо для навіть $ n $ . Після багато спроб, я не зміг знайти такі функції. Я впевнений, що зможу повернутися і попросити її роз'яснити, але я занадто збентежений, тому я запитаю вас усіх: чи може прогноз Кассандри бути справедливим для будь-якого навіть $ n $?


Оскільки нижчезазначене співвідношення інтерпретує питання інакше, ніж передбачалося, дозвольте мені формально виписати умову: $$ F = f (x_1) + \ ldots + f (x_n) \ pmod 6 $$ $ $ G = g (x_1) + \ ldots + g (x_n) \ pmod 6. $$ Ми хочемо, щоб для будь-яких підходящих $ a $ та $ b $ мали що $ $ P (F = a \ text {and} G = b) + P (F = b \ text {and} G = a) = \ frac (1) {18}. $ $ де $ P $ - ймовірність того, що відбувається подію. Це те, що мається на увазі, говорячи, що $ (F, G) $ має таке ж розподіл, як і рулон двох неупорядкованих кісток.

Як натяк, дозвольте мені сказати, що заплановане рішення не є підрахунковим аргументом, а також не має відношення до вивчення ймовірностей занадто обережно; він має більш аналітичний характер.

10
Де це говорить: "Від чисто трьох цифр, що показують ...", що має бути $ n $ замість трьох? Або, можливо, у першому реченні третій, а не $ n $?
додано Автор hexomino, джерело
@ hexomino Дякуємо, що вказали на це; Я виправив це, щоб бути $ n $ в обох місцях.
додано Автор Milo Brandt, джерело
Я відчуваю, що питання має бути тут теж math.stackexchange.com
додано Автор Adit Kirtani, джерело

8 Відповіді

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

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

Оскільки штампи не відрізнені за дизайном, $ x_i $ - випадкове присвоєння. Використовуйте будь-яке завдання, яке використовується для формування головоломки. Формули задовольняють задачею. Це не аргумент підрахунку, і він не вивчає ймовірності занадто обережно.

4
додано
Вам не дозволяється встановлювати F = x1. Ви повинні вибрати F опосередковано, вказавши, що f, яке разом з рівнянням F = f (x1) + ... + f (xn) визначає F.
додано Автор Matt Obee, джерело
Будь ласка, поясніть. І використовуйте зниження спойлера.
додано Автор Silent-Bob, джерело

[Ця відповідь раніше стверджував, що це не може бути зроблено для будь-яких $ n $, непарних чи навіть, але при доказі було щонайменше два великі отвори. Нижче перераховується лише те, що може стати початком доказу. Я все ще думаю про це.]

Напишіть $ p = x ^ (f (1)) y ^ (g (1)) + \ cdots + x ^ (f (6)) y ^ (g (6)} $. Тоді ймовірність отримання сум $ i, j $ після прокатки $ n $ кісток дається коефіцієнтом $ x ^ iy ^ j $ в $ (p/6) ^ n $. Щоб зменшити суми мод 6, потрібно працювати в поліномах mod $ (x ^ 6-1, y ^ 6-1) $. І питання полягає в тому, чи зможемо ми організувати, що $ p ^ n/6 ^ (n-2) = (1 + \ cdots + x ^ 5) (1 + \ cdots + y ^ 5) $ mod $ (x ^ 6 -1, y ^ 6-1) $ або, що тотожно, $ p ^ n/6 ^ (n-2) = (1 + \ cdots + x ^ 5) (1 + \ cdots + y ^ 5) + 1-x ^ 6) a + (1-y ^ 6) b $, де $ a, b $ - поліноми.

... За винятком того, що ми повинні розглядати пари результатів неупорядкованих , це означає, що ми хочемо, щоб відповідна річ мала місце не для $ p (x, y) ^ n $, а для $ p (x, y) ^ n + p (y, x) ^ n $. Якщо ми поставимо $ x = y $, то це всього лише $ 2p (x, x) ^ n $.

Припустимо, $ x $ - це шостий корінь з одиниці, відмінною від 1. Тоді ясно, що RHS дорівнює нулю, тому LHS теж є. Тож $ p (x, x) ^ n = 0 $ для кожного такого вибору $ x $; тому $ p (x, x) = 0 $ для кожного такого вибору $ x $. Зокрема, коли $ \ omega ^ 6 = 1 $, $ (x- \ omega) $ є коефіцієнтом $ p (x, x) $ і, отже, є продуктом всіх цих факторів, а саме $ (x ^ 6 -1)/(x-1) = 1 + \ cdots + x ^ 5 $.

Тепер, що саме таке $ p (x, x) $? Це $ \ sum x ^ (f (i) + g (i)) $; і пам'ятайте, що ми тільки піклуємось про $ f, g $ mod 6. Отже, що це говорить нам, що кожен залишок мод6 з'являється рівно один раз серед $ f (i) + g (i) $. Таким чином, ми можемо написати $ p = \ sum x ^ i (y/x) ^ (h (i)} $ з звичайними застереженнями щодо показників, які є мод6. (Якщо ви зацікавлені не поліноміальними, скажімо $ x ^ 5y $ замість $ y/x $.)

2
додано
Як дещо натяк, це початок рішення, яке я мав намір *, хоча частина матеріалу, який ви використовували для аналізу $ p (x, y) ^ n $ у першому черновику вашого повідомлення, перш ніж ви редагуєте, є релевантним для аналізу також $ p (x, y) ^ n + p (y, x) ^ n $. (* Я передбачав, що використовую дещо різні інструменти, але я працював над цим поліноміальним твором, і все було приблизно однаковим)
додано Автор Milo Brandt, джерело

Може, я дуже лінько ... можливо, я не розумію питання.

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$

Для будь-яких рівних n рівна кількість кісток поєднуються для F та G, але, оскільки кожна вірогідність на одному рулі є рівною, ви можете просто розбити прокату кістку на дві довільні купи і взяти суму по модулю 6 з кожної палі окремо .

Що залишається, тривіально еквівалентно двом окремим рулонах.

1
додано
Так, я думаю, ви неправильно зрозуміли це питання. Ідея полягає в тому, що у вас є функції f, g, які рівномірно застосовуються до всім , які згортаються і складаються.
додано Автор Pankaj, джерело

Чи не виходить наступний нормальний розподіл для будь-якого $ n $, будь-якої кількості невпорядкованих виходів і будь-якого типу кістки?

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
додано
Ви не можете розрізнити кістки (тобто ви не знаєте, яка з них - $ x_1 $, а яка з них $ x_ (n-d + 1) $), тому ви не можете вивести $ x_1 '$ або $ x_2' $ від того, що ви знаєте, використовуючи ці формули.
додано Автор jns, джерело
Я бачу, що ви маєте на увазі, і тому я не можу уявити ніякого способу нанесення 16 можливих вхідних станів $ \ Sigma n $ у 21 необхідний вихідний стан для збереження нормального розподілу.
додано Автор Aswin P J, джерело

Хай $ x_i $ - це $ i $ -й елемент послідовності результатів, сортованих у зростаючому порядку.

Нехай $ k $ - ітерація рулонів.

Нехай $ E = \ Sigma x_i \ (mod ~ 6) \ $ для рівномірного $ i $

Нехай $ O = \ Sigma x_i \ (mod ~ 6) \ $ для непарних $ i $

Хай $ F = E $, якщо $ k $ є рівним, інакше $ F = O $

Нехай $ G = O $, якщо $ k $ непарний, інакше $ G = E $

1
додано
Це рішення не відповідає формі, вказаній у питанні.
додано Автор Pankaj, джерело

Якщо заява триває для будь-якого навіть $ n $, вона тримається при $ 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
додано
Як каже Міло, ця відповідь показує результат для замовлених пар, а не невпорядкований. Наприклад, Припустимо (забуваючи про суму-функції), ми взяли $ x'_1 = \ min (x_1, x_2) $, а $ x'_2 = \ max (x_1, x_2) $. Тоді це робить точно імітує розподіл невпорядкованої пари кісток, хоча (з тих же причин, що і ваш приклад) він лише дає 21 можливі результати. Він ніколи не дасть $ (4,3) $, але він дасть $ (3,4) $ (що дає ту ж неупорядковану пару) вдвічі частіше, тому на рівні індукованого розподілу ймовірностей на неупорядкованих парах це приходить вийде правильно
додано Автор dreeves, джерело
Я не розумію, чому його тримання для будь-яких рівних $ n $ означає, що він тримається при $ n = 2 $. Крім того, ідея полягає в тому, що результат $ (x_1 ', x_2') $ також вважається невпорядкованим - так що в ній виникають однаково багато неупорядкованих пар $ (x_1, x_2) $. (Отже, ви можете довести, що не кожна неупорядкована пара $ (x_1 ', x_2') $ відображається для двох кісткових рулонів, але це не є тривіальним)
додано Автор Milo Brandt, джерело
@MiloBrandt: Ви використовуєте "замовлений" в іншому сенсі, ніж Fons. Ви повинні бути в змозі сказати "червона смерть прийшла 3, і синя смерть прийшла 4" на виході, як окрема подія від "червона смерть прийшла 4, а синя смерть підійшла 3", але ви don Не отримуйте цю інформацію про вхід.
додано Автор pcsnyder, джерело
Я думаю, Фони можуть взяти "P тримається для будь-якого навіть n", щоб означати "для всіх навіть n, P тримає", тоді як ви задаєте запитання "чи існує навіть n, для якого P тримається?".
додано Автор Pankaj, джерело

Хай $ x_i $ - це $ i $ -й елемент послідовності результатів, сортованих у зростаючому порядку.

Нехай $ k $ - ітерація рулонів.

Використання позначення дужки Іверсона:

$ 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) $

Тут $ n $ може бути непарним чи рівним. $ (mod ~ 6) $ робить це нерелевантним.

0
додано
Так що у вас є $ f (x, i, k) $ і $ g (x, i, k) $ Цікаво, чи це прийнятно?
додано Автор Jonathan Allan, джерело

(Перевірте історію редагування цього повідомлення, щоб переглянути мою стару відповідь, в якій відсутня точка.)

Тепер, коли я бачу, що відбувається, я не впевнений, що така функція існує в описаній формі.

Тобто нам потрібно, щоб це мало місце, коли існують принаймні шість векторов $ \ bf {x} $, таких, що $ \ sum f (x_i) \ mod 6 = 0 $, які також задовольняють властивості $ \ sum g (x_i) \ mod 6 $ рівномірно розподілено від 0 до 5.

Число вхідних та вихідних станів вирівнюється - за принципом будь-якої кількості кісток - але я думаю, що функціональне обмеження, що функція застосовується до окремих рулонів, а потім підсумовується, руйнує вашу здатність достатньо відрізнити стану. Не зрозуміло, як ви збираєтеся позбутися співвідношення між сумою $ f $ і сумою $ g $, але мені також не видно, як довести, що вони завжди пов'язані. Можливо, тут є аргумент теорії групової роботи, що є акуратним?

0
додано
Ідея "невпорядкованого" виходу полягає в тому, що $ (a, b) $ і $ (b, a) $ вважаються однаковими - це те, що я намагався отримати за підсумками відповіді Фона. Отже, для двох кубиків є 21 вхід і 21 вихід. Крім того, ваша відповідь передбачає, що необхідно, щоб кількість можливих введених даних поділяла кількість можливих виходів. Це вірно, коли як вхідний, так і вихідний розподіляються рівномірно, однак вхід, коли він приймається як комбінація, безумовно, не розподіляється рівномірно, тому стан не вдається. (наприклад, $ (6,6,6,6) $ перевищує $ 24 $ час рідше, ніж $ (1,2,3,4) $)
додано Автор Milo Brandt, джерело
@MiloBrandt Ви маєте рацію, я помиляюся роз'ясненням з іншого питання, де (3,6) та (6,3) дозволено мати один і той самий результат. Мені було враження, що ти повинен був сказати різницю між ними. Моя інтуїція полягає в тому, що поділ потрібно для отримання будь-якого зручного картографування, але це не повинно бути справою.
додано Автор pcsnyder, джерело