3015: D&D Combinatorics

2024-11-25T15:36:53Z

Dustle: /* Explanation */ Added another simple method of calculation using only a six-sided die.

{{comic
| number = 3015
| date = November 22, 2024
| title = D&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==
{{incomplete|Created by a BOT THAT GRABBED A CURSED ARROW AND A NORMAL ARROW - Please change this comment when editing this page. Do NOT delete this tag too soon.}}

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.

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}}

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.
#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.
#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>%.
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 fourth option could also be used to suggest this 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, 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==
{{incomplete transcript|Do NOT delete this tag too soon.}}
:[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>
: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.

{{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:Games]]
[[Category:Math]]

explain xkcd - User contributions [en]

3015: D&D Combinatorics