3015: D&D Combinatorics

Explain xkcd: It's 'cause you're dumb.
Jump to: navigation, search
D&D Combinatorics
Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.
Title text: Look, you can't complain about this after giving us so many scenarios involving N locked chests and M unlabeled keys.

Explanation[edit]

Ambox notice.png This explanation may be incomplete or incorrect: Created by a HTML SHORTENING CODE TYPO - Please change this comment when editing this page. Please DO delete this tag too soon.
If you can address this issue, please edit the page! Thanks.
Dungeons and Dragons (D&D) is a 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 polyhedral dice, with the number of faces denoted by XdY (e.g., 3d10 is a rolling of 3 10-sided die, 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 d65536).[citation needed]

With these, you can simulate events with a wide variety of denominators. In this case, Cueball gives a 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 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 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 -

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 71 52 34 20 10 4 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:

  1. 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 live-action as opposed to tabletop (though is still possible in tabletop).
  2. 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.
  3. 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.
  4. 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).
  5. 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.
  6. Or to roll 1d6 twice and multiply, rather than add, the results. A successful roll is 20 or more.
  7. 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.222%. 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 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).[citation needed]

Transcript[edit]

[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[edit]

When this comic was originally released, due to seeming error on Randall's end, the official title of the page was "xkcd: D[sic] Combinatorics", instead of "xkcd: D&D Combinatorics". The reason for this is thought to be caused by literal interpretation of the &D as an HTML escape character.

comment.png add a comment! ⋅ comment.png add a topic (use sparingly)! ⋅ Icons-mini-action refresh blue.gif refresh comments!

Discussion

The bot originally created this page as “D Combinatorics”. I renamed it to the correct title and tried to get as many of the references as possible (including a few redirects). JBYoshi (talk) 00:54, 23 November 2024 (UTC)

The title in the Atom feed (which I'm assuming the bot consumes) is "D Combinatorics". I'm guessing something in Randall's pipeline didn't like the ampersand. --162.158.154.160 01:41, 23 November 2024 (UTC)
Yup, if you look at 3015's JSON you see that title and safe_title differ, and if you look at the HTML page source you'll see 3 different things: <title>xkcd: D Combinatorics</title>, <meta property="og:title" content="D&amp;D Combinatorics">, and <div id="ctitle">D&D Combinatorics</div>! So probably what happened is Randall entered D&D but was supposed to enter D&amp;D, and the openGraph tags adder code, having to be HTML-aware, decoded & normalized D&D as HTML would, but the other parts of the pipeline just ate it for some reason. 172.69.65.224 (talk) 06:09, 23 November 2024 (please sign your comments with ~~~~)
The problem now is that the feed doesn't validate (because it contains a bare &) and it's also not updating (maybe because of the previous problem). --172.71.119.13 11:10, 28 November 2024 (UTC)

What are the odds of rolling 16 or higher on 3D6+D4? 3D6 average 10.5, D4 average is 2.5, total average should be 13. I do not know how to proceed from here. 172.71.147.206 (talk) 01:14, 23 November 2024 (please sign your comments with ~~~~)

By raw combinatorics: 71 + 52 + 34 + 20 + 10 + 4 + 1 ways to get each of 16 - 22 respectively, for a total of 192, out of 4(6^3) = 864 total. 192/864 simplifies to exactly 2/9. I have no idea how Randall found this; if anyone has an idea, please let me know. Kaisheng21 (talk) 01:33, 23 November 2024 (UTC)
I used some simple python code to loop over every dice and confirm and it's 2/9 162.158.158.111 12:11, 23 November 2024 (UTC)
I suspect there is no better way of doing it than looping over the dice. As to how Randall discovered it, it was obvious that at least 2d6 would be needed (since d6 is the only D&D dice that has a multiple of 3 sides), and after that my guess is Randall used a combination of a python script and some experimentation to land on the correct choice of dice. 172.70.162.56 14:15, 1 December 2024 (UTC)

It seems like we edited the transcript at the same time. The odds of rolling 16 or higher in this situation seem to be 2/9? Darkmatterisntsquirrels (talk) 01:29, 23 November 2024 (UTC)

There are 864 possible rolls (6 * 6 * 6 * 4). If you enumerate all of the rolls you will find that 192 are 16 or higher. 192/864 = 2/9, the value from the explanation. 172.68.54.139 01:41, 23 November 2024 (UTC)

I added a table of outcomes to clarify how it works out to 2/9, anyone know how to make it pretty? -- Laurence Cheers 172.71.150.247 (talk) 02:03, 24 November 2024 (please sign your comments with ~~~~)

A much simpler approach: Roll two six sided dice and sum the result. You are successful if the result is 5 or 9. That happens 8 times out of 36. 8/36 = 2/9. (Or successful if the sum is 4 or 6, or 2 or 7, or 2,3,4 or 11, or several other combinations.) 172.68.54.139 01:41, 23 November 2024 (UTC)

Clever, but dice rolls in D&D involving summing all the dice, applying modifiers, if any, and then comparing to one or more threshold values. Your method makes it very difficult to apply modifiers. 162.158.41.8 02:49, 23 November 2024 (UTC)
I think you misunderstand the problem here. This is not skill, no modifiers apply, it's purely probability 162.158.158.111 12:11, 23 November 2024 (UTC)

Minor quibble, arrows aren't fired (unless they're flaming or self-propelled, perhaps), they are shot. (Shotguns are fired of course.) 162.158.41.73 02:52, 23 November 2024 (UTC)

Arrows are "loosed", even more accurately. At least to avoid the confusion from how so many things may be shot, or a shot. (Many different nouns, from a physical measure of liquer/coffee/vaccine to a projectile, or an even abstract fundemental of chance; and, as verb, projectiles perhps may be shot, then so may their targets.) 172.68.205.178 14:32, 23 November 2024 (UTC)
Well, lets not quarrel over it.172.71.103.67 14:37, 25 November 2024 (UTC)
Too many barbed comments, and I'd be all of a quiver... 141.101.99.153 14:51, 25 November 2024 (UTC)

Rolling 22 or lower on percentile dice (or, equivalently, 79 or higher) is close enough, and easier to come up with. (Give or take whether 00 is treated as 100 or zero.) Or directly represent the action: roll a d10. If it's 1-5, you lose. If it's 6-10, roll again; if it's 1-5 you lose, 6-9 you win, 10 roll again. (Modify slightly if you want to distinguish the case of grabbing *two* cursed arrows.) Jordan Brown (talk) 03:26, 23 November 2024 (UTC)

Alternative exact solution for getting this probability using dice: Roll: 1d8, 2d6, 1d4 succeed on 19 or higher. 172.68.55.11 (talk) 03:54, 23 November 2024 (please sign your comments with ~~~~)

I couldn’t remember the formula for binomial coefficients (“n choose k”), but there’s an easy way to calculate that the probability of drawing no cursed arrows is 2/9 without that formula. You just need to multiply the probabilities that each of the arrows drawn is not cursed. Since only two arrows are drawn, you only have to multiply two numbers.

The probability that the first arrow is not cursed is 5/10 – there are 5 non-cursed arrows and 5 cursed arrows out of 10 total. After taking out one non-cursed arrow, there are 4 non-cursed arrows and 5 cursed arrows out of 9 total, so the probability that the second arrow is not cursed is 4/9. Multiplying the two probabilities, the probability of drawing two non-cursed arrows is (4*5)/(10*9) = 20/90 = 2/9.

I was considering writing this observation in the Explanation section of the page, but I’m not if it belongs there. This solution avoids using formulas from combinatorics, so it might not be connected enough to the comic.—Roryokane (talk) 06:02, 23 November 2024 (UTC)

My simple-minded approach:

  • Roll d10 once for your first arrow: if 1 to 5, the arrow is cursed, otherwise not;
  • Roll d10 again for your second arrow: same rules, but repeat until you have a different number from the first one (so d10 is in fact only a d9 this time)
  • I won't calculate probabilities – these are your arrows, live with it ;-) 172.69.109.51 07:33, 23 November 2024 (UTC)
That has the benefit (over 3d6+1d4) of telling you which arrow(s) (if either) was cursed. RegularSizedGuy (talk) 07:52, 23 November 2024 (UTC)
Also tells you how many cursed arrows are left, which is useful if the next player wants to take their chances with them too.172.71.103.68 14:40, 25 November 2024 (UTC)
If you don't like re-rolls, you can make d9 out of 2d3. Nine possibilities, so just assign one of them (perhaps by rolling them one at a time) to be the more significant digit. Don't have a d3 handy? Use d6 and modulo off the extra! (1=1, 2=2, 3=3, 4=1, 5=2, 6=3) 172.68.150.91 05:59, 24 November 2024 (UTC)

There seems to be doubt that a "N locks and M keys to unlock them" system could be easily accomplished. I think it could be trivial, with strategically interlocking locked-restraints. A chain formed of bike-locks can give a larger locked loop that can be unlocked by just unlocking any single one of the constituent locks, leaving the other locked loops to not matter (or you could also try the Borromean rings system, whereby it is again secure against itself, until just one ring is opened up to reveal that the rest now aren't even locked at all...). With almost arbitrary ability to cross-link (or, if you will, repeated/alternating-reflected Borromean triplet connections), you can extend the requirements to more than one unlocking being required (by looping chain elements to mre than just the 'adjacent' loops, sideways onto a parallel meta-loop or up/down the chain, all you might do is allow some slack (could be sufficient to get a thing held directly closed by the taut loop-of-loops, but not enough if the passage of the loop through a hasp/sneck actually prevents the otherwise free movement of the final slide-to-unlock action to occur), but a second (or third, or fourth) unlocking can be required to open-end the whole metaloop of locks. At the top end, M=N solutions are also trivial (e.g. two keys, two locks popularly of safety deposit boxes or other things). Which is not to say that a specific M-of-N puzzle (where 1<M<N) might not need a little bit of thought to actually design and implement, but there's no obvious reason why all such combinations shouldn't be nicely doable. 172.69.79.165 14:56, 23 November 2024 (UTC)

Can we first confirm that the M-of-N Encryption was what Randall was referencing in the first place? 172.71.154.140 03:17, 24 November 2024 (UTC)
No, first confirm that this is what the explanation treats as what Randall was referencing. As it was, "complicated lock mechanics" and/or "magic" were suggested as the only ways of doing this, when this (or what we thought this was) just needs a little thought and N bike-locks suitably entangled. 172.70.58.45 13:17, 24 November 2024 (UTC)
I'm glad someone else chimed in on this, because it is definitely not difficult to require unlocking of multiple discrete locks! I can't even figure out why one might think it would be? ProphetZarquon (talk) 15:55, 24 November 2024 (UTC)

"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)." - the d10 may be a poor choice as exemplar here; Back in the last century, when I was playing D&D, d10 were typically (and uniquely) numbered 0-9, not 1-10. This may no longer be the case, and I may be showing my age, but if it is still the norm, the d8 or d20 might be a better choice of example. 172.68.210.6 02:40, 24 November 2024 (UTC)

Typically, I've only seen 0-9 d10s, as part of a "d100" dice pair, with one reading 0-9 & the other reading 0⁰-9⁰... Single d10, mostly seem to come in 1-10? Maybe it depends which reseller one shops at... ProphetZarquon (talk) 15:49, 24 November 2024 (UTC)
They are usually numbered 0-9, but the 0 represents 10, since writing 10 would require that face to have a different font size. It is still a d10, since the die has ten sides, and still cannot roll at 0. The d100 variant does the same thing with 100, but for the added reason that the 00 face actually does mean 0 when the other die rolls a 1-9. This is the convention, so a die that actually writes 10 on it instead of 0 will be rare. Stardragon (talk) 23:14, 24 November 2024 (UTC)

You've all been nerd-sniped. Caliban (talk) 10:53, 24 November 2024 (UTC)

Combinatorics degree? Does such a degree really exist? --162.158.130.37 17:19, 24 November 2024 (UTC)

There are degrees for all kinds of things. A quick search reveals a number of "Combinatorics" or "Combinatorics and <Foo>" (e.g. "Optimisation") degrees. Some of them are marked as Masters degrees, and I haven't dug into the others to see if there are any 'pure' undergraduate ones (apart from anything else, I know there are crucial differences between the structures and scopes of UK and US 'degree courses' to consider, in particular), but there seems to be representation on both sides of the Atlantic (and elsewhere, e.g. Oceana).
At the very least, it could be a selected specialised segment of an even wider mathematical degree course, or a cross-disciplinary one (like my own, which was part under Physics and part under Computing, but could have included a Stats-based element). 162.158.74.49 19:07, 24 November 2024 (UTC)
So "Combinatorics and <Foo>" would be meta-combinatorics, since it is combining something with something else. :) RandalSchwartz (talk) 20:19, 28 November 2024 (UTC)
I shall do my degree in "Combinatorics, Selectivity, Comparison, Decision Making and/or Cross-Designation (Choose Any Three)"... 172.70.90.5 21:28, 28 November 2024 (UTC)


I'm trying this on my DM. -P?sych??otic?pot??at???o (talk) 15:11, 25 November 2024 (UTC)

Can someone put into the Explanation the current details regarding the nature of cursed arrows, in whatever edition of DnD we're currently up to. (8th? I've lost track.) In different DnD-like media, I know that it can act somewhat negatively (reduces aim accuracy) or even outright problematic (it curses the person loosing the projectile; or even renders the bow otherwise useless, as analogue to a cursed weapon), or else reduces/inverts the damage (breaks easier, or essentially acts like a thrown beneficial potion to increase health/strength/stamina/etc of the target). I assume that it one of these, from the assumption that the player desires a "good enough" roll to avoid. On the other hand, cursed projectiles could be treated akin to poisoned arrows or vengeful weapons in doing more, better or more targeted damage (in which case it's a powerful aid, the archer is instead taking a chance of using up a stock of 'special arrows', perhaps in line with not knowing whether their foe needs that extra degree of offensive power). But, at least from the explaining text's approach to dice-roll results, that doesn't exactly mesh with the typical "higher is better" rolling mantra. 172.70.86.129 22:43, 25 November 2024 (UTC)


I don't think making an M-of-N mechanism with physical locks would be "extremely cumbersome". For example you could have a bolt that must be drawn back to open the mechanism, with several padlocks over it, where the shackle of each padlock blocks the motion of the bolt, such that the distance you can draw the bolt is proportional to how many padlocks are removed. Removing any m of the n padlocks gives you enough range of motion to open the mechanism. 172.71.154.224 23:17, 27 November 2024 (UTC)

A DM with a degree in Combinatorics would be unlikely to find this annoying.162.158.62.245 05:30, 30 November 2024 (UTC)

With up to three D&D dice, it is impossible to achieve 2/9 exactly. The closest you can get is with d6 + 2d10x10 >= 146 (where d10x10 denotes the tens die, ranging from 10 to 100) yielding a probability of 133/600 = 0.2216667. Vandof (talk) 06:27, 30 November 2024 (UTC)

With four D&D dice, 2d6 + d8 + d10 >= 21 and d10 + 2d12 + d20 >= 36 are alternate solutions. The former is more feasible than 3d6 + d4 for those who don't have three d6's. Vandof (talk) 06:49, 30 November 2024 (UTC)