গামাকিচি আর গামাতাতসু নামের দুটো ব্যাঙ যথাক্রমে \((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?
BdMO National 2021 Secondary Problem 12
"When you change the way you look at things, the things you look at change." - Max Planck
Re: BdMO National 2021 Secondary Problem 12
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.
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 (118.7KiB)Viewed 4985 times
Last edited by tanmoy on Sat Apr 17, 2021 9:42 pm, edited 1 time in total.
Reason: Correcting latex error
Reason: Correcting latex error
Re: BdMO National 2021 Secondary Problem 12
How did I not see that bijection . Awsome solution nonetheless!!!F Nishat wrote: ↑Fri Apr 16, 2021 9:07 pmWithout 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.
"When you change the way you look at things, the things you look at change." - Max Planck