The jumps of the bunny
A one year old bunny is sitting on the number 0 in the number line. His father, Bugs Bunny, is waiting for him on the number 10.
The bunny has to reach his father. At each minute, he can:
- Move one step forward;
- Move two steps forward;
- Stay still;
- Move one step backward;
- Move two steps backward.
There are N possible ways the bunny can be on the number 10 after 10 minutes. Find the last three digits of N .
Details and assumptions
-
The bunny is allowed to hop beyond 10, and then come back.
-
There are no restrictions on the bunny entering the negative numbers. The bunny can go as much backwards as he wants.
-
Order does matter. For example, the steps { 0 0 0 0 0 2 2 2 2 2 } and { 2 0 2 0 2 0 2 0 2 0 } are considered distinct.
The answer is 403.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
How do you expand this :P
Log in to reply
You could use WolframAlpha but Sreejato showed me a method which involved multiplying the argument in the parentheses by x 2 and then finding the coefficient of x 3 0 .
Also, how did you solve it? :P
After multiplying by x^2, change it into (x^5-1)^10 * (x-1)^(-10), then use binomial expansion, the coefficient of x^30 term = (10 choose 0)(-10 choose 30) + (10 choose 1)(-10 choose 25) + (10 choose 2)(-10 choose 20) + (10 choose 3)(-10 choose 15) + (10 choose 4)(-10 choose 10) + (10 choose 5)(-10 choose 5) + (10 choose 6)(-10 choose 0). And of course (-n choose m)=(n+m-1 choose m) for n,m=nonnegative integers.
Log in to reply
excellent method however i thin what you mean is(10 choose 0)(-10 choose 30) - (10 choose 1)(-10 choose 25) + (10 choose 2)(-10 choose 20) - (10 choose 3)(-10 choose 15) + (10 choose 4)(-10 choose 10) - (10 choose 5)(-10 choose 5) + (10 choose 6)(-10 choose 0) because x^5 -1 will give negative coefficients for odd powers of x
also notice that coefficient of x^10 = coefficient of x^30 so simply we have.
(-10 choose 0)(-10 choose 10)-(10 choose 1)(-10 choose 5)+(10 choose 2)(-10 choose 0)
Note that the exponents are 2, 1, 0, -1, and -2 which correspond to the number of moves he has moved towards his father. (Negative means backwards). The whole expression raised to the 10th power represents the 10 minutes. Thus the coefficient of x^10 will be the number of ways. If you would like to know more about generating functions this is a good site
www.mathdb.org/notes download/elementary/algebra/ae A11.pdf
(That was the article that introduced me to this concept)
Log in to reply
i want to know what do you mean by x,what is the value of x,and how can i get 72403
Log in to reply
x is not really meaningful here, it's just a tool to keep the exponents (total distance) and coefficients (combinations of steps that get that distance) meaningful. You could divide the whole thing x 1 0 because 10 is the distance you're looking for and then find the constant term. In other problems, the variables can take on meaning, though.
This question went over my head!!!! it didn't even dare to pass through it :p.....................i wonder why? by the way the this solution even went over my head.... i again wonder why? :(
Log in to reply
Generating functions are totally worth learning if you enjoy combinatorics
Haha me too; I just entered the function (1+x+x^2+x^3+x^4)^10, and I found the coefficient of x^30
woowww.... :p i tried it with permutations... it's binomial problem!! ;) i'll try it again.... it's a great problem..! :)
great! I did the same thing too. But how do you expand this by hand?
Nice solution! BTW Good luck for SMO Open!
We have to find the number of solutions of summation of a series of 10 variables which can take values from -2 till +2 and count the cases when the answer is 10...
Force Brute is always an option ::
import java.io.*;
public class TheJumpsOfTheBunny
{
public static void main(String args[])
{
int q=0,w=0,e=0,r=0,t=0,y=0,u=0,i=0,o=0,p=0,sum=0;
for(q=-2;q<3;q++)
{
for(w=-2;w<3;w++)
{
for(e=-2;e<3;e++)
{
for(r=-2;r<3;r++)
{
for(t=-2;t<3;t++)
{
for(y=-2;y<3;y++)
{
for(u=-2;u<3;u++)
{
for(i=-2;i<3;i++)
{
for(o=-2;o<3;o++)
{
for(p=-2;p<3;p++)
{
if((q+w+e+r+t+y+u+i+o+p)==10)
sum++;
}
}
}
}
}
}
}
}
}
}
System.out.print(sum);
}
}
OUTPUT:: 72403
That's called cheating!
Log in to reply
can you get me a detailed solution ?
Log in to reply
Read the other solution for deriving the generating function, and Maya Maya's comment for computing the coefficient of x 1 0 .
We can also use dynamic programming method. a[i][j] = a[i-1][j-2] + a[i-1][j-1] + a[i-1][j] + a[i-1][j+1] + a[i-1][j+2], where a[i][j] - the number of ways be on number j after i minutes.
Log in to reply
.... Plus the obvious boundary conditions a [ 1 ] [ j ] = 1 , ∀ j = 8 , 9 , 1 0 , 1 1 , 1 2 and zero otherwise.
Above attempt is called brute force attempt. In this attempt ,this problem has a complexity of 5^10... that's a huge one.
This is not a computer science problem.
hey priyanka! u used programming skills very well..thumbs up!
without using programming can we solve this another way, do you have any idea about this, please if you able,send it my email. [email protected]
We seek the number of solutions to the equation x 1 + x 2 + x 3 + . . . + x 1 0 = 1 0 where each x i ∈ { − 2 , − 1 , 0 , 1 , 2 } , or equivalently the number of solutions to x 1 + x 2 + x 3 + . . . + x 1 0 = 3 0 where each x i ∈ { 0 , 1 , 2 , 3 , 4 } . (You can picture the original problem as the bunny moving 0 to 4 steps forward and always 2 steps back each minute. Ignoring the 2 steps back each time, it would end up at the number 30 instead of 10)
This is then a routine inclusion-exclusion problem. Using " stars and bars ," the number of solutions to x 1 + x 2 + x 3 + . . . + x 1 0 = 3 0 where each x i ∈ { 0 , 1 , 2 , 3 , 4 , 5 , . . . } is ( 9 3 9 ) .
If x 1 ∈ { 5 , 6 , 7 , . . . } we can define x 1 ′ = x 1 − 5 ∈ { 0 , 1 , 2 , . . . } and the equation becomes x 1 ′ + x 2 + x 3 + . . . + x 1 0 = 2 5 , which has ( 9 3 4 ) nonnegative integer solutions.
This is true for each of the ( 1 1 0 ) x i s. Thus there are ( 1 1 0 ) ( 9 3 4 ) solutions with one of the x i s above 4 that we should subtract.
However by inclusion-exclusion, we must then add back the ( 2 1 0 ) ( 9 2 9 ) where two of the x i s are above 4 , and subtract the ( 3 1 0 ) ( 9 2 4 ) where three of the x i s are above 4 , and so on, yielding:
( 9 3 9 ) − ( 1 1 0 ) ( 9 3 4 ) + ( 2 1 0 ) ( 9 2 9 ) − ( 3 1 0 ) ( 9 2 4 ) + ( 4 1 0 ) ( 9 1 9 ) − ( 5 1 0 ) ( 9 1 4 ) + ( 6 1 0 ) ( 9 9 ) = 7 2 4 0 3
Good Show ! Jolly Good Show !
The generating function is ( x 2 + x + 1 + x 1 + x 2 1 ) 1 0 The coefficient of x 1 0 when expanded is 72403. Thus there are 72403 ways and the last three digits are 403.