BdMO National 2021 Secondary Problem 12

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Pro_GRMR
Posts:46
Joined:Wed Feb 03, 2021 1:58 pm
BdMO National 2021 Secondary Problem 12

Unread post by Pro_GRMR » Sun Apr 11, 2021 9:38 pm

গামাকিচি আর গামাতাতসু নামের দুটো ব্যাঙ যথাক্রমে \((0, 0)\) আর \((2, 0)\) বিন্দুতে আছে। তারা যথাক্রমে \((5, 5)\) আর \((7, 5)\) বিন্দুতে পৌঁছাতে চায়। তারা শুধু ধনাত্মক \(x\) বা \(y\) দিকে এক দৈর্ঘ্যের লাফ দিতে পারে। কতভাবে তারা তাদের লক্ষ্যে পৌঁছাতে পারবে যদি এমন কোনো বিন্দু না থাকে যেটা তারা দুজনই স্পর্শ করে?

Two toads named Gamakichi and Gamatatsu are sitting at the points $(0,0)$ and $(2,0)$ respectively. Their goal is to reach $(5,5)$ and $(7,5)$ respectively by making one unit jumps in positive $x$ or $y$ direction at a time. How many ways can they do this while ensuring that there is no point on the plane where both Gamakichi And Gamatatsu land on?
"When you change the way you look at things, the things you look at change." - Max Planck

User avatar
F Nishat
Posts:7
Joined:Fri Apr 16, 2021 4:21 pm

Re: BdMO National 2021 Secondary Problem 12

Unread post by F Nishat » Fri Apr 16, 2021 9:07 pm

Without restrictions the answer would be $\binom{10}{5}^2=63504$. We now try to find the number of ways such that Gamakichi and Gamatatsu have at least one common point in their path. To do so, we make a bijection:
Bijection: Consider a path of the two toads where there is at least one common point of the toads. We now swap each path after the first meeting of Gamakichi and Gamatatsu (i.e.change the pink paths into green and vice versa). Note that the toads can overlap each other. Now, we get a pair of paths where Gamakichi will go from $(0,0)$ to $(7,5)$ and Gamatatsu will go from $(2,0)$ to $(5,5)$. So, we get a bijection. Now, there are $\binom{12}{5}\cdot\binom{8}{5}=44352$ paths in the second case.
So, the answer to the given problem will be $63504-44352=\boxed{19152}$.
Image description: In the image, we swap the paths of the toads after the yellow point where pink lines are paths of Gamakichi and green lines are paths of Gamatatsu.
Edited after remark of sman96.
Attachments
rsz_image.png
rsz_image.png (118.7KiB)Viewed 1646 times
Last edited by tanmoy on Sat Apr 17, 2021 9:42 pm, edited 1 time in total.
Reason: Correcting latex error

User avatar
Pro_GRMR
Posts:46
Joined:Wed Feb 03, 2021 1:58 pm

Re: BdMO National 2021 Secondary Problem 12

Unread post by Pro_GRMR » Mon Apr 19, 2021 7:07 pm

F Nishat wrote:
Fri Apr 16, 2021 9:07 pm
Without restrictions the answer would be $\binom{10}{5}^2=63504$. We now try to find the number of ways such that Gamakichi and Gamatatsu have at least one common point in their path. To do so, we make a bijection:
Bijection: Consider a path of the two toads where there is at least one common point of the toads. We now swap each path after the first meeting of Gamakichi and Gamatatsu (i.e.change the pink paths into green and vice versa). Note that the toads can overlap each other. Now, we get a pair of paths where Gamakichi will go from $(0,0)$ to $(7,5)$ and Gamatatsu will go from $(2,0)$ to $(5,5)$. So, we get a bijection. Now, there are $\binom{12}{5}\cdot\binom{8}{5}=44352$ paths in the second case.
So, the answer to the given problem will be $63504-44352=\boxed{19152}$.
Image description: In the image, we swap the paths of the toads after the yellow point where pink lines are paths of Gamakichi and green lines are paths of Gamatatsu.
Edited after remark of sman96.
How did I not see that bijection :o . Awsome solution nonetheless!!! :oops:
"When you change the way you look at things, the things you look at change." - Max Planck

User avatar
F Nishat
Posts:7
Joined:Fri Apr 16, 2021 4:21 pm

Re: BdMO National 2021 Secondary Problem 12

Unread post by F Nishat » Mon Apr 19, 2021 7:23 pm

Pro_GRMR wrote:
Mon Apr 19, 2021 7:07 pm
How did I not see that bijection :o . Awsome solution nonetheless!!! :oops:
Yes, the bijection looks easy but hard to notice. Solved after trying for $2$ days :D

Post Reply