Chess Squares
What is the probability to randomly chose any 3 squares on a chess board, and they would form a continuous diagonal?
You don't hold a chess board in your hands to solve this one. simply think.
You don't hold a chess board in your hands to solve this one. simply think.
Labels: Probability, thinktank
posted by Rajesh Lal at
9:32 AM
20 Comments:
Chess Diagonals Problem
For this problem analyze the probability of hitting square 1, then the probability of hitting a 2nd square that may form a diagonal with the first square and then probability of hitting a 3rd square that actually forms the diagonal. If we do this for every square and then sum up the probabilities, this will be the net probability of a diagonal being formed if 3 random squares are picked.
By symmetry, the number of cases is reduced to 6 cases, which are labelled as A,B,C,D,E,F. Their location is shown on the board below.
A B C C C C B A
B D E E E E D B
C E F F F F E C
C E F F F F E C
C E F F F F E C
C E F F F F E C
B D E E E E D B
A B C C C C B A
Explanation of below diagrams:
For each case the 1st square is chosen e.g. A. The possible second squares are then labelled with a number that shows how many possible 3rd squares are possible if that 2nd square is hit.
Case A:
4 squares, 2 possible 2nd squares, which have only 1 possible 3rd square each
P(A)=4/64*2/63*1/62=8/(64*63*62)
A . . . . . . .
. 1 . . . . . .
. . 1 . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Case B:
8 squares, 2 possible 2nd squares, which have only 1 possible 3rd square each
P(B)=8/64*2/63*1/62=16/(64*63*62)
. B . . . . . .
. . 1 . . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Case C:
16 squares, 4 possible 2nd squares, which have only 1 possible 3rd square each
P(C)=16/64*4/63*1/62=64/(64*63*62)
. . 1 . . . . .
. 1 . . . . . .
C . . . . . . .
. 1 . . . . . .
. . 1 . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Case D:
4 squares, 5 possible 2nd squares, 4 which have only 1 possible 3rd square each and 1 square with 2 possible 3rd squares.
P(D)=4/64*(4/63*1/62+1/63*2/62)=24/(64*63*62)
1 . 1 . . . . .
. D . . . . . .
1 . 2 . . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Case E:
16 squares, 6 possible 2nd squares, 4 which have only 1 possible 3rd square each and 2 squares with 2 possible 3rd squares each.
P(E)=16/64*(4/63*1/62+2/63*2/62)=128/(64*63*62)
. . . 1 . . . .
1 . 2 . . . . .
. E . . . . . .
1 . 2 . . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Case F:
16 squares, 8 possible 2nd squares, 4 which have only 1 possible 3rd square each and 4 squares with 2 possible 3rd squares each.
P(B)=16/64*(4/63*1/62+4/63*2/62)=192/(64*63*62)
1 . . . 1 . . .
. 2 . 2 . . . .
. . F . . . . .
. 2 . 2 . . . .
1 . . . 1 . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Total= P(A)+ P(B)+ P(C)+ P(D)+ P(E)+ P(F)
Total=(8+16+64+24+128+192)/(64*63*62)=432/(64*63*62)
Total=432/249984 ~= 0.17281 %
Overall, chances don't look too good for this happening at random.
ANSWER: 432/249984 ~= 0.17281 %
Hopefully no mistakes above.
Cam
First of all, Anonymous, you are a much better mathematician than I am ...I'm hoping you will look at my analysis and tell me where I went wrong.
Consider a chessboard. Using scientific notation, it looks like this:
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
The possible number of 3 connected diagonal squares are:
a6 - c8 (1)
a5 - d8 (2)
a4 - e8 (3)
a3 - f8 (4)
a2 - g8 (5)
a1 - h8 (6)
b1 - h7 (5)
c1 - h6 (4)
d1 - h5 (3)
e1 - h4 (2)
f1 - h3 (1)
That's a total of 36 going one way and the same number in the opposite direction ... making a total of 72 possible 3 square connected diagonals.
When you randomly select the f1rst square, there are 64 possible picks ... 63 with the second ... and 62 with the third ... making the total number of 3 square picks = 249,984
Since the number of possible 3 square connected diagonals is 72... I'm thinking the possibility of randomly picking 3 square connected diagonally is:
72/249,984 = .000288
.0288%
However, if I was to bet on this, I'm going with Anonymous's answer ... heh heh!
Hi Zaux. The diagonals aren't equally likely.
Hi Cam. Small point - if you choose three squares at random, they could all be the same square. So all your denominators should be 64^3 rather than 64*63*62. More seriously, you are counting some of the diagonals more than once.
Hi again Zaux. I'm not so sure that my statement is right. I think you have the correct answer.
... except I think it should be 64*64*64 rather thatn 64*63*62. We're not pulling balls out of a bag without replacement.
Chris ... thanks. I guess what I did was to determine what percentage the total number of possible 3 square diagonals is of the total number possible 3 square picks...
But once a square is selected, it is not available as the 2nd or 3rd selection.... right?
Hi Zaux. If you stab a pin into a chessboard, whilst wearing a blindfold, what's going to stop you choosing the same square the next time you stab?
Anyway I'm only nit-picking. As far as I'm concerned, you have given the correct answer. I'm not sure why I first thought that the diagonals were not equally likely.
Nice one beating Cam, feel smug (until next time) :) I'm sure Cam will be kicking himself when he sees his error. It was a trap that was easy to fall into. I took quite a while spotting it.
Oh ...ok ... I did not consider that. I interpreted the statement to mean 3 different random picks ...
Milking it a bit, I was pretty sure Cam had got it wrong because of the way the question was phrased: second paragraph => this is easy.
Hi Zaux. I could easily be wrong, the phrasing of the question makes it quite likely that you and Cam have done the right thing. I am guilty of overriding with common-sense.
I guess the wording does open the door to either interpretation...
I guess the wording does open the door to either interpretation...
wow, a lot has happened in the week I was gone.
For this I found 41,664 unique sets of three squares, and 72 of them create unique diagonal sets.
I will read the previous posts and see if anyone got the same.
Opps Now I got 249984 unique sets of 3.
Hi Ragknot. I had noticed your abscence.
Well spotted, I hadn't bothered to check Zaux's 249,984 = 64!/(64-3)! = 64*63*62 - I just assumed that was the correct number. I hadn't thought to check, but I agree with your 41,664 = 64!/((64-3)!*3!)= 64*63*62/6. i.e. the order in which you choose the 3 squares doesn't matter.
So the answer is 72/41664 ≈ 0.17281%.
Now I'm dumbfounded. I've just noticed that's Cam's result. I'm going to have to re-think. I've obviously made a major goof or two somewhere. Looks like I'm more fallible than I'd previously thought. Back soon...
Got it. Cam was over-counting, but by the required factor of 6 for both diagonals and non-diagonals. I'd only noticed he'd been over-counting, not that it was always by exactly 3! = 6. I jumped to the wrong conclusion that the factor varied and so immediately assumed the whole of Cam's program was flawed.
So Cam had done it correctly, as I had originally anticipated. Zaux and I hadn't noticed the subtle difference in the way we counted the diagonals and the non-diagonals.
I also liked the simplicity of Zaux's solution, that would have biased me enormously. If not for a silly mistake, I would have realised that both Cam and Zaux (essentially) were right. I'm sure Cam will agree with me on that.
Having got that sorted, I've just noticed that Ragknot has published a "correction" to the other figure. Well I think that's now been dealt with.
Wow,
Can someone recap, as to whether I'm supposedly right or supposedly wrong and if I'm wrong why ?
Anyhow for what it's worth I did assume that 3 seperate squares must be selected. From inspection, the method Ragknot has selected assumes the same, and thankfully we have reached the same result. Good job, by the way, Ragknot.
If a square can be reselected the same method can be used but the divisor changes from (64*63*62) to 64^3. The probability then drops from 432/(64*63*62)~=0.1728% to 432/(64^3)~=0.1648%.
That is, of course, if my method isn't fundamentally flawed.
Cam
This post has been removed by the author.
Hi Cam, I was wondering where you were. For the record, you were right and Zaux (and I) was wrong.
Zaux and I saw it as there are 72 diagonals and you saw it as 432 diagonals. You were (possibly unwittingly as you were in probability mode) counting each diagonal 6 times. i.e. if label the 3 squares as a, b and c, you were treating abc, acb, bac, bca, cab and cba as distinct diagonals. You counted the set of all the groups of 3 square in the same way.
Unfortunately Zaux and I counted the random sets of three using permutations, instead of combinations. So we had a factor of 6 error as aptly demonstrated by Ragknot. The rest is in my pathetic self-defence speech.
I'm sorry about the confusion and the incorrect denouncement of your result.
And I agree with your 0.1648% other calculation (I dare not disagree :) )
Post a Comment
Links to this post:
Create a Link
<< Home