Puzzle: A Confused Frog.
It took a visit to the "Love Letter Company" and I was with a new puzzle.So there's this frog which has to go 30 steps downstairs. Now this amazing frog can either jump over either one or two stairs at a time. So to say that minimum 15 and maximum 30 leaps is what the frog wud take to cross the staircase.
The question is "In how many different ways can the frog cross the staircase ?"
TrackBack:
This puzzle seems to be inherently a programming problem; like the Combinatorial Explosion Puzzle posted earlier. Of course this is NOT to claim that it cannot be solved otherwise !
posted by Praveer @ Thursday, January 06, 2005
20 Comments:
This is what i think is the solution. There are 15 leaps the frog needs to take if it jumps 2 steps at a time.
Lets consider this case, the frog choose to take 2 big leaps and rest small leaps. the number of ways of choosing two big leaps of the 15 is 15C2 and for each of these 15C2 ways there is only one way in which the frog can take small leaps.
So the whole problem boils down to number of ways in which it can choose 0 big leaps + 1 big leap +....+15 big leaps which is
15C0+15C1+.....+15C15
consider (a+b)^n=ncoa^nb^0+......+ncna^0b^n
replacing n=15,a=1,b=1
the we find that the frog is in deep confusion its got 2^15 choices to choose from.
There is a small correction to the solution above...the from has 28 and not 25 ways of taking big leaps....so the solution i think is 2^28
Dear Anon,...
For 6 steps the answer is 13 and for 10 steps its 89.
Your 2^(N-2) thing doesnt fit in here.
My reasoning says the no of possibilities,
N = 30C0 + 30C2 + 30C4 + ... + 30C30
The number of ordered pairs satisfying (2x+y=30) is 16 viz {(0,30),(1,28),...,(15,0)}. For each of these, there are different combinations possible, i.e. 30Cy or 30C2x. Hence the result
N reduces to 2 raised to the power 30.
oops! I didn't see Praveer's comment before. Is the answer for N = 6 etc given already?
@ Sundar's First ...
30C0 is fine but 30C2 does not enforce the condition that the 2 selected shud be TOGETHER. Similarly, 30C4 does not enforce a condition that there shud be two pairs of two consecutive stairs. In fact for just one big leap, there are 28 different ways possible.
@Sundar's second.
30C0 + 30C2 + 30C4 + ..... 30C30 is NOT equal to 2^30.
@Sundar's Third.
The answer is not given. It is what I found manually to verify my result. By enumerating possibilities for 6 steps.
I got the first point. How stupid of me!
The second point I had thought about, but somehow forgot while finding the closed form. Btw, I have a hunch that for even number of steps i.e. 30, 30C0 + 30C2+...+30C30 = 2 raised to the power 29.
Solution : -
a+2b=30
15 <= a+b <= 30
15 <= 30-b <= 30
0 <= b <= 15
(15*2, 0*1) = 15!/ 15! 0!
(14*2, 2*1) = 16!/ 14! 2!
(13*2, 4*1) = 17!/ 13! 4!
(12*2, 6*1) = 18!/ 12! 6!
------
------
------
(2*2, 26*1) = 28!/ 2! 26!
(1*2, 28*1) = 29!/ 1! 28!
(0*2, 30*1) = 30!/ 0! 30!
= Sigma(n=0,15) [(x+n)! / {(2n)!*(x-n)!}]
I guess this can be calculated easily by calculator or program !!!
DEATH TO EVERYONE....
Who is the last anonymous? HATS OFF.
Anthro.
Great Work Anonymus !!
I believed it was a programming excercise but u gave it an amazing mathematical dimension.
The answer seems to be correct I verified it for n = 6.
Just a small typo in the formula....
Sigma(x=0,n)[(x+n)!/{(n-x)! * (2x)!}
For n = 6 it gives 13.
The problem can be modelled using a binary tree, assuming each a node corresponds to some step and at each step there are two possibilities so the tree grows in either direction untill and growing the tree with two possibilities(jump 1 or 2) at each node. The answer is the number of leaves in the tree. Making a Program which generates a binary tree and enumerates the leaves
wasn't difficult; but of course enumerating it is NOT solving it.
The interesting part was generalising it mathematically. I got an idea for the following program
which gives the same answer without making a tree at all and guess what, it is simple :-)
The very reason why it works has its roots in modelling the problem using Binary Tree.
======
#define DEPTH 30
int
Fib(int N)
{
if(N < 4)
return N ;
else
return (Fib(N-1) + Fib(N-2)) ;
}
int
main(void)
{
printf("For Depth = %d Total No of Leaves = %d\n",DEPTH, Fib(DEPTH) ) ;
return 1 ;
}
====
So The answer for DEPTH=30 is .... 1346269
Guess anonymous wud like to have a look at it.
ps: It is easier to define such a function in excel...
Good Work Praveer.......To find out that the solution for stairs is the 30th number in fibonacci series......Still not sure about your data-structure solution (Binary Tree).......Simple thinking is the Best !!!
I guess no one needs proof....
Good Work Praveer.......To find out that the solution for No of stairs=30 is the 30th number in fibonacci series......Still not sure about your data-structure solution (Binary Tree).......Simple thinking is the Best !!!
I guess no one needs proof....
Simplicity has solution.....you learned little later !!!
Hey Anon,
I made The Tree for 4 steps... see the link...
http://weblogimages.com/static/amL260677PU9.jpg
The number of leaves is 5 which is the answer for 4 steps.
Now the reason why fibonacci number is the answer is as follows.
Build tree for N=3... No of leaves = 3
Build tree for N=4... No of leaves = 5.(ref link)
To get the tree for N=5, add left child(jump = 1) to leaves of N=4 tree and add right child to the leaves of N=3 tree so effectively the number of leaves in N=5 tree will be 3+5=8.
This fibonacci number solution is hard to fathom without binary trees. Thats the point I wanted to make.
Yet another manifestation of Fibonacci numbers ...
instead of creating a tree and counting the no of leaves how abt creating the leftmost branch of the tree (in this case the one with height=30) and then backtracking at every level for the no of possible steps from that level.
I did not get you anonymous :-/. Kindly Explain.
Post a Comment
<< Home