https://www.explainxkcd.com/wiki/api.php?action=feedcontributions&feedformat=atom&user=Lgstarnexplain xkcd - User contributions [en]2026-05-19T21:28:36ZUser contributionsMediaWiki 1.30.0https://www.explainxkcd.com/wiki/index.php?title=1685:_Patch&diff=3583891685: Patch2024-12-01T15:50:01Z<p>Lgstarn: /* Explanation */ Adding additional explanation of isPrimeRegex</p>
<hr />
<div>{{comic<br />
| number = 1685<br />
| date = May 25, 2016<br />
| title = Patch<br />
| image = patch.png<br />
| titletext = My optimizer uses content-aware inpainting to fill in all the wasted whitespace in the code, repeating the process until it compiles.<br />
}}<br />
<br />
==Explanation==<br />
{{w|Adobe Photoshop}} is a commonly used application for image manipulation. One of its features is the Patch tool, which allows the user to overwrite parts of the image, replacing them with a copy of another area of the same image. It is often used for “patching up” photographs by overwriting scratches or other visible damage to the photo. Another of Photoshop’s features is “content-aware fill”, which could also be described as “content-aware inpainting”. It works similarly to the Patch tool, but automatically generates a replacement texture from the area surrounding the deleted part instead of copying a user-specified area exactly.<br />
<br />
{{w|GNU}} {{w|Patch (Unix)|patch}} is a program that replaces only parts of code with an updated version, without requiring the user to download the entire source code. Here, it appears the author was told to “patch” the code but used Photoshop to do this instead of GNU patch, with devastating results.{{citation needed}} Although the title text suggests that if you did this enough times the code would eventually compile, this would be so unlikely to happen that it is effectively imposible. In fact, Photoshop could only edit an image of the text and not the text itself. However, it could work if optical character recognition (OCR) were integrated into the workflow as well.<br />
<br />
The comic blurs the difference between {{w|text_file|text}} (in which letters and symbols represent discrete values, such as 65 being the number for the letter A in the ASCII encoding standard, and it's relatively easy for a program compiler to interpret combinations of these values as keywords and other programming constructs) and {{w|Raster_graphics|graphics}} (where the letters and symbols in the comic are actually represented by a pattern of colored dots), playing with the idea that the ''patch'' metaphor can be used on both (although with different meanings). There are common and straightforward processes for converting text information to images, such as printing, which can convert text to a graphics format very faithfully. The reverse, however, requires the use of {{w|optical character recognition}} (OCR), which attempts to figure out which letter or symbol certain patterns of dots "look like". OCR could be effective in converting some of the image in the comic back to usable text; however, it would fail on some of those patterns that have been mangled and don't look like any existing characters or symbols. A compiler can only operate on text data, so converting the graphic back into text would be a requirement to even begin to attempt to compile it, a step omitted in the title text.<br />
<br />
The code appears to be written in {{w|Python_(programming_language)|Python}}, a programming language often referred to in xkcd, such as in [[353: Python]]. A few of the function names that can be recognized are "isPrime" and "quicksort", both elementary programming algorithms. It was also apparently originally edited using a Python-aware programming text editor, which is able to use different colors for different programming elements. For example, it appears to use red for keywords, blue for variables, and black for other elements; however, because of the mangling from the use of the wrong patching program, that doesn't appear to be consistent. Since the patching replaced graphical elements rather than whole characters, there are examples of symbols that are combinations of two different characters, and when the original two characters were rendered in different colors the resulting non-character could be in two colors, or the resulting "word" might be rendered in multiple colors.<br />
<br />
The comic brings to attention the high rate of Adobe Photoshop piracy. GNU Patch is available for free, even [http://gnuwin32.sourceforge.net/packages/patch.htm for Windows], and Mac OS X. So the comic implies that Adobe Photoshop, a subscription to which costs $20/month, is more available than GNU patch. According to [http://blog.epicedits.com/2008/03/28/60-of-photoshop-users-are-pirates/ this poll], 58% of Photoshop copies were pirated.<br />
<br />
The title text also explains that the patch used the content-aware inpainting to fill in all the wasted whitespace in the code. In most programming languages, whitespace is necessary to separate words, so this would combine words that shouldn’t be combined and create invalid code. Since the code in the image is Python, the code will be messed up even more, because Python uses whitespace as a part of its programming syntax. For example, statements are separated by newlines instead of by semicolons (;), and indentation is used instead of brackets to determine the scope of each section of code.<br />
<br />
The original code was likely as follows:<br />
<br />
<font color="red">import</font> re<br />
<font color="red">def<font color="purple"> isPrime</font></font>(n):<br />
<font color="red">if </font>n<font color="red"><=</font><font color="#44A1FF">1</font>:<br />
<font color="red">return</font> <font color="#44A1FF">False</font><br />
<font color="red">for</font> i <font color="red">in <font color="#44A1FF">range</font></font>(<font color="#44A1FF">2</font>, <font color="#44A1FF">int</font>(n<font color="red">**</font><font color="#44A1FF">0.5</font>)<font color="red">+</font><font color="#44A1FF">1</font>):<br />
<font color="red">if</font> n<font color="red">%</font>i<font color="red">==<font color="#44A1FF">0</font></font>:<br />
<font color="red">return<font color="#44A1FF"> False</font></font><br />
<font color="red">return <font color="#44A1FF">True</font></font><br />
<font color="red">def <font color="purple">isPrimeRegex</font></font>(n):<br />
<font color="red">if</font> re.match(<font color="red">r</font><font color="blue">'</font><font color="#44A1FF">^</font><font color="blue">1</font><font color="red">?<font color="#44A1FF">$</font>|<font color="#44A1FF">^</font><font color="blue">(11</font>+?<font color="blue">)</font><font color="green">\1+</font><font color="#44A1FF">$</font></font><font color="blue">'</font>, <font color="blue">'1'</font><font color="red">*</font>n): <br />
<font color="red">return <font color="#44A1FF">False</font><br />
<font color="red">return<font color="#44A1FF"> True</font></font></font><br />
<font color="red">def<font color="purple"> quicksort</font></font>(a):<br />
<font color="red">if <font color="#44A1FF">len</font></font>(a) <font color="red">< <font color="#44A1FF">2</font></font>:<br />
<font color="red">return </font>a<br />
pivot<font color="red">=</font>a[<font color="#44A1FF">0</font>]<br />
l<font color="red">=</font>[i<font color="red"> for</font> i <font color="red">in</font> a <font color="red">if</font> i<font color="red"><</font>pivot]<br />
r<font color="red">=</font>[i<font color="red"> for</font> i <font color="red">in</font> a <font color="red">if</font> i<font color="red">></font>pivot]<br />
mid<font color="red">=</font>[pivot]<font color="red">*</font>(<font color="#44A1FF">len</font>(a)<font color="red">-</font>(<font color="#44A1FF">len</font>(l)<font color="red">+</font><font color="#44A1FF">len</font>(r)))<br />
<font color="red">return </font>quicksort(l)<font color="red">+</font>mid<font color="red">+</font>quicksort(r)<br />
<br />
isPrime and quicksort are standard python implementations of simple algorithms (although you would not generally write a sorting algorithm in python as there are built-in algorithms available). isPrimeRegex uses the [https://docs.python.org/library/re.html re module] to detect if a number is prime by seeing if a string containing that many 1s can be matched to 2 or more copies of some string containing at least 2 1s. This works by transforming the number into the [https://en.wikipedia.org/wiki/Unary_numeral_system unary numeral system] and seeing if there is a repeating patterns of 1s, i.e. the number is [https://en.wikipedia.org/wiki/Composite_number composite] and thus not prime. In more detail, the expression <font color="blue">'1'</font><font color="red">*</font>n converts the whole number n into a string of <font color="blue">'1'</font> repeated n times. The regex then matches against this string. The first regex component <font color="#44A1FF">^</font><font color="blue">1</font><font color="red">?</font><font color="#44A1FF">$</font> finds the edge cases of 0 and 1 (not prime) as <font color="#44A1FF">^</font> is the beginning of the line, <font color="blue">1</font><font color="red">?</font> means one or zero 1s, and <font color="#44A1FF">$</font> is the end of the line. This matches only a blank string (the number 0) or a <font color="blue">'1'</font> (the number 1). The second regex expression is separated from the first by |, a logical "or", so either expression will cause a match. The regex <font color="#44A1FF">^</font><font color="blue">(11</font>+?<font color="blue">)</font><font color="green">\1+</font><font color="#44A1FF">$</font> selects for a repeating pattern (the content inside the parenthesis) an additional one or more times as indicated by <font color="green">\1+</font>. The pattern inside the parenthesis is a string of 1s longer than 2 (thus filtering out the edge case of 2, which is a prime number) using the property of composite numbers that they must be two non-prime numbers multiplied together. Altogether, the entire line between <font color="#44A1FF">^</font> and <font color="#44A1FF">$</font> must be precisely a pattern of 2 or more ones with this pattern repeated 1 or more times. If either of these two statements is true (0 or 1 or a repeated pattern greater than length 2), the number is not a prime. Interesting benchmarks of this "useless skill" isPrimeRegex method in comparison to the naive isPrime method can be found [https://geelaw.blog/entries/regex-prime-js-benchmark/ here].<br />
<br />
The comic two comics back [[1683: Digital Data]], also related to turning digital data into bad copies. Less than a month before quicksort was mentioned in [[1667: Algorithms]], and a month before that another "easy" solution to a programming problem was released in [[1654: Universal Install Script]].<br />
<br />
Using a Photoshop tool for a task it is not intended for was also used in [[1784: Bad Map Projection: Liquid Resize]], where [https://helpx.adobe.com/photoshop/using/content-aware-scaling.html Photoshop's content-aware resizing tool] was a very questionable choice to use for a Map Projection.<br />
<br />
==Transcript==<br />
:[The panel displays part of a code, in five different colors (red, purple, light blue, blue, and green) as well as normal black text, which due to image editing is difficult to read. The first and last lines are partly obscured by the frame of the panel. Here below is an attempt to transcribe the code, using the sign "¤" for anything not easily transcribed. Feel free to add other signs instead of these that look more like the one in the image (and also improve the attempted transcription if possible).]<br />
<font color="red">impoɞt</font> <font color="purple">ne</font><br />
<font color="red">doo</font><font color="purple">PisPʂnme</font>(n):<br />
<font color="red">⫠</font>(<font color="purple">¤</font>n<font color="red"><</font>n,<font color="#44A1FF">1</font>:<br />
<font color="red">retɐrn</font> <font color="#44A1FF">F</font>(<font color="#44A1FF">ise</font><br />
<font color="red">for</font> i <font color="red">ir</font><font color="#44A1FF">arar𝞬e</font>(<font color="#44A1FF">2</font>, <font color="#44A1FF">ninߙ</font> <font color="red">*</font>n<font color="red">**</font>n<font color="red">+</font><font color="#44A1FF">5</font>)<font color="red">+</font><font color="#44A1FF">5</font>):<br />
<font color="red">if</font> n i<font color="red">==</font><font color="#44A1FF">0</font><br />
<font color="red">re力¤𝑟nr</font><font color="#44A1FF">₅ɵlsel</font>:<br />
<font color="red">re</font><font color="purple">𝗿</font><font color="red">⃓rn </font><font color="#44A1FF">True</font><br />
<font color="red">defe</font><font color="purple">𝟧isPrimϵieg˓x</font>(c<font color="purple">x</font><br />
<font color="red">if</font> <font color="purple">g</font>ƨ<font color="purple">¤i</font>natc<font color="purple">x</font>(<font color="red">r</font>'<font color="#44A1FF">^</font><font color="blue">(1</font><font color="red">?| ?.</font><font color="blue">1</font><font color="red">+?</font><font color="blue">)</font><font color="lime">\+</font><font color="blue">)</font><font color="#44A1FF">$</font>'<font color="red">*</font>n <font color="blue">⎞1'</font><font color="red">*</font>n):<br />
<font color="red">rerɹrn </font><font color="#44A1FF">Fa</font><font color="blue">(</font><font color="#44A1FF"> e</font><br />
<font color="red">ιetu⃓</font><font color="purple">nr</font><font color="#44A1FF">TrꙆ</font><br />
<font color="red">dq</font><font color="purple">⃓ q⃓soʀsor</font><font color="#44A1FF">η</font>(a :<br />
<font color="red">if </font><font color="#44A1FF">¤n</font>(a <font color="red">< </font><font color="#44A1FF">2</font>:<br />
<font color="red">eteturn </font>a<br />
pi<font color="red">=꞊ᵣ f</font>a[<font color="#44A1FF">0</font>]<br />
l<font color="red">=</font>pi<font color="red">=for</font> j <font color="red">ın</font> a i<font color="red"><</font> i<font color="red"><</font>pi<font color="red"><</font>(t]<small>(</small>)<br />
r<font color="red">=</font>[ı<font color="red">=for 𝟋 in</font> a) <font color="red">r</font> i<font color="red">></font>viviv]<small>(</small>vo)<br />
mid<font color="red">=</font>[pi[<font color="red">*</font>t]<font color="red">*</font>(<font color="#44A1FF">l</font><font color="red">*</font>t<font color="#44A1FF">ˌ</font>(a)<font color="red">-</font>(<font color="#44A1FF">⟘en</font>pᚆ<font color="#44A1FF">enlen</font>(c)))<br />
<font color="red">r¤lrurrr</font>ikıcksckt(l) <font color="red">+</font> r ¤ ¤quickrprt(r)<br />
<br />
:[Caption below the panel:]<br />
:Protip: If you don't have access to the GNU ''patch'' tool, you can use the Photoshop one.<br />
<br />
{{comic discussion}}<br />
[[Category:Comics with color]]<br />
[[Category:Protip]]<br />
[[Category:Programming]]<br />
[[Category:Photography]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=1685:_Patch&diff=3583871685: Patch2024-12-01T15:05:07Z<p>Lgstarn: /* Explanation */ Adding background on isPrimeRegex</p>
<hr />
<div>{{comic<br />
| number = 1685<br />
| date = May 25, 2016<br />
| title = Patch<br />
| image = patch.png<br />
| titletext = My optimizer uses content-aware inpainting to fill in all the wasted whitespace in the code, repeating the process until it compiles.<br />
}}<br />
<br />
==Explanation==<br />
{{w|Adobe Photoshop}} is a commonly used application for image manipulation. One of its features is the Patch tool, which allows the user to overwrite parts of the image, replacing them with a copy of another area of the same image. It is often used for “patching up” photographs by overwriting scratches or other visible damage to the photo. Another of Photoshop’s features is “content-aware fill”, which could also be described as “content-aware inpainting”. It works similarly to the Patch tool, but automatically generates a replacement texture from the area surrounding the deleted part instead of copying a user-specified area exactly.<br />
<br />
{{w|GNU}} {{w|Patch (Unix)|patch}} is a program that replaces only parts of code with an updated version, without requiring the user to download the entire source code. Here, it appears the author was told to “patch” the code but used Photoshop to do this instead of GNU patch, with devastating results.{{citation needed}} Although the title text suggests that if you did this enough times the code would eventually compile, this would be so unlikely to happen that it is effectively imposible. In fact, Photoshop could only edit an image of the text and not the text itself. However, it could work if optical character recognition (OCR) were integrated into the workflow as well.<br />
<br />
The comic blurs the difference between {{w|text_file|text}} (in which letters and symbols represent discrete values, such as 65 being the number for the letter A in the ASCII encoding standard, and it's relatively easy for a program compiler to interpret combinations of these values as keywords and other programming constructs) and {{w|Raster_graphics|graphics}} (where the letters and symbols in the comic are actually represented by a pattern of colored dots), playing with the idea that the ''patch'' metaphor can be used on both (although with different meanings). There are common and straightforward processes for converting text information to images, such as printing, which can convert text to a graphics format very faithfully. The reverse, however, requires the use of {{w|optical character recognition}} (OCR), which attempts to figure out which letter or symbol certain patterns of dots "look like". OCR could be effective in converting some of the image in the comic back to usable text; however, it would fail on some of those patterns that have been mangled and don't look like any existing characters or symbols. A compiler can only operate on text data, so converting the graphic back into text would be a requirement to even begin to attempt to compile it, a step omitted in the title text.<br />
<br />
The code appears to be written in {{w|Python_(programming_language)|Python}}, a programming language often referred to in xkcd, such as in [[353: Python]]. A few of the function names that can be recognized are "isPrime" and "quicksort", both elementary programming algorithms. It was also apparently originally edited using a Python-aware programming text editor, which is able to use different colors for different programming elements. For example, it appears to use red for keywords, blue for variables, and black for other elements; however, because of the mangling from the use of the wrong patching program, that doesn't appear to be consistent. Since the patching replaced graphical elements rather than whole characters, there are examples of symbols that are combinations of two different characters, and when the original two characters were rendered in different colors the resulting non-character could be in two colors, or the resulting "word" might be rendered in multiple colors.<br />
<br />
The comic brings to attention the high rate of Adobe Photoshop piracy. GNU Patch is available for free, even [http://gnuwin32.sourceforge.net/packages/patch.htm for Windows], and Mac OS X. So the comic implies that Adobe Photoshop, a subscription to which costs $20/month, is more available than GNU patch. According to [http://blog.epicedits.com/2008/03/28/60-of-photoshop-users-are-pirates/ this poll], 58% of Photoshop copies were pirated.<br />
<br />
The title text also explains that the patch used the content-aware inpainting to fill in all the wasted whitespace in the code. In most programming languages, whitespace is necessary to separate words, so this would combine words that shouldn’t be combined and create invalid code. Since the code in the image is Python, the code will be messed up even more, because Python uses whitespace as a part of its programming syntax. For example, statements are separated by newlines instead of by semicolons (;), and indentation is used instead of brackets to determine the scope of each section of code.<br />
<br />
The original code was likely as follows:<br />
<br />
<font color="red">import</font> re<br />
<font color="red">def<font color="purple"> isPrime</font></font>(n):<br />
<font color="red">if </font>n<font color="red"><=</font><font color="#44A1FF">1</font>:<br />
<font color="red">return</font> <font color="#44A1FF">False</font><br />
<font color="red">for</font> i <font color="red">in <font color="#44A1FF">range</font></font>(<font color="#44A1FF">2</font>, <font color="#44A1FF">int</font>(n<font color="red">**</font><font color="#44A1FF">0.5</font>)<font color="red">+</font><font color="#44A1FF">1</font>):<br />
<font color="red">if</font> n<font color="red">%</font>i<font color="red">==<font color="#44A1FF">0</font></font>:<br />
<font color="red">return<font color="#44A1FF"> False</font></font><br />
<font color="red">return <font color="#44A1FF">True</font></font><br />
<font color="red">def <font color="purple">isPrimeRegex</font></font>(n):<br />
<font color="red">if</font> re.match(<font color="red">r</font><font color="blue">'</font><font color="#44A1FF">^</font><font color="blue">1</font><font color="red">?<font color="#44A1FF">$</font>|<font color="#44A1FF">^</font><font color="blue">(11</font>+?<font color="blue">)</font><font color="green">\1+</font><font color="#44A1FF">$</font></font><font color="blue">'</font>, <font color="blue">'1'</font><font color="red">*</font>n): <br />
<font color="red">return <font color="#44A1FF">False</font><br />
<font color="red">return<font color="#44A1FF"> True</font></font></font><br />
<font color="red">def<font color="purple"> quicksort</font></font>(a):<br />
<font color="red">if <font color="#44A1FF">len</font></font>(a) <font color="red">< <font color="#44A1FF">2</font></font>:<br />
<font color="red">return </font>a<br />
pivot<font color="red">=</font>a[<font color="#44A1FF">0</font>]<br />
l<font color="red">=</font>[i<font color="red"> for</font> i <font color="red">in</font> a <font color="red">if</font> i<font color="red"><</font>pivot]<br />
r<font color="red">=</font>[i<font color="red"> for</font> i <font color="red">in</font> a <font color="red">if</font> i<font color="red">></font>pivot]<br />
mid<font color="red">=</font>[pivot]<font color="red">*</font>(<font color="#44A1FF">len</font>(a)<font color="red">-</font>(<font color="#44A1FF">len</font>(l)<font color="red">+</font><font color="#44A1FF">len</font>(r)))<br />
<font color="red">return </font>quicksort(l)<font color="red">+</font>mid<font color="red">+</font>quicksort(r)<br />
<br />
isPrime and quicksort are standard python implementations of simple algorithms (although you would not generally write a sorting algorithm in python as there are built-in algorithms available). isPrimeRegex uses the [https://docs.python.org/library/re.html re module] to detect if a number is prime by seeing if a string containing that many 1s can be matched to 2 or more copies of some string containing at least 2 1s. This works by transforming the number into the [https://en.wikipedia.org/wiki/Unary_numeral_system unary numeral system] and seeing if there is a repeating patterns of 1s, i.e. the number is [https://en.wikipedia.org/wiki/Composite_number composite] and thus not prime. The first regex component filters out the edge cases of 0 and 1. Interesting benchmarks of this "useless skill" isPrimeRegex method in comparison to the naive isPrime method can be found [https://geelaw.blog/entries/regex-prime-js-benchmark/ here].<br />
<br />
The comic two comics back [[1683: Digital Data]], also related to turning digital data into bad copies. Less than a month before quicksort was mentioned in [[1667: Algorithms]], and a month before that another "easy" solution to a programming problem was released in [[1654: Universal Install Script]].<br />
<br />
Using a Photoshop tool for a task it is not intended for was also used in [[1784: Bad Map Projection: Liquid Resize]], where [https://helpx.adobe.com/photoshop/using/content-aware-scaling.html Photoshop's content-aware resizing tool] was a very questionable choice to use for a Map Projection.<br />
<br />
==Transcript==<br />
:[The panel displays part of a code, in five different colors (red, purple, light blue, blue, and green) as well as normal black text, which due to image editing is difficult to read. The first and last lines are partly obscured by the frame of the panel. Here below is an attempt to transcribe the code, using the sign "¤" for anything not easily transcribed. Feel free to add other signs instead of these that look more like the one in the image (and also improve the attempted transcription if possible).]<br />
<font color="red">impoɞt</font> <font color="purple">ne</font><br />
<font color="red">doo</font><font color="purple">PisPʂnme</font>(n):<br />
<font color="red">⫠</font>(<font color="purple">¤</font>n<font color="red"><</font>n,<font color="#44A1FF">1</font>:<br />
<font color="red">retɐrn</font> <font color="#44A1FF">F</font>(<font color="#44A1FF">ise</font><br />
<font color="red">for</font> i <font color="red">ir</font><font color="#44A1FF">arar𝞬e</font>(<font color="#44A1FF">2</font>, <font color="#44A1FF">ninߙ</font> <font color="red">*</font>n<font color="red">**</font>n<font color="red">+</font><font color="#44A1FF">5</font>)<font color="red">+</font><font color="#44A1FF">5</font>):<br />
<font color="red">if</font> n i<font color="red">==</font><font color="#44A1FF">0</font><br />
<font color="red">re力¤𝑟nr</font><font color="#44A1FF">₅ɵlsel</font>:<br />
<font color="red">re</font><font color="purple">𝗿</font><font color="red">⃓rn </font><font color="#44A1FF">True</font><br />
<font color="red">defe</font><font color="purple">𝟧isPrimϵieg˓x</font>(c<font color="purple">x</font><br />
<font color="red">if</font> <font color="purple">g</font>ƨ<font color="purple">¤i</font>natc<font color="purple">x</font>(<font color="red">r</font>'<font color="#44A1FF">^</font><font color="blue">(1</font><font color="red">?| ?.</font><font color="blue">1</font><font color="red">+?</font><font color="blue">)</font><font color="lime">\+</font><font color="blue">)</font><font color="#44A1FF">$</font>'<font color="red">*</font>n <font color="blue">⎞1'</font><font color="red">*</font>n):<br />
<font color="red">rerɹrn </font><font color="#44A1FF">Fa</font><font color="blue">(</font><font color="#44A1FF"> e</font><br />
<font color="red">ιetu⃓</font><font color="purple">nr</font><font color="#44A1FF">TrꙆ</font><br />
<font color="red">dq</font><font color="purple">⃓ q⃓soʀsor</font><font color="#44A1FF">η</font>(a :<br />
<font color="red">if </font><font color="#44A1FF">¤n</font>(a <font color="red">< </font><font color="#44A1FF">2</font>:<br />
<font color="red">eteturn </font>a<br />
pi<font color="red">=꞊ᵣ f</font>a[<font color="#44A1FF">0</font>]<br />
l<font color="red">=</font>pi<font color="red">=for</font> j <font color="red">ın</font> a i<font color="red"><</font> i<font color="red"><</font>pi<font color="red"><</font>(t]<small>(</small>)<br />
r<font color="red">=</font>[ı<font color="red">=for 𝟋 in</font> a) <font color="red">r</font> i<font color="red">></font>viviv]<small>(</small>vo)<br />
mid<font color="red">=</font>[pi[<font color="red">*</font>t]<font color="red">*</font>(<font color="#44A1FF">l</font><font color="red">*</font>t<font color="#44A1FF">ˌ</font>(a)<font color="red">-</font>(<font color="#44A1FF">⟘en</font>pᚆ<font color="#44A1FF">enlen</font>(c)))<br />
<font color="red">r¤lrurrr</font>ikıcksckt(l) <font color="red">+</font> r ¤ ¤quickrprt(r)<br />
<br />
:[Caption below the panel:]<br />
:Protip: If you don't have access to the GNU ''patch'' tool, you can use the Photoshop one.<br />
<br />
{{comic discussion}}<br />
[[Category:Comics with color]]<br />
[[Category:Protip]]<br />
[[Category:Programming]]<br />
[[Category:Photography]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577653015: D&D Combinatorics2024-11-24T13:00:10Z<p>Lgstarn: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation. First, literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number as before. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. These two approaches work well without requiring understanding probabilities, but to achieve the required odds just using two d6 dice, a 2/9 probability can be found by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36 = 2/9). Using a d100 with 89 or higher gives a 22% percent chance as an approximation to 2/9 = 22.222..%, which may be sufficient.<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required total. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577633015: D&D Combinatorics2024-11-24T12:50:29Z<p>Lgstarn: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation. First, literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. These two approaches work well without requiring understanding probabilities, but to achieve the required odds just using two d6 dice, a 2/9 probability can be found by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36 = 2/9). Using a d100 with 89 or higher gives a 22% percent chance as an approximation to 2/9 = 22.222..%, which may be sufficient.<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required total. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577613015: D&D Combinatorics2024-11-24T12:42:26Z<p>Lgstarn: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation. First, literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. These two approaches work well without requiring understanding probabilities, but to achieve the required odds just using two d6 dice, a 2/9 probability can be found by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36 = 2/9). Using a d100 with 89 or higher gives a 22% percent chance as an approximation to 2/9 = 22.222..%, which may be sufficient.<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required numer. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577603015: D&D Combinatorics2024-11-24T12:40:46Z<p>Lgstarn: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation. First, literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. These two approaches work well without requiring understanding probabilities, but to achieve the required odds just using two d6 dice, a 2/9 probability can be found by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36 = 2/9). Using a d100 with 89 or higher gives 22% percent chance as an approximation to 2/9 = 22.222..%.<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required numer. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577593015: D&D Combinatorics2024-11-24T12:39:19Z<p>Lgstarn: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation. First, literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. These two approaches work well without requiring understanding probabilities, but to achieve the required odds just using two d6 dice, a 2/9 probability can be found by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36 = 2/9). Using a d100 with 89 or higher gives 22% percent chance as an approximation to 2/9 = 22.222..%..<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required numer. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577583015: D&D Combinatorics2024-11-24T12:16:03Z<p>Lgstarn: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation. First, literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. Even just using two d6 dice, a 2/9 probability is easily achieved by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36 = 2/9 probability).<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required numer. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577573015: D&D Combinatorics2024-11-24T12:14:32Z<p>Lgstarn: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation. First, literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. Even just using two d6 dice, achieving a 2/9 probability is easily achieved by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36 = 2/9 probability).<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required numer. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577563015: D&D Combinatorics2024-11-24T12:07:43Z<p>Lgstarn: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation. First, literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. Even just using two d6 dice, achieving a 2/9 probability is easily achieved by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36 = 2/9 probability).<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required numer. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to.be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577553015: D&D Combinatorics2024-11-24T12:05:43Z<p>Lgstarn: /* Explanation */ several methods</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There are several much easier ways of implementing this operation: literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. Even just using two d6 dice, achieving a 2/9 probability is easily achieved by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36=2/9 probability).<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required numer. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to.be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577543015: D&D Combinatorics2024-11-24T12:04:14Z<p>Lgstarn: /* Explanation */ Adding "polished" D&D feel argument</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There is a much easier way of implementing the operation: literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution. Even just using two d6 dice, achieving a 2/9 probability is easily achieved by saying Cueball would succeed with a 9, 11, or 12 (4/36, 2/36, and 1/36 probability, respectively, giving 8/36=2/9 probability).<br />
<br />
One could argue that the above solutions do not have the "polished" D&D feel of rolling a certain number of dice, adding them up, and seeing if the result is greater than or equal to a given required numer. This is a commonly used mechanic for difficulty checks, hit calculations, and other such chance-based events in D&D. The DM may feel that this dice format is a requirement, but this approach is far too clunky for most DMs to.be practical. It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward and less time-consuming solutions to this cursed arrow problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarnhttps://www.explainxkcd.com/wiki/index.php?title=3015:_D%26D_Combinatorics&diff=3577533015: D&D Combinatorics2024-11-24T11:31:24Z<p>Lgstarn: /* Explanation */ improving explanation</p>
<hr />
<div>{{comic<br />
| number = 3015<br />
| date = November 22, 2024<br />
| title = D&D Combinatorics<br />
| image = dnd_combinatorics_2x.png<br />
| imagesize = 328x446px<br />
| noexpand = true<br />
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}<br />
<br />
Dungeons and Dragons (D&D) is a role-playing game that usually has a "Dungeon Master" (narrator) that takes a team of players through scenarios where they attack monsters and go on quests.<br />
<br />
Often, there will be semi-random events: e.g., when attacking a monster, often a player will roll a die and deal damage based on the result. D&D uses a variety of dice, from regular d6 (6-sided, cubic dice) to other polyhedral dice, with the number of faces denoted by dX (e.g., d10 is a 10-sided die, with numbers from 1 to 10 on it). Common sets include: d4, d6, d8, d10, d12, d20, and occasionally d100 (typically not, however, the [[2626:_d65536|d65536]]).{{cn}}<br />
<br />
With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:<br />
<br />
* There are 10 arrows.<br />
* 5 arrows are cursed.<br />
* You randomly take two.<br />
* What are the odds that neither of them are cursed?<br />
<br />
Calculating using {{w|binomial coefficients}}, there are “10 choose 2” (45) ways to choose two arrows, of which there are “5 choose 2” (10) ways to choose 2 arrows that are non-cursed. As a result, the odds of taking all non-cursed arrows is 10/45, which simplifies to 2/9. <br />
<br />
To see this in a different way, the probability of choosing one non-cursed arrow is 5/10, which then must be multiplied by the probability of choosing the second non-cursed arrow, which is now 4/9, giving 20/90 or 2/9, the same result as before.<br />
<br />
The Dungeon Master (DM) in this case [[356: Nerd Sniping|has to]] map that probability into rolling multiple dice, whose sums are also not evenly distributed: i.e. if rolling 3d6 (3 six-sided dice) and a d4 (1 four-sided die), the sums can range from 4 to 22. It's pretty hard to do this in one's head, but it does happen that the odds of rolling 16 or more with this combination is 2/9, matching the probability that we want to simulate. Here's a table of all the 6*6*6*4=864 possible outcomes -<br />
<br />
{| class="wikitable"<br />
|+ All possible combinations of rolls for 3d6 + 1d4<br />
|-<br />
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22<br />
|-<br />
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88<br />
| style="background:#ffffcc;" | 71<br />
| style="background:#ffffcc;" | 52<br />
| style="background:#ffffcc;" | 34<br />
| style="background:#ffffcc;" | 20<br />
| style="background:#ffffcc;" | 10<br />
| style="background:#ffffcc;" | 4<br />
| style="background:#ffffcc;" | 1<br />
|}<br />
<br />
71+52+34+20+10+4+1 = 192<br />
<br />
192/864 = 2/9, which matches the desired probability from earlier. The table of outcomes can either be bruteforced with a program, or can be derived using generating functions.<br />
<br />
The caption elaborates that the DM has a degree in the relevant field, and is unable to resist applying this to the D&D game when the opportunity arises - opportunities that Cueball eagerly provides for this very reason.<br />
<br />
There is a much easier way of implementing the operation: literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (cards, for example), with the assigned information of whether each one is cursed hidden away from Cueball, and then let Cueball pick any two. Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and for the second, roll another 1d10 and reroll if Cueball gets the same number. If 1-5 represents the cursed arrows and 6-10 represents the non-cursed arrows, following the convention that lower rolls are bad in D&D, then this achieves the same result without coming up with a more complex solution.<br />
<br />
It may be inferred that as the DM's mind tends towards more combinatorial solutions, she is either unable or unwilling to consider more straightforward solutions to the problem.<br />
<br />
The title text claims that Randall only started doing this to the DM after she herself insisted on forcing another combinatorial puzzle on the players several times, involving a bunch of locked treasure chests and a multitude of keys to unlock them with. This might be a reference to an M-of-N encryption system, where a system has ''n'' valid passwords (instead of just one) but requires ''m'' of those passwords to be given before it will open; it is assumed m is greater than 1 but less than n. While this is easy enough to implement in a computer system, it would be extremely cumbersome to build for a physical lock with keys, and spreading the mechanism across multiple separate treasure chests would be impossible without literal magic (luckily, magic is in plentiful supply in a typical Dungeons and Dragons game).{{cn}}<br />
<br />
==Transcript==<br />
{{incomplete transcript|Do NOT delete this tag too soon.}}<br />
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting at a table. Everyone is looking at Cueball. Ponytail is facepalming. The table is covered in sheets of paper and assorted dice.]<br><br />
:Cueball: I grab 2 of the 10 arrows without looking and fire them, hoping I didn't grab one of the 5 cursed ones. Did I?<br />
:Ponytail: Sigh. Umm. Okay.<br />
:Ponytail: Roll... Uh... Hang on...<br />
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.<br />
<br />
:[Caption below the panel:]<br />
:I got '''''way''''' more annoying to play D&D with once I learned that our DM has a combinatorics degree and can't resist puzzles.<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Comics featuring Megan]]<br />
[[Category:Comics featuring Ponytail]]<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Knit Cap]]<br />
[[Category:Games]]<br />
[[Category:Math]]</div>Lgstarn