Table coin problem
Problem Statement: There are eight people sitting on a round table, they all flip a coin simultaneously, if head shows up the person is going to stand while if tails shows up that person will remain seated, now what is the probability that no two adjacent person are standing?
Solution:
Let's begin by counting total number of possible configurations, we will have 2 possibilities for each person on the table that's 2x2x2x2x2x2x2x2 = 256 possible configurations.
We can also denote the same in binary H is 1 and T is 0, we will then have combinations starting from all tails(00000000) going all the way upto all heads(11111111) giving us 256 total combinations.
Now, how many favourable combinations we need here, one thing is clear that for no adjacent heads the maximum people that can have head is 4 because we can arrange maximum of 4 head and tails alternatively after that no position will be left for the 5th head, so let us consider the problem case by case:
0 Heads:
There is absolutely no problem when all tails comes (00000000) as none of the person has to stand, no adjacency problem. Hence we have one favourable case here.
1 Head:
In this case only one person is standing and he/she can be arranged in 8 ways
(00000001) (00000010) (00000100) (00001000) (00010000) (00100000) (0100000) and (10000000).
Note: MSB is for 8th person and LSB is for 1st person.
2 Heads:
In this case two standing persons should not come together, i.e number of 1's should not come together, we can calculate this in easy way by saying that total we will have 8!/6!*2!
= 28, because we can form this much different words using 1,1,0,0,0,0,0,0.
ways of arranging these combinations now subtract from this the combinations which will have two 1's together, there will be 8 such combinations (11000000, 01100000, 00110000, 00011000, 00001100, 00000110, 00000011), hence we will subtract these 8 cases in which two heads are adjacent from the total 28 cases.
Hence no. of favourable cases here will be 20.
3 Heads:
We have use a little bit of imagination in this case, let's see how can we arrange 1's so that there is atleast one 0 in between them
Case 1: Alternative 0's and 1's
These 8 ways to rotate the same will be (10101000) (01010100) (00101010) (00010101) (10001010) (01000101) (10100010) (01010001)
Case 2: Two zeros between a pair of one and one zero between the other pair
These 8 ways to rotate the same will be (10010100) (01001010) (00100101) (10010010) (01001001) (10100100) (01010010) (00101001)
Now if we try to make two zeros in between 2 pairs the case becomes same as above
So, in total we have 16 favourable cominations in case of 3 Heads.
4 Heads:
There is only one way by placing 0's and 1's alternatively and the same can be rotated in 8 ways.
These cases are (10101010) and (01010101)
5, 6, 7, 8 Heads:
There is no way to arrange no of 1's >= 5 so that no ones are together as we can see from the figure.
SUMMING UP ALL THE CASES:
So we in total we have 1 + 8 + 20 + 16 + 2 = 47 in which no two ones are together.
These all cases are:
(00000000) (00000001) (00000010) (00000100) (00001000) (00010000) (00100000) (0100000) (10000000) 28-[ (11000000) (01100000) (00110000) (00011000) (00001100) (00000110) (00000011)] (10101000) (01010100) (00101010) (00010101) (10001010) (01000101) (10100010) (01010001) (10010100) (01001010) (00100101) (10010010) (01001001) (10100100) (01010010) (00101001) (10101010) and (01010101).
Hence the probability that no two adjacent person are standing will be equal to 47/256.
This problem was asked in AMC (American Mathematical Competitions) 2015.
Thank you guys for reading, have a nice day!