# Two Dragons and a Princess

## The Quest

You are a knight tasked with rescuing the King's daughter. The princess is being held captive by a band of evil dragon pirate monks. You've been debriefed with prior intelligence gathered through reconnaissance to inform your journey. To reach her prison cell you must pass through two consecutive rooms, each guarded by a single dragon. Thankfully, you need not fight the dragons alone. You've managed to sneak into the band's incubating chamber where they keep their dragons in suspended animation. The dragons are grouped into seven weyrs1. Each weyr has a corresponding summoning stone used to summon a dragon out of suspended animation. The stones are labeled as follows:

A: 2, 14, 17

B: 7, ?, 16

C: 13, ? 15

D:

E:

F: 8, ?, 6

G: ? 11, 18

Each weyr (indicated by its letter) contains three pairs of dragons. No two pairs of dragons share the same class amongst the seven weyrs, and each pair always shares the same class. The three numbers next to each weyr represent the class of each pair. A class represents a dragon's strength. Classes range from 1 to 21, with a class 21 dragon being the strongest.2

The summoning stone is used to summon a dragon from its weyr. Each dragon from that weyr has an equal probability of being summoned. Only one dragon from a weyr can remain summoned at a time. The outcome of each summon is independent of the last.

You notice that some of the numbers on the stones are unreadable (indicated by a "?"), and two stones are missing altogether.

## The Rooms

Each day, the band of dragon pirate monks randomly selects two summoning stones and randomly summons a dragon from each stone into a room. You do not know which dragons from the missing weyrs currently guard the two rooms.

## The Strategy

In order to get past the dragons and save the princess, you plan to steal one of the remaining five summoning stones. For each room you'll summon a dragon. If all goes well, your dragon will be of higher class and will defeat the other dragon3. The dragons cannot fit through the doors, so after (hopefully) defeating the first dragon, you'll return it back into suspended animation and proceed through the next door, where you'll summon another dragon. Each stone only has enough magic for two summons, and you can only choose one stone.

The good news: before you began your quest, Intelligence had indicated that, should you choose the best stone, your chance of defeating the first dragon would be greater than 50%.

The bad news: The chances of defeating both dragons is still slim.

Which stone should you choose?

Bonus: What is the probability of defeating both dragons with this stone?

1. A weyr /ˈwɪər/ is a collection of dragons.
2. For example: Weyr A contains a pair of class 2 dragons, a pair of class 14 dragons, and a pair of class 17 dragons.
3. The dragons will fiercely protect their summoner and are hostile to other dragons
• have you deliberately indicated the full list for A in a footnote? or is that possibly not what A really has? Aug 23, 2016 at 20:40
• @Kate Gregory Good Catch! It was a mistake, but I'll add that information into the original list. Those are the correct values for A.
– WHY
Aug 23, 2016 at 21:02
• Even if someone answers the bonus correctly, I think the tick should go to Sconibulus: he answered the original question in a very simple way, probably even simpler than you intended.
– ffao
Aug 24, 2016 at 4:34
• I put a new answer in, I wasn't sure if I was supposed to keep the old one as-is or not, so I've left it as a part for now. Aug 25, 2016 at 18:57
• @Sconibulus Brilliant! 25/81 is the correct answer. Out of curiosity, how did solve for that?
– WHY
Aug 25, 2016 at 19:00

With the new understanding of what the Intelligence means, I've worked out the strengths of the dragons in each stone.

A: $2, 14, 17$
B: $7, 16, 12$
C: $13, 15, 5$
D: $9, 4, 20$
E: $3, 10, 21$
F: $6, 8, 19$
G: $11, 18, 1$

This fulfills the requirement that each stone is beaten more than half the time by at least two other stones. Shown below

A beaten by D,E
B beaten by A,D
C beaten by A,B
D beaten by C,E
E beaten by B,C,G,F
F beaten by A,B,C,D,E
G beaten by A,B,C,D,F

The chances in this situation, taking the best stone:

C gives $\frac{25}{81}$, or about $.31$, This is the best any stone can theoretically do against any other two stones in this setup, which could count as 'slim'.

Below this line was a misunderstanding of the problem parameters, however it is what led me to the right answer, and what the votes and comments reference, so I have left it for now.

The missing dragons are of strengths

1,3,4,5,9,10,12,19,20,21 with a median of (9,10).

Flattening the ranks, how many missing markers does each beat...

A: 1,7,7; B: 4,7,?; C: 7,7,?; F: 4,4,?; G: 6,7,?

This means that

C is the most reliable option, it cannot be any worse than A, and without further rules governing the missing marks, there is no reason to believe any of the other stones available have a better score on the 'hidden' column than C.

To answer the Bonus question, we must take into account the hints,

p1>.5 if we have the best stone. We think the best stone is C, however, as far as we can tell, stones B, C, and G all have pr>.5, where r is random selections from the options.

If we assume

p1>.5 iff we have the best stone, then 1 of the dragons in p1 must be of strength 12 another must be 218 so that pA1 = .444... pC1 is therefor 4/9 + (1/9)if z>x + (1/9)if z>12 + (1/9)if z>y. if z>y, also z>12; if z>12, also z>x. Because we know pC1>1/2, z>x, giving pC1 = 5/9 + (1/9)pz>12 + (1/9)pz>y as an expected value.

Then, onto the last dragon. Slim isn't a very good definition of chances, but I think we can assume it means at least <.5

if z>y from the previous problem, there is only one other value possible that is higher than any value of stone C. this would lead to pC1 = 7/9, and pC2 >=2/3, this is better than .5, and therefor not slim. We now know that z<y. If z = 19, y and the high dragon for room 2 (n) are 20 and 21, that gives pC1 = 2/3, pC2 = 2/3, which comes out to pC=4/9.

If that isn't considered slim...

Then we have eliminated the possibility of z>12, and therefore pC1 = 5/9, or .555... the remaining missing dragons allowed are x: {3,4,5,9} y:{19,20,21} z:{4,5,9,10} n/m/o:{1,3,4,5,9,10,19,20,21}. each random d2 has a 1/3 chance of being > all C, a 1/6 chance of being < all C, and a 1/2 chance of being <z. pCp2 therefor = 1/6 + 1/2(1/3)(1) + 1/2(1/3)(2/3) = 7/18, giving pC = 14/81 which probably is slim.

14/81, or .173

• Where did those numbers come from? Aug 24, 2016 at 12:31
• @dcfyj Which numbers? The first set are all the numbers between 1-21 that weren't names in the initial problem (no dragon is in two places) the second set was a flattening heuristic applied to the first set. Aug 24, 2016 at 14:01
• No idea what a flattening heuristic is, I'll take your word for it. Aug 24, 2016 at 14:05
• @dcfyj I don't know if it's a technical term... basically I applied a function f(x=>missing.Where(m=>m<x).Count) Aug 24, 2016 at 14:30
• ah, I see. That makes sense now. Aug 24, 2016 at 14:32

If we take the advice from Intelligence to mean that "no matter which two stones are missing, at least one remaining stone has a higher than 50% chance of beating a random one of them", then bruteforce shows that the labels of the stones can only be:

A: $2, 14, 17$
B: $7, 10, 16$
C: $13, 5, 15$
D: $1, 12, 20$
E: $3, 9, 21$
F: $8, 19, 6$
G: $4, 11, 18$

(Of course, the values in stones D and E can appear in any order, and those two stones can be swapped).

From this, the optimal choice is

Stone C. It beats stone D with probability $\frac59$ and stone E with probability $\frac59$, leading to an overall winning chance of $\left(\frac{5}{9}\right)^2 = \frac{25}{81}$

I've found a different solution with a different probability of success (given the optimal stone). My solution assumes that

Each stone must contain one number from each of $\{1,\dots,7\}, \{8,\dots,14\}$, and $\{15,\dots,21\}$.

which I'm omitting the proof for currently because I don't have it in a very readable format. My arrangement of the stones finds that the optimal stone

G, B, or F wins with probability $\frac{20}{81}$

and given the above assumption, I think that this is the worst probability of success possible with the optimal stone. My stones are: (laid out as stone: numbers [beaten by])

D: $(4?, 9?, 21?)$[GB];
F: $6, 8, 20?$ [DB];
E: $3?, 12?, 19?$ [DF];
G: $5?, 11, 18$ [FE];
A: $2, 14, 17$ [DFEG];
B: $7, 10?, 16$ [EGA];
C: $1?, 13, 15$ [DFEGAB]

Here's my line of reasoning:

Since each number for each stone falls in one of 3 "buckets", then the probability of a certain stone $O$ winning over a stone $X$ depends on how many of $O$ 's numbers are larger than $X$ 's in the corresponding bucket. If it's strictly smaller, then the probability is $\frac39$; if strictly larger, then $\frac69$. Most will be $\frac49$ or \frac59$, since at some level something has to beat the "strictly larger" stones. The best stones for the monks to have are (if possible) ones that are not beaten by the same stone. This means that the probability can be at most$\frac{4\times 6}{81} = \frac{24}{81}$. In this case, though, the$\frac69$implies that one of the stones chosen is strictly smaller than another stone, so it is strictly better for the monks to choose the other stone. So the probability is at most$\frac{20}{81}$. At the same time, we know that the probability is at least$\frac{3\times 5}{81}={15}{81}$, because you can always choose a stone that beats at least one of the missing ones. On the other hand, since at least two stones will beat each missing stone, you have at least$4$good stones to choose from, so why are you picking one that's strictly smaller than the monks' stone? Not all of them can be strictly smaller than one of the monks' stones, since one that is strictly smaller than stone$O$, but beats stone$X$, implies that stone$O$beats stone$X$and hence a stone that beats$O$cannot be strictly smaller than stone$X$. (because otherwise$X$would beat$O\$!)

If you're interested in the aformentioned proof, it's mostly a proof-by-brute-force. ;)