# Understand the problem

##### Source of the problem

##### Topic

##### Difficulty Level

##### Suggested Book

# Start with hints

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

**ways.**

*a_n-2***Case II : Person #1 in the line is sitting**

This means the rest can be arranged in

*ways. So, Case I + Case II, adds up to the relation we are looking for ? That would be something like :*

**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 !*

**a_n = a_n-2 + a_n-1**

**[ The Fibonacci Sequence goes like :**

**1,1,2,3,5,8,13, 21, 34,….***So, do you think you could conclude this…and find the required probability ?*

**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 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 =**. So, that’s our numerator ! Hence, the

*F_7 + F_9*= 13 + 34 = 47**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.

Google