Edited version of a known problem

For students of class 9-10 (age 14-16)
User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Edited version of a known problem

Unread post by Masum » Sun Dec 02, 2012 1:25 am

Probably most of you have solved the following problem:
In how many ways can you finish at $(n,m)$ from $(0,0)$ if the possible moves are only up and right. Now the question is what would be the number of ways if you are restricted the area enclosed by the rectangle with vertices $(a,0),(m,0),(m,b),(a,b)$.
One one thing is neutral in the universe, that is $0$.

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: Edited version of a known problem

Unread post by Phlembac Adib Hasan » Sun Dec 02, 2012 1:45 pm

(Guessing the start point is $(a,0)$ and the end point is $(m,b)$)
Translate $(a,0)$ to $(0,0)$ and solve.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: Edited version of a known problem

Unread post by *Mahi* » Sun Dec 02, 2012 7:21 pm

Phlembac Adib Hasan wrote:(Guessing the start point is $(a,0)$ and the end point is $(m,b)$)
Translate $(a,0)$ to $(0,0)$ and solve.
Nah bhai :p
I think Masum bhai means you can't step inside the rectangle formed by those 4 vertices.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: Edited version of a known problem

Unread post by Masum » Sun Dec 02, 2012 11:10 pm

yeah, that area is restricted, so you can't step inside the rectangle.
One one thing is neutral in the universe, that is $0$.

User avatar
Nadim Ul Abrar
Posts: 244
Joined: Sat May 07, 2011 12:36 pm
Location: B.A.R.D , kotbari , Comilla

Re: Edited version of a known problem

Unread post by Nadim Ul Abrar » Tue Dec 11, 2012 5:41 pm

Note that if we move the point $(0,0)$ to $(m,n)$ then it will take $m$ right operation and $n$ up operation .
So the number of required ways is number of ways to choose $m$ numbers from $m+n$ distinct numbers . I mean
$\displaystyle \binom {m+n}{m}$.

Now we will count in how many ways one can move the point through the restricted area .
If one move the point through restricted area then he must move the point through any of points
$(a+k,b-k)$. [$a+k \leq m $ and $b-k \geq 0$]

Now one can move the point from $(0,0)$ to $(a+k,b-k)$ in $\displaystyle \binom {a+b}{a+k}$ ways . And as Adib told using axis transformation one can move the point $(a+k,b-k)$ to $(m,n)$ in $\displaystyle \binom {m+n-a-b}{m-a-k}$

So we can move $(0,0)$ to $(m,n)$ through $(a+k,b-k)$ in $\displaystyle \binom {a+b}{a+k} \binom {m+n-a-b}{m-a-k} $ ways .

Case 1: $b>m-a$
then $k_{max} =m-a$ implying the numbers of ways as $\displaystyle \binom {m+n}{m}- \sum_{k=1}^{m-a} \binom {a+b}{a+k} \binom {m+n-a-b}{m-a-k}$

Case 2: $b\leq m-a$
then $k_{max} =b$ implying the numbers of ways as $\displaystyle \binom {m+n}{m}- \sum_{k=1}^{b} \binom {a+b}{a+k} \binom {m+n-a-b}{m-a-k}$
$\frac{1}{0}$

Post Reply