N cakes are arranged in a line. Each cake is of a different flavor. You and your friend play a game to eat the cakes. When you eat a cake, your friend eats the (<=2) adjacent cakes.
For example, suppose there were 5 cakes initially named A,B,C,D and E. If you eat cake C, your friend eats B and D, and the new configuration is A,E. Now, if you eat cake A, your friend eats cake E.
The question is simple: how many possible combinations of cakes can you finally eat? Note that the order of eating does not matter for the answer.
Hint: consider the Nth Fibonacci number, also called FN. Everyone knows that:
For example, suppose there were 5 cakes initially named A,B,C,D and E. If you eat cake C, your friend eats B and D, and the new configuration is A,E. Now, if you eat cake A, your friend eats cake E.
The question is simple: how many possible combinations of cakes can you finally eat? Note that the order of eating does not matter for the answer.
Hint: consider the Nth Fibonacci number, also called FN. Everyone knows that:
- F1=1, F2=2 and Fn=Fn-1+Fn-1
- FN is the number of ways to choose some objects from N objects (arranged in a line) such that no 2 are adjacent.
- FN is the also number of ways to climb a flight of n stairs using one or 2 steps.
This comment has been removed by the author.
ReplyDeleteBhaiya after i select a cake nd my friend selects one or 2 adj. cakes.Do we have to consider cakes left on the table as a new order. If it is so, i m getting the relation as
ReplyDeletef(n)=2*f(n-2)+(n-2)*f(n-3).
If it is correct , please tell how to solve the relation.
Here, f(n)denotes the no. of possible ways to select from n cakes..!!