Select Page

# 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

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

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 !

# Connected Program at Cheenta

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

## Unit digit | Algebra | AMC 8, 2014 | Problem 22

Try this beautiful problem from Algebra about unit digit from AMC-8, 2014. You may use sequential hints to solve the problem.

## Problem based on Integer | PRMO-2018 | Problem 6

Try this beautiful problem from Algebra based on Quadratic equation from PRMO 8, 2018. You may use sequential hints to solve the problem.

## Number counting | ISI-B.stat Entrance | Objective from TOMATO

Try this beautiful problem Based on Number counting .You may use sequential hints to solve the problem.

## Area of a Triangle | AMC-8, 2000 | Problem 25

Try this beautiful problem from Geometry: Area of the triangle from AMC-8, 2000, Problem-25. You may use sequential hints to solve the problem.

## Mixture | Algebra | AMC 8, 2002 | Problem 24

Try this beautiful problem from Algebra based on mixture from AMC-8, 2002.. You may use sequential hints to solve the problem.

## Trapezium | Geometry | PRMO-2018 | Problem 5

Try this beautiful problem from Geometry based on Trapezium from PRMO , 2018. You may use sequential hints to solve the problem.

## Probability Problem | AMC 8, 2016 | Problem no. 21

Try this beautiful problem from Probability from AMC-8, 2016 Problem 21. You may use sequential hints to solve the problem.

## Pattern Problem| AMC 8, 2002| Problem 23

Try this beautiful problem from Pattern from AMC-8(2002) problem no 23.You may use sequential hints to solve the problem.

## Quadratic Equation Problem | PRMO-2018 | Problem 9

Try this beautiful problem from Algebra based on Quadratic equation from PRMO 8, 2018. You may use sequential hints to solve the problem.

## Set theory | ISI-B.stat Entrance | Objective from TOMATO

Try this beautiful problem Based on Set Theory .You may use sequential hints to solve the problem.