Page 1 of 1
BdMO National 2021 Secondary Problem 12
Posted: Sun Apr 11, 2021 9:38 pm
by Pro_GRMR
গামাকিচি আর গামাতাতসু নামের দুটো ব্যাঙ যথাক্রমে \((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?
Re: BdMO National 2021 Secondary Problem 12
Posted: Fri Apr 16, 2021 9:07 pm
by F Nishat
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.
Re: BdMO National 2021 Secondary Problem 12
Posted: Mon Apr 19, 2021 7:07 pm
by Pro_GRMR
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
. Awsome solution nonetheless!!!
Re: BdMO National 2021 Secondary Problem 12
Posted: Mon Apr 19, 2021 7:23 pm
by F Nishat
Pro_GRMR wrote: ↑Mon Apr 19, 2021 7:07 pm
How did I not see that bijection
. Awsome solution nonetheless!!!
Yes, the bijection looks easy but hard to notice. Solved after trying for $2$ days
