Dominoes

[jfgw]

(Confession: I haven't worked out the answer myself yet but the problem seemed an interesting one.)

I draw three dominoes from a standard "double-six" set of 28. What is the probability that I can lay all three down (in the usual manner) in a single chain?

Julian F. G. W.

[Gengulphus]

I draw three dominoes from a standard "double-six" set of 28. What is the probability that I can lay all three down (in the usual manner) in a single chain?

Nice problem, with a number of ways to tackle it. Here's the best I've come up with so far...

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

The probability is the number of sets of three dominos that can be arranged in such a chain divided by the total number of sets of three dominoes. The latter is easy to calculate as 28 choose 3 = (28*27*26)/(3*2*1) = 3276. For those who don't know the argument, I can pick a set of three by picking one of the 28 dominoes, then picking one of the remaining 27 dominoes, then picking one of the remaining 26 dominoes, leading to 28*27*26 ways of picking a set of three. But for each set of three, I could have picked any one of the 3 first, then either of the remaining 2 second, then the remaining one third, leading to 3*2*1 ways of picking that particular set of three. So the 28*27*26 ways of picking a set of three split up into collections of 3*2*1 ways to pick the same set, leading to the answer.

So we need to determine the number of sets of three dominoes that can be arranged in a chain. This can be done in the same way, counting the number of ways of selecting such a set, but taking care to divide out by the number of ways that select the same set. This needs to be done with care, because that number of ways differs for different sets.

So what does such a chain look like? Obvious answer:

+---+---++---+---++---+---+
| a | b || b | c || c | d |
+---+---++---+---++---+---+

It's going to be important which of a, b, c and d are equal to each other. So first observe that a and c are not equal, nor are b and d, as those imply a repeated domino. That implies that there are the following categories of such sets of three dominoes:

CATEGORY 1) a, b, c and d are all different. I can pick a in 7 different ways, then b in 6 different ways, then c in 5 different ways, then d in 4 different ways. That implies there are 7*6*5*4 = 840 ways of choosing such a chain; however, each such chain can be selected by either choosing a or d first (the two numbers that only appear once on a domino), and then either following through on the only ways to complete the chain, which are picks of a, b, c, d or of d, c, b, a respectively. So I've double-counted the sets of three dominoes that lead to such a chain, so there are (7*6*5*4)/2 = 420 such sets of three dominoes. Note that such sets contain two numbers once each and two numbers twice each.

CATEGORY 2) a=b, but a, c, and d are all different. I can pick such a set in 7*6*5 = 210 ways, and the only way to pick a particular set is to pick the double first, then the domino that can connect to the double, then the remaining domino (which cannot connect to the double). So there are 7*6*5 = 210 such sets of three dominoes. Note that such sets contain one number 3 times, another twice and a third once, so they do not overlap with the 840 category 1 sets, and we have 840+210 = 1050 sets of 3 dominoes that can construct a chain so far.

CATEGORY 3) c=d, but a, b and c are all different. Again, there are 7*6*5 = 210 ways of picking such a set, but each such way has already been counted as a category 2 set, by selecting a=b, c and d for the category 2 set as this category's c, b and a respectively. So we don't add any further sets this time, and remain on 1050 sets of dominoes that can construct a chain.

CATEGORY 4) b=c, but a, b and d are all different (note a and d cannot be the same, as that would imply a repeated domino). We can select such a set in 7*6*5 = 210 different ways, but any such set can be selected in two different ways (pick either of a and d first, then b, then the other one of a and d). So there are (7*6*5)/2 = 105 such sets. Note that such sets contain one number 4 times and the other two once each, so cannot overlap with the category 1-3 sets above, and so we now have 1050+105= 1155 sets that can construct a chain.

CATEGORY 5) a=d, but a, b and c are all different (note b and c cannot be the same, as that would imply a repeated domino). Yet again, we can select such a set in 7*6*5 = 210 ways. But each such set can be selected by picking any of a, b and c first, then either of the remaining two, then the remainiing one, so there are (7*6*5)/(3*2*1) = 35 such sets. Noting that such sets contain three numbers twice each, they don't overlap with any of the sets found in categories 1-4 above, and so we now have 1155+35 = 1190 sets that can construct a chain.

CATEGORY 6) a=b and c=d, but a and c are different. Now we have 7*6 = 42 ways of selecting such a set, but each such set is selected twice, one by selecting a and then c, and once by selecting c and then a, so there are (7*6)/2 = 21 such sets. Noting the such sets contain two numbers, three times each, and thus do not overlap with sets in any of categories 1-5 above, that means we finish with 1190+21 = 1211 sets that can construct a chain.

So the probability is 1211/3276 = 173/468.

Gengulphus

[StepOne]

(I started writing this about 2 hours ago then had to go to watch the kids in school Spring show! Now I get back and I can see that Gengulphus has replied, so I'm debating whether to go ahead and post my response, or whether I'm about to embarrass myself by getting it wrong when someone else has already shown how easy it is!)


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

On the face of it this shouldn't be too bad. For the first pick, 1/4 chance of a double, 3/4 of a non-double.

If you get a double, then 6/27 remaining will be a match for it. None of those 6 are a double, so you now have 2 numbers in your chain to match. Of the 26 remaining dominoes 5 will match the first number and 6 will match the second, so 11/26 chance of a match (we've already picked the one domino that matches both numbers, so zero chance of picking that again). So 1/4 * 6/27 * 11/26 = 66/2808 chance.

Now just need to do the same for the case where the first domino is not a double

Chances of the second pick matching are 3/4 * 12/27 (there are 6 of each number still in the pack).

That second pick could be a double (1/6 chance of that). If it is then we still have the same 2 numbers to match, and one less domino in the remaining pile which could match so the chances of the third one matching here are 11/26.

If the second pick was NOT a double (5/6 chance) then we have still have 2 numbers at each end of the line to match (n.b these 2 numbers must be different - for them to be the same, the first and second dominoes would be identical). So we have 26 dominoes remaining, 12 of these must match the 2 numbers available (14 in the whole pack, less the 2 already picked) so chances of this third domino matching are 12/26

So to summarise
First pick a double;
1/4 * 6/27 * 11/26 = 66/2208 = 396/16848

First pick not a double, second pick a double
3/4 * 12/27 * 1/6 * 11/26 = 396/16848

First pick not a double, second pick not a double
3/4 * 12/27 * 5/6 * 12/26 = 1980/16848

Overall chance = 2772/16848 = 77/468 = 0.16453. About a sixth, which feels more or less like it could be correct.

Okay, now to post and see how close I got!

StepONe

[StepOne]

Okay, so I got it wrong, follow on problem for me is to figure out where!

StepOne

[Gengulphus]

StepOne,

You're trying to answer a subtly different question. I haven't tried checking your solution to that different question in detail yet, but the fact that it's different from my answer is at least partially down to the different question.

Specifically, my answer is to the question: Dominos 1-3 are selected at random, then I try to arrange them into a length-3 chain. What is the probability that I can do so?

And your answer is to the question: Domino 1 is selected and you put it on the table as a 'length-1 chain'. Then domino 2 is selected and you try to add it to the table to form a length-2 chain. If you succeed, domino 3 is selected and you try to add it to the table to form a length-3 chain. What is the probability that you will succeed in adding all three dominoes to the table and thus succeed in forming a length-3 chain?

Any sequence of three dominoes that leads to you succeeding also leads to me succeeding - I just put down the same final length-3 chain as you, without bothering with the intermediate length-2 chain step. But there are sequences of three dominoes that lead to me succeeding and you not - for instance, if domino 1 is 0-4, domino 2 is 5-6, and domino 3 is 4-5. So not surprisingly, you've ended up with a lower probability than me!

I don't think this explains the difference entirely - I can see it leading to an answer in the area of 2/3rds of mine, but not around 1/2 of it. So further explanation is needed - which incidentally could be a mistake in either my answer or yours... I know I came close to making a mistake about double-counting sets of dominoes like 1-2, 2-3 and 1-3, which can form more different chains than the usual two (one plus the same chain in the opposite direction), and wouldn't rule out the possibility of another I didn't detect!

Gengulphus

[jfgw]

A detailed answer as usual Gengulphus. I have yet to verify the answer using a different method (I seem to be getting a higher number and need to spend a bit of time checking).

StepOne, you did indeed answer a different question. I hope you enjoyed it nonetheless.

Julian F. G. W.

[Gengulphus]

I don't think this explains the difference entirely - I can see it leading to an answer in the area of 2/3rds of mine, but not around 1/2 of it. So further explanation is needed - which incidentally could be a mistake in either my answer or yours... I know I came close to making a mistake about double-counting sets of dominoes like 1-2, 2-3 and 1-3, which can form more different chains than the usual two (one plus the same chain in the opposite direction), and wouldn't rule out the possibility of another I didn't detect!

It turns out that I was right that StepOne's answer should be about 2/3rds of mine - and also right to suspect it might be a mistake in mine... :-(

The mistake was a very simple copying error: I calculated the number of sets in each category correctly, but the number I calculated in category 1 was 420 and I instead transferred the number 840 down to category 2! As a result, all totals of sets from category 2 onwards were too big by 420. With that corrected, my final fraction should have been 791/3276 = 113/468 rather than 1211/3276 = 173/468.

I have now double-checked that 113/468 is the right answer, using a 'brute force' spreadsheet. That spreadsheet also double-checks StepOne's chance for the different question he looked at, confirming that it is indeed 77/468 - and the ratio of the two answers is 77/113 = 0.6814..., which is indeed close to 2/3rds.

In case anyone is wondering why I thought the ratio should be close to 2/3rds, by the way, it's just that if there is only one way that the three dominoes can form a chain (counting a chain and the same chain traversed in the reverse order as just one chain), then I always succeed and StepOne succeeds unless he's unlucky enough to get the middle domino of the chain last, which is clearly a 1/3rd chance.

I could have added that if there is more than one way that the three dominoes can form a chain (with the same proviso about reverses), then both of us always succeed, since StepOne cannot get the middle domino of both chains last. So on some sets of three dominoes that I succeed on, StepOne has a 2/3rds chance of success, and on others, he has a certainty of success, and so his overall chance of success has to be at least 2/3rds of mine, and more than 2/3rds of mine if there are any sets in the latter group. There are, and it's not too difficult to see that they're precisely my category 5 sets, which are only 35 out of the 791 total sets that I can succeed with. As a consequence of that small proportion, the ratio of StepOne's chance to mine is only slightly over 2/3rds.

Gengulphus

[jfgw]

With that corrected, my final fraction should have been 791/3276 = 113/468 rather than 1211/3276 = 173/468.
Gengulphus

That matches my answer a lot better. I must have counted everything twice as I had double that.

Julian F. G W.

[jfgw]

Confirmed 791/3276. I brute-forced it as well using a spreadsheet but counted two full cycles. My mistake for not taking notice of the number of lines or setting a flag to indicate that 66 66 66 had already occurred.

Julian F. G. W.

[StepOne]

Thanks for checking that Gengulphus, good to know I'd managed to answer a question - even if it was the wrong one! And thanks to jfgw for posting it.

StepOne