  How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?

# Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]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?

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="4.0"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="4.0" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="4.0"]American Mathematics Competition [/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]Probability / Combinatorics

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]'7/10[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.29.2" open="off"]Challenges and Thrills of Pre-College Mathematics

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="4.0" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff" custom_padding="||150px|18px||"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]You could give it a thought first...are you sure you really need a hint ?

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]

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 ?

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]

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 ?

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

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 ?

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

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 !

# Similar Problems

[/et_pb_text][et_pb_post_slider include_categories="9" _builder_version="3.22.4"][/et_pb_post_slider][et_pb_divider _builder_version="3.22.4" background_color="#0c71c3"][/et_pb_divider][/et_pb_column][/et_pb_row][/et_pb_section]

# Knowledge Partner  