Лянівы спосаб зрабіць два кубіка з многіх

Нядаўна я натыкнуўся на загадку: зрабіць два кубіка з трох , які просіць рашэнне ў выпадку на наступнае пытанне:

<Р> Выкажам здагадку, я качуся $ N $ неадрозныя косткі. Ад чыста $ N $ лікаў паказу, і ніякай інфармацыі пра упарадкаванні косткі, які алгарытм можна выкарыстоўваць, выплёўваючы неўпарадкаваныя пару лікаў $ 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) + е (x_2) + \ ldots + е (x_n) \ pmod6 $$   $$ г (x_1) + г (x_2) + \ ldots + г (x_n) \ pmod6. $$   Я ўпэўнены, што гэта магчыма пры досыць вялікіх $ N $ і некаторага $ F $ і $ G $.

Мне падабаецца гэтая ідэя, так як можна было б толькі запомніць дзве функцыі на вобласці і дыяпазоне шасці элементаў і пазбегнуць якога-небудзь корпуса ўстаноўкі. Для таго, каб палегчыць маю працу крыху, я вырашыў толькі разгледзець, ці магчыма гэта <моцны> для нават $ N $ . Пасля доўгіх спроб, я не змог знайсці такія функцыі. Я ўпэўнены, што змагу вярнуцца і папрасіць у яе тлумачэнняў, але я занадта зьбянтэжаны, - таму я прашу ўсіх вас: Ці можа прадказанне Касандры быць дакладна для любых нават $ N $?


Як пара адказы ніжэй інтэрпрэтаваць пытанне інакш, чым меркавалася, дазвольце мне выпісаць ўмова фармальна: Няхай $$ F = F (x_1) + \ ldots + е (x_n) \ PMOD 6 $$ $$ G = (x_1) + \ ldots + г (x_n) \ PMOD 6. $$ мы хочам мець, што для любой прыдатны $ A $ і $ B $ мы маем, што $$ P (F = а \ тэкст {і} G = Ь) + Р (Р = Ь \ тэкст {і} G = ы) = \ гидроразрыва {1} {18}. $$ дзе $ P $ ёсць верагоднасць падзеі адбываецца. Гэта тое, што меў на ўвазе, кажучы, што $ (F, G) $ мае такое ж размеркаванне, як рулон двух неўпарадкаваных косткі.

У якасці падказкі, дазвольце мне сказаць, што меркаванае рашэнне не з'яўляецца падлік аргументу, і не трэба рабіць занадта дбайнае вывучэнне верагоднасці; гэта значна больш аналітычны характар.

10
Дзе ён кажа: «З чыста тры лічбы, паказваючы ...», гэта павінна быць $ п $ замест трох? Ці, можа быць, у першым сказе, яно павінна быць тры замест $ п $?
дададзена аўтар hexomino, крыніца
@hexomino Дзякуй за ўказанне, што з; Я усталяваў, што гэта будзе $ п $ у абодвух месцах.
дададзена аўтар Milo Brandt, крыніца
Я адчуваю, пытанне павінна быць тут math.stackexchange.com
дададзена аўтар Adit Kirtani, крыніца

8 адказы

<Р> $ F = F (x_1) + ... + е (x_n) = x_1 $

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

Паколькі матрыца неадметныя па дызайне, $ x_i $ з'яўляецца выпадковае размеркаванне. Выкарыстоўвайце тое, што прызначэнне ОП выкарыстоўваюцца ў абрамленні галаваломкі. Формулы задавальняюць гэтую праблему. Гэта не аргумент падліку, і яна не разглядае верагоднасці занадта старанна.

4
дададзена
Вы не можаце ўсталяваць F = x1. Вы павінны выбраць F ўскосна, паказаўшы, што Р, у якім разам з раўнаннем F = F (x1) + ... + е (хп) вызначае F.
дададзена аўтар Matt Obee, крыніца
Калі ласка, растлумачце. І выкарыстоўваць спойлер ўцэнкі.
дададзена аўтар Silent-Bob, крыніца

[Гэты адказ раней сцвярджаў, што даказаць, што рэч не можа быць зроблена для любога $ N $, цотным або няцотнай, але па меншай меры два вялікіх адтуліны ў доказе. Ніжэй цяпер сцвярджае, што не павінна быць не больш, чым тое, што можа калі-небудзь стаць пачаткам доказы. Я ўсё яшчэ думаю пра гэта.]

Запіс $ р = х ^ {F (1)} {ў ^ г (1)} + \ cdots + х ^ {F (6)} {ў ^ г (6)} $. Тады верагоднасць траплення сум $ I, J $ пасля пракаткі $ N $ косткі вызначаецца каэфіцыентам $ х ^ гу ^ J $ ў $ (р/6) ^ N $. Для памяншэння сум мод 6 мы павінны працаваць у полиномах мод $ (х ^ 6-1, у ^ 6-1) $. І пытанне тады можам мы зладзіць, што $ р ^ п/6 ^ {п-2} = (1+ \ cdots + х ^ 5) (1+ \ cdots + у ^ 5) $ мод $ (х ^ 6 -1, у ^ 6-1) $ або, што тое ж самае, што $ р ^ п/6 ^ {п-2} = (1+ \ cdots + х ^ 5) (1+ \ cdots + у ^ 5) + ( 1-х ^ 6) а + (1-й ^ 6) б $, дзе $ а, B $ полиномы.

... Акрамя таго, што мы павінны глядзець на неўпарадкаваных пар вынікаў, а гэта значыць, што мы хочам, каб адпаведная рэч мае месца ня дзеля $ р (х, у) ^ п $, але для $ р (х, у) ^ п + р (у, х) ^ п $. Калі пакласці $ х = у $, то гэта ўсяго толькі $ 2р (х, х) ^ п $.

Хай $ X $ з'яўляецца шосты корань з адзінкі, акрамя 1. Тады ясна, што RHS роўная нуля, так што LHS таксама. Так $ р (х, х) ^ п = 0 $ для кожнага такога выбару $ х $; так што $ р (х, х) = 0 $ для кожнага такога выбару $ х $. У прыватнасці, калі $ \ Omega ^ 6 = 1 $, $ (х \ Omega) $ з'яўляецца фактарам $ р (х, х) $ і, такім чынам, такім чынам з'яўляецца творам ўсіх гэтых фактараў, а менавіта $ (х ^ 6 -1)/(х-1) = 1 + \ cdots + х ^ 5 $.

Цяпер, што менавіта $ р (х, х) $? Гэта $ \ сума х ^ {е (я) + г (я)} $; і памятайце, што мы клапоцімся толькі пра $ F, G $ модом 6. Так што гэта кажа нам пра тое, што кожны вылік па модулю 6 з'яўляецца роўна адзін раз сярод $ F (я) + г (я) $. Такім чынам, мы можам напісаць $ р = \ сума х ^ я (у/х) ^ {ч (я)} $ са звычайнымі агаворкамі з нагоды паказчыкаў, якія з'яўляюцца па модулю 6. (Калі вы пераборлівы пра не-мнагачлена, скажам, $ х ^ 5у $ замест $ г/х $.)

2
дададзена
Неяк намёк, гэта пачатак рашэння я меў намер *, хоць некаторыя з матэрыялу, які вы выкарыстоўвалі для аналізу $ р (х, у) ^ п $ у першым праекце вашага паста перад рэдагаваннем актуальныя да аналізу $ р (х, у) ^ п + р (у, х) ^ п $ а. (* Я мяркуючы, выкарыстоўваючы некалькі розных інструментаў, але я працаваў рэчы з дапамогай гэтых полиномов, і ўсё пра тое ж)
дададзена аўтар 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$

Для любога цотнага п, роўны лік кубікаў аб'ядноўваецца для 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_ {п-д}) \ {тэкст} [Mod \ тэкст {} с] $$ $$ x'_2 = F (x_2) + ... + F (X_ {n-й + 1}) \ {тэкст} [Mod \ тэкст {} с] $$ $$ x'_3 = F (x_3) + ... + F (X_ {n-й + 2}) \ {тэкст} [Mod \ тэкст {} с] $$ $$ \ CDOT $$ $$ \ CDOT $$ $$ \ CDOT $$ $$ x'_d = е (x_d) + ... + е (X_ {п}) \ тэкст {} [Mod \ тэкст {} s] $$


1
дададзена
Вы не можаце адрозніць косткі (гэта значыць, вы не ведаеце, які з іх $ x_1 $ і які адзін з'яўляецца $ x_ {п-d + 1} $), так што вы не можаце вывесці $ x_1 «$ або $ x_2» $ ад таго, што вы ведаеце, з дапамогай гэтых формул.
дададзена аўтар jns, крыніца
Я разумею, што вы маеце на ўвазе, і таму я не магу сабе ўявіць, ня магчымы спосаб адлюстравання 16 магчымых ўваходных стану $ \ Sigma $ п ў 21 неабходных выходных стану для захавання нармальнага размеркавання.
дададзена аўтар Aswin P J, крыніца

Хай $ x_i $ будзе на $ I $ й элемент паслядоўнасці вынікаў у парадку ў парадку ўзрастання.

Хай $ K $ будзе рулонная ітэрацыі.

Хай $ E = \ Sigma x_i \ (мод ~ 6) \ $ за нават $ I $

Хай $ O = \ Sigma x_i \ (мод ~ 6) \ $ для няцотнай $ I $

Хай $ F = E $, калі $ да $ цотна, у адваротным выпадку $ F = O $

Хай $ G = O $, калі $ да $ няцотная, у адваротным выпадку $ G = E $

1
дададзена
Гэта рашэнне не ў форме, названай у гэтым пытанні.
дададзена аўтар Pankaj, крыніца

Калі зацвярджэнне справядліва для любых нават $ N $, гэта мае месца для $ n = 2 $.

$ X_1 = F (x_1) + е (x_2) \ мод 6 \\ x_2 '= г (x_1) + г (x_2) \ мод 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 = \ мін (x_1, x_2) $ і $ x'_2 = \ макс (x_1, x_2) $. Тады гэта <я> гэта дакладна мадэляваць размеркаванне неўпарадкаванай пары костак, хоць (па тых жа прычынах, што і ваш прыклад) дае толькі 21 магчымых выхадаў. Яна ніколі не дасць $ (4,3) $, але гэта дасьць $ (3,4) $ (што дае тую ж самую неўпарадкаваных пару) у два разы часцей, так што на ўзроўні індукаванага размеркавання верагоднасцяў на неўпарадкаваных пар, гаворка ідзе з правільна.
дададзена аўтар dreeves, крыніца
Я не разумею, чаму ён трымае для любога нават $ п $ вынікае, што мае месца для $ n = 2 $. Акрамя таго, ідэя заключаецца ў тым, што вынік $ (x_1 ', x_2') $ таксама бярэцца неўпарадкаванай - таму аднолькава шмат неўпарадкаваных пароў $ (x_1, x_2) $ ідзе як там згасае. (Тым не менш, вы <я> можна даказаць, што не ўсякая неўпарадкаваных пара $ (x_1 ', x_2') $ паказвае на двух кідкоў костак, але гэта не трывіяльна)
дададзена аўтар Milo Brandt, крыніца
@MiloBrandt: Вы карыстаецеся «замовілі» у іншым сэнсе, чым Fons ёсць. Вы павінны быць у стане сказаць «чырвоны кубік прыйшоў 3, а сіні кубік прыйшоў 4» на выхадзе як асобную падзею з «чырвонага кубіка прыйшоў 4 і сіні кубік прыйшоў 3», але вы не «т атрымаць гэтую інфармацыю пра ўвод.
дададзена аўтар pcsnyder, крыніца
Я думаю, што Fons можа прымаць «P мае месца для любога цотнага п» азначае «для ўсіх цотных п, Р мае месца», тым часам як вы задаеце пытанне «ці ёсць яшчэ п, для якіх P мае месца?».
дададзена аўтар Pankaj, крыніца

Хай $ x_i $ будзе на $ I $ й элемент паслядоўнасці вынікаў у парадку ў парадку ўзрастання.

Хай $ K $ будзе рулонная ітэрацыі.

Выкарыстоўваючы Айверсон кранштэйн абазначэння:

$ F = \ Вялікі ({\ вялікая {\ scriptsize [к \ у \ {2j: J \ у \ mathbb N \}]} \ sum_ {= 1} ^ п {\ scriptsize [г \ у \ {2j- 1: J \ у \ mathbb N \}]} ~ x_i} \ Вялікі) (мод ~ 6) + \ Вялікі ({\ scriptsize [к \ у \ {2j-1: J \ у \ mathbb N \}]} \ sum_ {= 1} ^ п {\ scriptsize [г \ у \ {2j: J \ у \ mathbb N \}]} ~ x_i \ Вялікі) (мод ~ 6) $

$ G = \ Big ({\ вялікая {\ scriptsize [к \ у \ {2j-1: J \ у \ mathbb N \}]} \ sum_ {= 1} ^ п {\ scriptsize [г \ у \ { 2j-1: J \ у \ mathbb N \}]} ~ x_i} \ Вялікі) (мод ~ 6) + \ Вялікі ({\ scriptsize [к \ у \ {2j: J \ у \ mathbb N \}]} \ sum_ {= 1} ^ п {\ scriptsize [г \ у \ {2j: J \ у \ mathbb N \}]} ~ x_i \ Вялікі) (мод ~ 6) $

Тут $ N можа быць цотных або няцотных. $ (Мод ~ 6) $ робіць гэта не мае значэння.

0
дададзена
Такім чынам, у вас ёсць $ F (х, I, K) $ і $ г (х, I, K) $ Цікава, калі гэта прымальна?
дададзена аўтар Jonathan Allan, крыніца

(Праверце гістарычныя версіі гэтай пасады, каб убачыць мой стары адказ, які быў які адсутнічае пункт.)

Цяпер, калі я бачу, што адбываецца, я не ўпэўнены, што такая функцыя існуе апісаны выгляд.

Гэта значыць, нам трэба, каб гэта было ў выпадку, калі ёсць, па меншай меры, шэсць $ \ БФ {х} $ вектары, такія, што $ \ сума е (x_i) \ мод 6 = 0 $, якія таксама задавальняюць тым уласцівасцю, што $ \ сума г (x_i) \ модов 6 $ раўнамерна размеркаваны ад 0 да 5.

Колькасць ўваходных і выходных станаў выбудоўвацца - для ў асноўным любую колькасць кубікаў - але я думаю, што функцыянальнае абмежаванне, што функцыя прымяняецца да асобных валкамі, а затым сумуюцца, разбурае вашу здольнасць адэкватна адрозніваць паміж станамі. Пакуль не ясна, якім чынам вы збіраецеся пазбавіцца ад карэляцыі паміж сумай $ F $ і сума ў $ G $, але гэта таксама не адразу відавочна для мяне, як даказаць, што яны заўсёды звязаныя паміж сабой. Можа быць, ёсць група тэорыі аргумент тут ахайна?

0
дададзена
Ідэя «неўпарадкаваных» выснову, што $ (а, б) $ і $ (Ь, а) $ прымаюцца быць тое ж самае - што тое, што я спрабаваў атрымаць у адказ пад FONS '. Такім чынам, для двух костак, ёсць 21 уваходаў і 21 выхадаў. Акрамя таго, ваш адказ кажа пра тое, што гэта неабходна, каб лік магчымых уваходаў падзяліць лік магчымых выхадаў. Гэта справядліва, калі ўваход і выхад размяркоўваюцца раўнамерна, а ўваходны сігнал, калі прымаецца ў выглядзе камбінацыі, безумоўна, не размяркоўваецца раўнамерна, таму ўмова не выконваецца. (Напрыклад, $ (6,6,6,6) $ прыходзіць $ $ 24 разоў радзей, чым $ (1,2,3,4) $)
дададзена аўтар Milo Brandt, крыніца
@MiloBrandt Вы маеце рацыю, я няправільна інтэрпрэтаваў тлумачэнні на іншае пытанне, дзе (3,6) і (6,3) дазволеныя быць такім жа вынікам. У мяне склалася ўражанне вы павінны былі быць у стане сказаць, розніцу паміж імі. Мая інтуіцыя, што дзяленне патрабуецца, каб атрымаць якія-небудзь зручнае адлюстраванне, але гэта не павінна быць так.
дададзена аўтар pcsnyder, крыніца