Editing 3015: D&D Combinatorics

{{comic
| number    = 3015
| date      = November 22, 2024
| title     = D&amp;D Combinatorics
| image     = dnd_combinatorics_2x.png
| imagesize = 328x446px
| noexpand  = true
| titletext = Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.
}}

==Explanation==

{{w|Dungeons and Dragons}} (D&D) is a {{w|tabletop 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.

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 {{w|Dice#Common_variations|polyhedral dice}}, with the number of faces denoted by XdY (e.g., 3d10 is a rolling of 3 10-sided dice, which each have 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}}

With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a {{w|combinatorics|combinatorial}} problem:

* There are 10 arrows.
* 5 arrows are cursed.
* You randomly take two.
* What are the odds that neither of them are cursed?

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. 

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.

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 -

{| class="wikitable"
|+ All possible combinations of rolls for 3d6 + 1d4
|-
!Total!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22
|-
|Ways to roll it||1||4||10||20||34||52||71||88||100||104||100||88
| style="background:#ffffcc;" | ''' ''71'' '''
| style="background:#ffffcc;" | ''' ''52'' '''
| style="background:#ffffcc;" | ''' ''34'' '''
| style="background:#ffffcc;" | ''' ''20'' '''
| style="background:#ffffcc;" | ''' ''10'' '''
| style="background:#ffffcc;" | ''' ''4'' '''
| style="background:#ffffcc;" | ''' ''1'' '''
|}

71+52+34+20+10+4+1 = 192

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.

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.

There are several much easier ways of implementing this operation, without coming up with a more complex solution:
#Do not even attempt to abstract the chances with dice-rolls. Literally present 10 similar-looking arrows, or other objects that are taken to represent arrows (face-down playing cards, for example), where the assigned information of whether each one is cursed initially hidden away from Cueball, and then just let Cueball pick any two. This approach would more likely be used if the D&D gameplay were {{w|Live action role-playing game|live-action}} as opposed to {{w|Tabletop role-playing game|tabletop}} (though is still possible in tabletop). 
#Even just with D&D dice, the DM could ask Cueball to roll a 1d10 for the first arrow, and then again for the second, re-rolling the second so long as Cueball gets the same number as before (which emulates the same sort of process, but with a non-zero chance of having to make and reject an arbitrary number of extra dice-rolls). One could specify that 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.
#Similarly, the player could be asked to roll a d20, with a score of 15 or 16 requiring a re-roll and 17–20 being successful choices. This would give a 4/18 chance, i.e., 2/9 for a successful roll on the first (and any subsequent) rolls. As with option 2, there would be a 1/10 chance of having to make and reject at least one extra dice-roll. 
#If understanding the actual odds, but wishing to keep the dice in use simple, a 2/9 probability can also be found by saying Cueball would succeed when 2D6 produces a 9, 10, or 12 (4/36, 3/36, and 1/36 probability, respectively, giving 8/36, i.e., 2/9).
#Another method would be to roll 1d6 twice, using the first as a base number and the second as a control die where 1-2 = +0, 3-4 = +6 and 5-6 = +12 for a linear spread of 1-18. In this case a roll of 3, 4, 5, or 6 on the first roll coupled with a 5 or 6 on the second roll would indicate the top four of the eighteen possibilities, 4/18, or 2/9.
#Or to roll 1d6 twice and ''multiply'', rather than add, the results. A successful roll is 20 or more.
#Or to take the maximum of 1d6 and 1d12. Denoting 4 or lower as a successful roll, the method yields a probability of 16/72 = 2/9.
#Alternatively, approximate the odds by using a d100 (or equivalent roll of two D10s) and seeking an 78 or higher (i.e. the range of 78-99, assuming this roll can produce a zero/double-zero roll, instead of a 'natural 100' for which the range would have to start at 79), which gives a 22% chance, which may be sufficiently acceptable as it is substantially similar to 2/9's effective odds of 22.<span style="text-decoration:overline">222</span>%. If you re-roll either the 0 or 100 (depending on whether you use 78 or 79 as the cutoff), you would bring the probability exactly to 22/99 or 2/9.

The first two options also instantly reveal cases of whether ''two'' cursed arrows are nominally chosen (an outcome that is at identical odds to the opposite possibility of neither being so), should this be useful roleplaying information in addition to the basic fact of ''failing'' to avoid at least one of them. The option suggested in the comic could also be used to indicate this if the dice add up to 10 or lower, the fourth one if (for example) the complementary results of 2, 4 or 5 are rolled, and the final one in the event that the 'percentage' given is 0-21 (or 1-22).

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 an entirely correct 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.

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 [https://thalesdocs.com/gphsm/luna/6.3/docs/usb/Content/overview/security_features/mofn_about.htm] [https://blog.apnic.net/2021/05/28/what-is-m-of-n-in-public-private-key-signing/], 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}}

==Transcript==
:[Cueball, Megan, Ponytail, White Hat, and Knit Cap are sitting around a table on office chairs. The first and last at either end and the other on the same side facing outwards. Everyone is looking at Cueball who is holding a finger up in front of him while speaking. Ponytail is facepalming while replying. The table is covered in sheets of paper and assorted dice.]
: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?
:Ponytail: Sigh. Umm. Okay.
:Ponytail: Roll... Uh... Hang on...
:Ponytail: Roll 3d6 and a d4. You need... 16 or better to avoid the cursed arrows.

:[Caption below the panel:]
: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.

==Trivia==
When this comic was originally released, the official title of this page was "xkcd: D Combinatorics"{{sic}}, instead of "xkcd: D&D Combinatorics", due to an apparent error on Randall's end. The reason for this is thought to be caused by literal interpretation of the '''''&D''''' as {{w|List of XML and HTML character entity references|character entity}} by the code that created it, though it does not match any normally valid code. <!-- **optional extended explanation** Of the standard list, only the codes for "&deg;" and "&divide;" ''start'' with a (lowercase) "d" and do not ''always'' require a semi-colon at their end, though apparently even they still do so here. No entity name includes whitespace, so "&D ..." must theoretically only be sanitised out by a far too general converter of possible codes to plaintext. -->
Whatever the precise problem, the ampersand also presumably [[explain_xkcd:Community_portal/Admin_requests#RSS_Feed_Broken|broke the RSS feed]], an issue that is said to be only fixable by [[User:Jeff]], who has been inactive for over a year now. {{comic discussion}}

[[Category:Comics featuring Cueball]]
[[Category:Comics featuring Megan]]
[[Category:Comics featuring Ponytail]]
[[Category:Comics featuring White Hat]]
[[Category:Comics featuring Knit Cap]]
[[Category:Dungeons & Dragons]]
[[Category:Math]]