Talk:3015: D&D Combinatorics

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&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)

Well, it's updating now, but it still doesn't validate. Sigh... --172.70.160.195 11:33, 10 December 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)

I had assumed that the locks were built into the chests (as they sometimes are), and that the chests were physically separated. Using m of n keys on a single chest would merely be complicated, but wouldn't really fulfill the description. Leaving the chests unlocked, but tightly wrapped in a locked chain would be more like drawers of a single "chest". I instead assumed that each of m chests had to be individually opened with its own proper key, but you had n chests to choose from. It was unspecified what would happen if you tried pairing a chest to the wrong key; perhaps both the key and the chest would be disabled (melted/stuck/burned/teleported). (And yes, needing only a subset of the chests, but any sufficiently large subset will do, is a semi-standard class of problem; a search for Byzantine Generals or PAXOS algorithm will get you started.) JimJJewett (talk) 07:45, 5 December 2024 (UTC)

For certain combinations of Ms and Ns, one solution is to have each chest have M locks (that must all be unlocked), such that each possible combination of M keys fully opens (at least) one chest, within which are the necessary complimentary keys to now fully unlock every other chest. A looser version is to have possibly only M/2 (or M/3, etc) locks in a configuration whereby you get to open any given two (or 3+) chests that only produce the full set of keys (and probably spares), but does leave it open to being exploited as "we could only open the one chest, and maybe one or two others with (M/2)<(owned keys)<(M) partial key overlap but at least it had some of the available treasure", unless designed to not work like that.

The limited subset of workable {M,N} values makes it impractical as "I have N chests and M chests, how do I...?" puzzle-setting, but still leaves it possible to force a puzzle from scratch that works this way (e.g. "you must have visited at least M antechambers and deceated the Key Guardians within, before you can open the chests within which are all the components necessary to create the potion that makes you ElementalLevelBoss-Proof"), for which you can determine a convenient set of requirements.

One (simple) combination would be two of three distinct keys (#1, #2 and #3) and three chests ("A", needs #1+2, contains #3; "B" needs 1+3, contains 2; "C" need 2+3, contains 1).

Add in the feature of duplicate keys but also a mechanism (or magic, or valid physical reason) which causes keys to be stuck in the locks (or vanish/melt/shatter/etc) upon being used, and you can create an even more complex puzzle, whereby having keys enough to (theoretically) open two chests is actually only enough to open one of them initially as you then lose the ability to attempt to open the other... at least until the opened chest provides new keys enough to open (perhaps by opening a different interim chest, with its own new keys, etc) the one that you did not initially choose. This would greatly expand the number of higher-order "M-of-N" combinations that you could facilitate. And could even created "M>N" requirements (three keys, two (combo-)locks: chest A needs 1+2, chest B needs 1+3; both render any keys inserted beyond further use but also contain a 'spare' 1; you need to externally gain 1+2+3 to eventually open A+B).

Exactly how (and why) you do it is open to your own needs.

And, if you're open to add an intermediate "locked box", you can exploit the trivial many:one and one:many relationships by just compounding them together, and maybe even adding more steps; e.g. with the last example of keys 1+2+3 opening A+B, you can offer up (from A, 4)+(from B, 5). To unlock C needs both 4+5 (thus 1+2+3, once removed), which itself handily contains all the further individual keys (or copies of the one key) required to open D, E, F, ... Z, so grants the stipulation of "3 needed to open 23". Or the earlier 2 keys (non-sticking, or regained by copies) for 3 chests grants the full co-keys needed to open that same key-store (see also Annett's key). Arbitrarily higher permutations of pretty much any initial number of (original) keys and however many intermediate openings (to match the singular key-safe's relatively simple multi-key requirements) steps you through the means to then open an arbitrary number of (final) locks, but you won't get any of the last locks unlocked if you have not fully satisfied the very first requirement.

...although it'd be neater if it was an M-and-N that was more direct, I still think. 141.101.99.85 18:13, 5 December 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)

You can do it with two dice, although not by summation. Roll 2d3; if 1,1, or 3,3 pass, else fail. 162.158.167.88 19:41, 3 December 2024 (UTC)

Could someone explain option 6, multiplying two six-sided dice, with a threshold of > 20? I think 66, 65, 64, 56, 55, and 46 all work, making it ... equivalent to 1D6. JimJJewett (talk) 07:25, 5 December 2024 (UTC)

It's >= 20, so 54 and 45 work as well. That brings the probability up to 8/36 = 2/9. Vandof (talk) 13:31, 5 December 2024 (UTC)

Scales for locking

Wouldn't using scales for the chests that measure their current mass and lock/open the doors based on whether the chest still has the object work for an M-of-N encryption? A simple example: A chest has 2.5 kg of Au, with the chest itself and its combination lock being 20 kg. The next door opens iff the chest's total mass is less than 21 kg. Removing all the Au from the chest opens the door. The second one has an object with the mass of 3 kg, and the chest itself is 22 kg, with that door opening if the chest's mass is between 23 and 24 kg. Removing the object and replacing it with 1 kg of Au opens the door. Long story short: no, one does not need magic for realizing an M-of-N encryption, one just needs scales for a physical M-of-N encryption. 172.68.245.25 08:16, 13 December 2024 (UTC)

Randall doesn't understand probability or games

You don't need to combine the probabilities. You just make two checks. The first check is even odds of cursed / normal. If the check fails and it's cursed, presumably you proceed with the consequences of grabbing a cursed arrow, whatever that might be. In any case, whether the first arrow was normal, or the curse doesn't prevent you from grabbing and firing another arrow, the second check is either 4:9 (if the first arrow was normal) or 5:9 (if it was cursed). (These odds are written as the number of normal arrows remaining : the total number of arrows.)

There is no reason to roll the dice given in the comic. He just made up some dice rolls vaguely similar to those that he heard someone mention in the context of tabletop games, and he's certainly never actually played in one. You can convert these probabilities into decimal form and use a d100 for every check. Probabilistic results like these are the reason the d100 is in the game. (You can also roll 2d10, selecting one of them to be the tens digit and the other to be the units digit.)

The chance of succeeding (choosing a normal arrow) on the first check is 50%, so you can use any type of dice, and success is rolling above X/2, X = faces of the dice.

The chance of succeeding on the second check is 4/9 if the first arrow was normal, or about 44%. So you succeed on a roll of 44 or less. The chance is 5/9 if the first arrow was cursed, or about 56%. So you succeed on a roll of 56 or less.

You don't need a degree in anything to reach these conclusions. 172.70.83.67 (talk) 20:51, 17 March 2025‎ (please sign your comments with ~~~~)