면을 갖는 다이의 독립적 인 롤 에서 식별 가능한 식별 가능한 결과 의 세트 은 요소를 갖는다. 다이는 공정 인 경우에는, 수단은 하나의 롤의 각 결과에 확률 갖는 이러한 결과는 각각 따라서 확률 것이다 독립 수단 이고, 그들이 균일 한 분포를 갖도록$\Omega(d,n)$$n$$d=6$$d^n$$1/d$$(1/d)^n:$$\mathbb{P}_{d,n}.$

다이 의 결과 , 즉 의 요소를 결정하거나 실패를보고 하는 절차 를 고안했다고 가정 해 봅시다. 결과를 얻으려면 반복하십시오.) 그건,$t$$m$$c (=150)$$\Omega(c,m)$

t : Ω ( d , n ) → Ω ( c , m ) ∪ { Failure } .

$$t:\Omega(d,n)\to\Omega(c,m)\cup\{\text{Failure}\}.$$

하자 확률 될 것이 실패 결과 비고 어떤 정수배 말하자면$F$$t$$F$$d^{-n},$

F = 잠 ( t ( ω ) = 실패 ) = N Fd – n .

$$F = \Pr(t(\omega)=\text{Failure}) = N_F\, d^{-n}.$$

(나중에 참조 할 수 있도록 실패하지 않기 전에 를 호출해야하는 예상 횟수 는 )$t$$1/(1-F).$

요건 이러한 결과 것을 균일하고 독립적 인 조건 에서 실패 수단보고하지 즉 의미에서 보존 확률이 모든 이벤트$\Omega(c,m)$t t A ⊂ Ω ( c , m ) ,$t$$t$$\mathcal{A}\subset\Omega(c,m),$

P d , n ( t * A )1 − F =Pc,m(A)

$$\frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) \tag{1}$$

어디

t ∗ ( A ) = { ω ∈ Ω ∣ t ( ω ) ∈ A }

$$t^{*}\left(\mathcal A\right) = \{\omega\in\Omega\mid t(\omega)\in\mathcal{A}\}$$

프로 시저 가 이벤트 할당 하는 다이 롤 세트입니다$t$.$\mathcal A.$

원자력 이벤트 . 확률은 이어야합니다 ( 와 관련된 주사위 롤 )에 요소 가 있다고 합시다 . 이됩니다$\mathcal A = \{\eta\}\subset\Omega(c,m)$$c^{-m}.$$t^{*}\left(\mathcal A\right)$$\eta$$N_\eta$$(1)$

N η d – n1 − N F d − n = P d , n ( t * A )1 − F =Pc,m(A)=c−m.

$$\frac{N_\eta d^{-n}}{1 - N_F d^{-n}} = \frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) = c^{-m}.\tag{2}$$

가 모두 정수 과 같다는 것은 즉각이다$N_\eta$$N.$ 가장 효율적인 절차를 찾아야한다 비 장애의 예상 수 의 롤 당 다이 양면 IS를$t.$씨$c$

1m (1–F).

$$\frac{1}{m}\left(1 - F\right).$$

두 가지 즉각적이고 명백한 의미가 있습니다. 하나는 이 커질 때 작게 유지할 수 있다면 실패보고의 효과는 무의미 하다는 것 입니다. 다른 하나는 주어진 ( 시뮬레이션을 위해 다이 의 롤 수 )에 대해 를 가능한 작게 만들고 싶습니다 .$F$$m$$m$$c$$F$

분모를 지우고 를 자세히 살펴 보겠습니다 .$(2)$

N c m = d n – N F > 0.

$$N c^m = d^n - N_F \gt 0.$$

이것은 (결정 주어진 상황에서 그것이 분명하게 ), 함으로써 가능한 한 작게 만들어진다 최대의 다중 동일 보다 작거나 같음 우리는 이것을 가장 큰 정수 함수 (또는 “floor”) 로 쓸 수 있습니다.$c,d,n,m$$F$$d^n-N_F$$c^m$$d^n.$$\lfloor*\rfloor$

N = ⌊ d nc m ⌋.

$$N = \lfloor \frac{d^n}{c^m} \rfloor.$$

마지막으로 은 중복성 을 측정하기 때문에 효율성을 높이기 위해 가능한 한 작아야 한다는 것이 분명합니다 . 구체적으로, 다이 의 하나의 롤을 생성하는데 필요한 다이 의 예상 롤 수 는$N$t d c$t$$d$$c$

N × nm ×11 – F .

$$N \times \frac{n}{m} \times \frac{1}{1-F}.$$

따라서 고효율 절차에 대한 우리의 탐색은 이 일부 전력 과 거의 같거나 거의 크지 않은 경우에 중점을 두어야합니다$d^n$$c^m.$

주어진 와 대해,이 접근법이 완벽한 효율에 근접한 배수 의 시퀀스가 있음을 보여 주면서 분석이 끝납니다 . 이는 이 한계에서 에 접근 하는 을 찾는 것입니다 자동으로 보장 ). 이러한 하나의 시퀀스 취함으로써 얻어진다 및 판단$d$$c,$$(n,m)$$(n,m)$$d^n/c^m \ge 1$$N=1$$F\to 0$$n=1,2,3,\ldots$

m = ⌊ n 로그 d로그 c ⌋.

$$m = \lfloor \frac{n\log d}{\log c} \rfloor.\tag{3}$$

증거는 간단합니다.

이것은 우리가 원래 롤하고자 때 꼭 시간의 충분히 큰 수를 다이 양면 우리 시뮬레이션 기대할 수를 거의 의 결과 (A)의 롤 당 다이 양면 . 마찬가지로$d$$n,$$\log d / \log c = \log_c d$$c$

다수의 시뮬레이션 할 수 (A)의 독립적 인 롤 적정에 사용한 다이 양면 평균하여 다이 양면 결과 당 롤 선택하여 임의로 작게 할 수 충분히 커야한다.$m$$c$$d$$\log(c)/\log(d) + \epsilon = \log_d(c) + \epsilon$$\epsilon$$m$

---

예제와 알고리즘

질문에서 이고 .$d=6$$c=150,$

로그 d ( c ) = 로그 ( c )로그 ( d ) ≈2.796489.

$$\log_d(c) = \frac{\log(c)}{\log(d)} \approx 2.796489.$$

따라서 가능한 최상의 절차는 각 결과 를 시뮬레이트하기 위해 평균 롤 이상이 필요합니다 .$2.796489$d6d150

분석은이를 수행하는 방법을 보여줍니다. 우리는 그것을 수행하기 위해 숫자 이론에 의지 할 필요가 없습니다 : 우리는 단지 과 의 거듭 제곱을 도표화 하고 비교하여 은 가깝습니다. 이 무차별 힘 계산은 쌍을 제공합니다$d^n=6^n$$c^m=150^m$$c^m \le d^n$$(n,m)$

( n , m ) ∈ { ( 3 , 1 ) , ( 14 , 5 ) , … }

$$(n,m) \in \{(3,1), (14,5), \ldots\}$$

예를 들어 숫자에 해당

( 6 n , 150 m ) ∈ { ( 216 , 150 ) , ( 78364164096 , 75937500000 ) , … } .

$$(6^n, 150^m) \in \{(216,150), (78364164096,75937500000), \ldots\}.$$

첫 번째 경우에서 는 a의 3 개의 롤 결과의 을 실패에 연관 시키고 다른 결과는 각각 a의 단일 결과와 연관 될 것이다 . $t$$216-150=66$d6$150$d150

두 번째 경우에서 는 14 롤의 결과 중 을 실패 에 연결하고 ( 약 3.1 %)-5 개의 결과 시퀀스를 출력합니다 .$t$$78364164096-75937500000$d6d150

구현하는 간단한 알고리즘$t$ d 0 , 1 , … , d – 1 c 0 , 1 , … , c – 1. n n d . c . m m t 의 라벨면 도면 부호 다이 양면 과의 얼굴 도면 부호 다이 양면첫 번째 다이 의 롤은 베이스 에서 자리 숫자 로 해석됩니다 이것은 밑 의 숫자로 변환됩니다 최대 자릿수 가 있으면 마지막 자릿수 의 순서 가 출력됩니다. 그렇지 않으면, 는 재귀 적으로 호출하여 Failure를 리턴합니다.$d$$0,1,\ldots, d-1$$c$$0,1,\ldots, c-1.$$n$$n$$d.$$c.$$m$$m$$t$

훨씬 더 긴 시퀀스 의 경우 의 연속 분수 확장의 다른 모든 수렴 을 고려하여 적합한 쌍 을 찾을 수 있습니다 연속 분수 이론은 이러한 수렴이 보다 작고 클 때 사이에서 번갈아 나타난다는 것을 보여줍니다 ( 가 이미 합리적이지 않다고 가정 ). 보다 작은 것을 선택하십시오$(n,m)$$n/m$$x=\log(c)/\log(d).$$x$$x$$x.$

문제에서 처음 몇 가지 수렴은

3,14/5,165/59,797/285,4301/1538,89043/31841,279235/99852,29036139/10383070….

$$3, 14/5, 165/59, 797/285, 4301/1538, 89043/31841, 279235/99852, 29036139/10383070 \ldots.$$

마지막 경우, 29,036,139 롤의 a d6시퀀스는d150 미만의 실패율을 가진 10,383,070 롤의 시퀀스를 생성하여 2.79649 의 효율로 점근 적 한계에서 없습니다.$2\times 10^{-8},$$2.79649$

---

답변