shlomi-fish-homepage / t2 / MathVentures / 3d-outof-4d-mathml.xhtml.wml

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
#include "prelude.wml"
<define-tag latemp_html_doctype>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0//EN"
"http://www.w3.org/Math/DTD/mathml2/xhtml-math11-f.dtd" >
</define-tag>
#include "driver.wml"

<latemp_subject "Combinatorics and the art of Dungeons and Dragons" />

<p>
I used to play “Advanced Dungeons &amp; Dragons” in the 8th and 9th grades. I
quit, though, but many of my friends continued to play a long time
afterwards. In AD&amp;D (that’s the commonly used acronym for the game’s name),
the amount a character is skilled in certain abilities is determined by a
number ranging from 3 to 18. This number is normally generated by rolling 3
dice and summing up the numbers on their sides. That way, high or low
numbers are considerably less frequent then mid-range ones.
</p>

<p>
Yet, this method, which is highly random, often results that the scores are
unsuitable for what the player planned the character to be or simply too
low. Therefore, there are several alternative methods to generate scores
which are better as far as the player is concerned. One of the common ones,
which is described in the game’s manual goes like that: instead of three
dice, four dice are rolled. Then, the three highest die-scores are summed
and together add up to the ability number.
</p>

<p>
One day, my friend who was a game-master at that time called and asked me if
I could tell him what was the average result which is generated by this
method. I couldn’t tell him right away, but he said that he wrote a computer
program to check it, and it ended up around 12.24 . He went on to say that in
his opinion this average was not too high, so he will probably allow the
members of the new team he was going to lead to use that method.
</p>

<p>
Anyway, he still wondered if anyone could think of a mathematical way to calculate
it. I didn’t know or heard of any at that time so I told him that I didn’t
know. He also said that he asked another acquaintance of us, who had already
began his maths studies at the university if he could tell him, but he didn’t
know either.
</p>

<p>
In any case, I thought about it for a while and after a month or so came to a
solution. I presented this problem to other people who seemed interested at
solving maths riddles at various times since. Some of them managed to solve
it, but I didn’t find a more elegant way than what I thought of.
</p>

<p>
Before you see my answer, here is a summary of the problem. You may try to
figure it yourself, before looking at my solution:
</p>

<table border="1">
<tr><td>
<p>
<b>1.</b> Throw 4 dice, sum the numbers they generated and subtract the
lowest value from the sum. (if there is more than one die with the lowest
value, subtract it only once). What is the average number of such throws?
</p>

<p>
More generally, one can ask:
<b>2.</b> Throw n dice, each evenly generating values in the range 1 .. m,
sum them, and subtract the number of the lowest die. What is the average of
the solutions of this throw? (the expression is dependant on n and m.)
</p>

<p>
And yet more generally:
<b>3.</b> Throw n dice each in the range 1..m, sum them and subtract the p
lowest dice (p &lt; n). What is the average outcome of this throw?
</p>

</td></tr>
</table>

<p>
The solution can be found some space below:
</p>

<longblank />

<h2>Solution:</h2>


<!--l. 15--><p class="noindent" >Like I said, it did not come to me right away and I had to think about it for a while. I pondered various
methods, and then came to think about the question this way:
</p><!--l. 19--><p class="noindent" >In each throw the numbers 1..6 can be subtracted. I first realized that I could immediately subtract 1 from all
<!--l. 20--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
></math> of the
possible throws, because one always subtract <span
class="cmbx-10">at least </span>1. Furthermore, when is another 1 point subtracted from the
final sum? Obviously this is the case when 2 or more points are subtracted. When does it happen? It happens when
all the dice are bigger than 1. (or else 1 would have been subtracted.) Since all the dice are in the range 2-6 there are
<!--l. 25--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>5</mn></mrow><mrow
><mn>4</mn></mrow></msup
></math>
different possibilities for this case.
</p><!--l. 28--><p class="noindent" >The next point is subtracted when all the dice are in the range 3-6, hence
<!--l. 29--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>4</mn></mrow><mrow
><mn>4</mn></mrow></msup
></math>
possibilities and so on. Now, to calculate the total, let&#x2019;s start from the sum of all
possible throws of 4 dice, without the minimal die removed. This sum is equal to
<!--l. 31--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-bin">&#x22C5;</mo> <mn>1</mn><mn>4</mn> <mo
class="MathClass-rel">=</mo> <mn>1</mn><mn>8</mn><mn>1</mn><mn>4</mn><mn>4</mn></math>. Then, let&#x2019;s remove
<!--l. 31--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-rel">=</mo> <mn>1</mn><mn>2</mn><mn>9</mn><mn>6</mn></math> because of the first
point removed, <!--l. 32--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>5</mn></mrow><mrow
><mn>4</mn></mrow></msup
></math>
because of the second point etc. Eventually we get:
</p><!--l. 35--><p class="noindent" ><!--l. 35--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-bin">&#x2217;</mo> <mn>1</mn><mn>4</mn> <mo
class="MathClass-bin">&#x2212;</mo> <msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-bin">&#x2212;</mo> <msup><mrow
><mn>5</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-bin">&#x2212;</mo> <msup><mrow
><mn>4</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-bin">&#x2212;</mo> <msup><mrow
><mn>3</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-bin">&#x2212;</mo> <msup><mrow
><mn>2</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-bin">&#x2212;</mo> <msup><mrow
><mn>1</mn></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-rel">=</mo> <mn>1</mn><mn>5</mn><mn>8</mn><mn>6</mn><mn>9</mn></math>
</p><!--l. 37--><p class="noindent" >To find the average, all one has to do is divide it by
<!--l. 37--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
></math>, which is the number
of individual throws. <!--l. 38--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mfrac><mrow
><mn>1</mn><mn>5</mn><mn>8</mn><mn>6</mn><mn>9</mn></mrow>
  <mrow
><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
></mrow></mfrac>    <mo
class="MathClass-rel">=</mo> <mn>1</mn><mn>2</mn><mo
class="MathClass-punc">.</mo><mn>2</mn><mn>4</mn></math>,
which is also the number that my friend&#x2019;s program returned.
</p><!--l. 41--><p class="noindent" >To generalise it for n dice each having the numbers 1..m on its side (AD&#x0026;D) also involves
using dice with 4, 8, 10,12, 20 and sometimes 100 sides. :-)) all one has to do is replace
<!--l. 43--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mn>6</mn></math> with
<!--l. 43--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mi
>n</mi></math> and
<!--l. 43--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mn>4</mn></math> with
<!--l. 43--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mi
>m</mi></math>
where appropriate. One should remember that the average throw for an individual die of 1..m is
<!--l. 45--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mfrac><mrow><mn>1</mn> <mo
class="MathClass-bin">+</mo> <mi
>m</mi></mrow>
  <mrow><mi
>m</mi></mrow></mfrac>  </math> and for
n such dice <!--l. 46--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mfrac><mrow><mi
>n</mi> <mfenced separators=""
open="("  close=")" ><mrow><mn>1</mn> <mo
class="MathClass-bin">+</mo> <mi
>m</mi></mrow></mfenced></mrow>
   <mrow><mi
>m</mi></mrow></mfrac>    </math>.
We eventually get to:
</p><!--l. 48--><p class="noindent" ><!--l. 48--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mfrac><mrow
><mfenced separators=""
open="("  close=")" ><mrow><mfrac><mrow
><msup><mrow
><mi
>m</mi></mrow><mrow
><mi
>n</mi></mrow></msup
><mo
class="MathClass-bin">&#x22C5;</mo><mi
>n</mi><mo
class="MathClass-bin">&#x22C5;</mo><mfenced separators=""
open="("  close=")" ><mrow><mn>1</mn><mo
class="MathClass-bin">+</mo><mi
>m</mi></mrow></mfenced></mrow>
     <mrow
><mi
>m</mi></mrow></mfrac>   </mrow></mfenced><mo
class="MathClass-bin">&#x2212;</mo><msup><mrow
><mi
>m</mi></mrow><mrow
><mi
>n</mi></mrow></msup
><mo
class="MathClass-bin">&#x2212;</mo><msup><mrow
><mfenced separators=""
open="("  close=")" ><mrow><mi
>m</mi><mo
class="MathClass-bin">&#x2212;</mo><mn>1</mn></mrow></mfenced></mrow><mrow
><mi
>n</mi></mrow></msup
><mo
class="MathClass-bin">&#x2212;</mo><msup><mrow
><mfenced separators=""
open="("  close=")" ><mrow><mi
>m</mi><mo
class="MathClass-bin">&#x2212;</mo><mn>2</mn></mrow></mfenced></mrow><mrow
><mi
>n</mi></mrow></msup
><mo
class="MathClass-bin">&#x2212;</mo><msup><mrow
><mfenced separators=""
open="("  close=")" ><mrow><mi
>m</mi><mo
class="MathClass-bin">&#x2212;</mo><mn>3</mn></mrow></mfenced></mrow><mrow
><mi
>n</mi></mrow></msup
><mo
class="MathClass-punc">.</mo><mo
class="MathClass-punc">.</mo><mo
class="MathClass-punc">.</mo><mo
class="MathClass-bin">&#x2212;</mo><msup><mrow
><mn>1</mn></mrow><mrow
><mi
>n</mi></mrow></msup
></mrow>

                           <mrow
><msup><mrow
><mi
>m</mi></mrow><mrow
><mi
>n</mi></mrow></msup
></mrow></mfrac>                </math>
</p><!--l. 53--><p class="noindent" >Eliminating the next smallest die, and the other dice in order, is a bit more tricky. As a matter of fact, it took
me two more years to finally come up with a solution. (not that I spent all my time thinking about
it)
</p><!--l. 57--><p class="noindent" >The basic idea is this: regarding the first point of the second least die, it&#x2019;s obvious that we still have to remove
<!--l. 58--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
></math> from
the total. About the second point: it is removed only if all the dice, except maybe one has a face value of 2 or
more. Phrased in a different way it is removed:
     </p><ol  class="enumerate1" >
     <li
  class="enumerate" id="x1-3x1">If there are 4 dice in the range 2..6. <span
class="cmbx-10">Or</span>:
     </li>
     <li
  class="enumerate" id="x1-5x2">If there are 3 dice in the range 2..6 and one die whose value is 1.</li></ol>
<!--l. 67--><p class="noindent" >The conditions for the other 4 cases are similar: if the additional point is the Kth than there could be either 4
dice in the range K..6 or 3 dice in the range K..6 and one die in the range 1..(K-1). To evaluate it
mathematically, I&#x2019;ll use the standard formulas and eventually get to:

</p><!--l. 72--><p class="noindent" ><!--l. 72--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
> <mfenced separators=""
open="("  close=")" ><mrow><mn>6</mn> <mo
class="MathClass-bin">&#x2212;</mo> <mi
>K</mi> <mo
class="MathClass-bin">+</mo> <mn>1</mn></mrow></mfenced></mrow><mrow
><mn>4</mn></mrow></msup
> <mo
class="MathClass-bin">+</mo> <mfenced separators=""
open="("  close=")" ><mrow><msup><mrow
><mfenced separators=""
open="("  close=")" ><mrow><mn>6</mn> <mo
class="MathClass-bin">&#x2212;</mo> <mi
>K</mi> <mo
class="MathClass-bin">+</mo> <mn>1</mn></mrow></mfenced></mrow><mrow
><mn>3</mn></mrow></msup
> <mo
class="MathClass-bin">&#x22C5;</mo><mfenced separators=""
open="("  close=")" ><mrow><mi
>K</mi> <mo
class="MathClass-bin">&#x2212;</mo> <mn>1</mn></mrow></mfenced></mrow></mfenced> <mo
class="MathClass-bin">&#x22C5;</mo> <mn>4</mn></math>
</p><!--l. 75--><p class="noindent" >If we subtract <!--l. 75--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
></math>
and those 5 sums from the total sum that was acquired in the previous stage, we&#x2019;d get to the
new total with the two least dice removed on each throw. Divide it by the number of throws -
<!--l. 77--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
></math> - and
we get the new average. The grand formula, then, is:
</p><!--l. 80--><p class="noindent" ><!--l. 80--><math
 xmlns="http://www.w3.org/1998/Math/MathML" display="inline" ><mfrac><mrow
><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
><mo
class="MathClass-bin">&#x22C5;</mo><mn>1</mn><mn>4</mn><mo
class="MathClass-bin">&#x2212;</mo><munderover accentunder="false" accent="false"><mrow
><mo
class="MathClass-op">&#x2211;</mo></mrow><mrow
>
<mi
>i</mi><mo
class="MathClass-rel">=</mo><mn>1</mn></mrow><mrow
><mn>6</mn></mrow></munderover
> <mfenced separators=""
open=""  close="" ><mrow><msup><mrow
><mi
>i</mi></mrow><mrow
><mn>4</mn></mrow></msup
> </mrow></mfenced><mo
class="MathClass-bin">&#x2212;</mo><munderover accentunder="false" accent="false"><mrow
><mo
class="MathClass-op">&#x2211;</mo></mrow><mrow
>
<mi
>i</mi><mo
class="MathClass-rel">=</mo><mn>1</mn></mrow><mrow
><mn>6</mn></mrow></munderover
> <mfenced separators=""
open="["  close="]" ><mrow><msup><mrow
> <mfenced separators=""
open="("  close=")" ><mrow><mn>6</mn><mo
class="MathClass-bin">&#x2212;</mo><mi
>i</mi><mo
class="MathClass-bin">+</mo><mn>1</mn></mrow></mfenced></mrow><mrow
><mn>4</mn></mrow></msup
><mo
class="MathClass-bin">+</mo><mfenced separators=""
open="("  close=")" ><mrow><msup><mrow
><mfenced separators=""
open="("  close=")" ><mrow><mn>6</mn><mo
class="MathClass-bin">&#x2212;</mo><mi
>i</mi><mo
class="MathClass-bin">+</mo><mn>1</mn></mrow></mfenced></mrow><mrow
><mn>3</mn></mrow></msup
><mo
class="MathClass-bin">&#x22C5;</mo><mfenced separators=""
open="("  close=")" ><mrow><mi
>i</mi><mo
class="MathClass-bin">&#x2212;</mo><mn>1</mn></mrow></mfenced></mrow></mfenced><mo
class="MathClass-bin">&#x22C5;</mo><mn>4</mn></mrow></mfenced></mrow>

                                 <mrow
><msup><mrow
><mn>6</mn></mrow><mrow
><mn>4</mn></mrow></msup
></mrow></mfrac>                 </math>
</p><!--l. 86--><p class="noindent" >From the 3rd least dice onward, this method gets more and more complicated because we have to consider 3
different cases for every point we subtract, 4 cases for the fourth die, and so on. If anyone has an idea on how to
improve this method, or can suggest an alternative method which is simpler as more and more dice are removed
by order, please let me know and I&#x2019;ll post it here.
</p><!--l. 93--><p class="noindent" >I, for my part, am no longer interested in this problem, and do not deal with it, at least not until I extend my
knowledge in Combinatorics and the Theory of Probability.
</p><!--l. 97--><p class="noindent" >A final note: you can find a C program, not unlike the one my friend used, that calculates the average of such
throws <span
class="cmbx-10">TODO Link me here</span>. It can do that for any number of dice with any number of sides, and while
eliminating any number of minimal dice. &#x00A1;/p&#x00BF;
</p><!--l. 104--><p class="noindent" >The program is quite stupid and merely iterates over all the different throws, and adds the sum of
every throw to the total. It becomes less efficient as the number of sides and/or the number of dice
increases.
</p><!--l. 109--><p class="noindent" >Writing a program that implements my method <span
class="cmbx-10">for any number of removed dice </span>is a bit complicated
because the formula itself gets more and more complicated. Maybe I&#x2019;ll get to it one day.
</p>


<h2>Links</h2>

<ul>
<li>
<a href="http://carnalreason.org/2006/07/29/a-mathematical-diversion/">An alternate solution in the Carnal Reason blog</a>
</li>
</ul>
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.