Understand the problem

Eight people are sitting around a circular table, each holding a fair coin. All eight people flip their coins and those who flip heads stand while those who flip tails remain seated. What is the probability that no two adjacent people will stand?

Source of the problem
American Mathematics Competition 
Topic
Probability / Combinatorics

Difficulty Level
‘7/10
Suggested Book
Challenges and Thrills of Pre-College Mathematics

Start with hints

You could give it a thought first…are you sure you really need a hint ?

Let’s not get worried by the idea of having to find out the probability. For, we may simply recall : Probability = Number of favorable events / Total number events in the sample space So, the denominator is easy to find out here, 8 people, all of whom are either standing or sitting. So, 2 possibilities for every person. And that makes our denominator, \(2^8 = 256 \) Now, with a little bit of focus, it is not at all hard to see that the numerator, “number of favorable events” is essentially a Combinatorics arrangement problem. 

So, would you like to have a go at this by yourself now ?

Now, as we go ahead with the solution, let us develop the idea of the strategy we could use here. You must be familiar with recursion, but let’s just recall its philosophy. Recursion essentially meant that you could express a variable or a term in terms of its own parameters. As in, when a function calls itself. If you want a brief look-up, catch the short story in the paragraph below [ Much like imagine, you’re eating a large cake. You won’t really eat the whole thing at once, would you ? You would possibly enjoy it in parts. Imagine you’d have 1/3 rd of it, to begin with. Then if your problem initially is, EAT THE CAKE. Even, after you have had a first bite, as I just said, what’s the name of your problem ? It’s still EAT THE CAKE , isn’t it ? Yes, you’re still eating the same cake, only your problem is reduced by 1/3-rd, somewhat like a miniature version. Something we could call, ( EAT THE CAKE ) / 3…That’s pretty much, an intuitive idea of recursion. ] How could we model our problem in that fashion ? Imagine we talk of 8 persons standing in the line, to begin with. Let us try to develop a recurrence relation for the problem. Let’s talk of a person, N in the queue. See the catch here, if this person N is sitting, our problem size reduces by 1 – which means it is now equivalent to 7 people standing in the queue. On the other hand if this person N is standing, it is implied by the statement of the problem, that the adjacent people on his either side must be sitting ! That reduces our problem size by 2… Hey, so now that we have kind of linguistically framed it, could you try out a mathematical interpretation ?     

Let, the answer we are looking for is a_n. ( That is, the number of ways to arrange n people in a line such that no two of them, who are adjacent, are standing ) So for a_n >= 2,
See there can be only two broad-spectrum cases : Case I : Person #1 in the line is standing If Person #1 in the line is standing, the second one is sitting. So the rest can be arranged in a_n-2 ways.  Case II : Person #1 in the line is sitting
This means the rest can be arranged in a_n-1 ways. So, Case I + Case II, adds up to the relation we are looking for ? That would be something like :  a_n = a_n-2 + a_n-1 Wait ! Does this, by any chance seem familiar ? Does it ? Well yes, this is nothing but the Fibonacci Recurrence Relation. The problem of rabbits in the field, if you need some off-beat reference !  [ The Fibonacci Sequence goes like :
   1,1,2,3,5,8,13, 21, 34,….
It’s quite easy to see that from the third time onwards, every term is numerically equal to the sum of its two previous terms ] So, do you think you could conclude this…and find the required probability ?                  

So we just saw, we can map the given problem at hand to the Fibonacci problem.  Our starting cases here would be a_0 = 1 and a_1 = 2. ( By the problem ). This means our ans would be the (n+2)th Fibonacci number for a_n F_n stands for the n’th Fibonacci number, of the sequence you just came across in the last hint. So that gives us a_5 + a_7 = F_7 + F_9 = 13 + 34 = 47. So, that’s our numerator ! Hence, the required probability =   47 / 256 

And that’s pretty much of all we need ! 

Watch video

Connected Program at Cheenta

Math Olympiad Program

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year. Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.

Similar Problems

Roots of Equation and Vieta’s formula | AIME I, 1996 Problem 5

Try this beautiful problem from the American Invitational Mathematics Examination, AIME, 1996 based on Roots of Equation and Vieta’s formula.

Amplitude and Complex numbers | AIME I, 1996 Question 11

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1996 based on Amplitude and Complex numbers.

Tetrahedron Problem | AIME I, 1992 | Question 6

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1992 based on Tetrahedron Problem.

Triangle and integers | AIME I, 1995 | Question 9

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1995 based on Triangle and integers.

Functional Equation Problem from SMO, 2018 – Question 35

Try this problem from Singapore Mathematics Olympiad, SMO, 2018 based on Functional Equation. You may use sequential hints if required.

Arithmetic sequence | AMC 10A, 2015 | Problem 7

Try this beautiful problem from Algebra: Arithmetic sequence from AMC 10A, 2015, Problem. You may use sequential hints to solve the problem.

Sequence and greatest integer | AIME I, 2000 | Question 11

Try this beautiful problem from the American Invitational Mathematics Examination, AIME, 2000 based on Sequence and the greatest integer.

Inscribed circle and perimeter | AIME I, 1999 | Question 12

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 2011 based on Rectangles and sides.

Problem based on Cylinder | AMC 10A, 2015 | Question 9

Try this beautiful problem from Mensuration: Problem based on Cylinder from AMC 10A, 2015. You may use sequential hints to solve the problem.

Series and sum | AIME I, 1999 | Question 11

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1999 based on Series and sum.