BdMO National Secondary 2020 P10

[Mursalin]

রাহুল স্থানাংক তলে $(3, 3)$ বিন্দুতে আছে। সে একধাপে হয় তার বিন্দুর একঘর উপরের বিন্দুতে যেতে পারে অথবা একঘর ডানের বিন্দুতে যেতে পারে। তার মৌলিক সংখ্যা খুবই পছন্দ, তাই সে কখনো এমন কোনো বিন্দুতে যাবে না যার ভুজ আর কোটি উভয়ই যৌগিক। সে কতভাবে $(20, 13)$ বিন্দুতে পৌঁছাতে পারে?

-----

Rahul is at $(3,3)$ on the coordinate plane. In each step, he can move one point up or one point to the right. He loves primes, and will never visit a coordinate point where both values are composite. In how many ways can he reach $(20,13)$?

[Thephysimatician]

Let A be the set of all such paths and let B be the set of all sequence of coordinates (x,y) such that both x and y are primes , if (x1,y1) is an entry of the sequence then then the next entry is (x2,y2) where x1=x2 and y2 is the smallest prime greater than y2 or vice versa and the first entry of the sequence is (3,3) and the last entry of the sequenceis(20,13). Then there is a bijection which maps A to B.So both A and B have the same number of elements. Of course the number elements in B is 12C5=792

[hu_tanim]

I think you misunderstood the problem or intentionally counted only a special case where both the co ordinates of the lattices of a particular path contain prime numbers only. But according to the conditions above, you can use a lattice who has a prime as well as a composite number as $x$ and $y$ co ordinates. For example, say $A(3,4)$, is such a lattice. Hence the answer should be far bigger than that you provided .

[Safin]

we may draw the grid and then count manually and can have the answer 210

[asif e elahi]

First of all, $(20, 13)$ can only be reached from $(19, 13)$. Notice that we can only take turns at points where both $x$ and $y$ coordinates have prime values. Which means we only have to consider points with prime coordinates, leaving us with a $6\times 4$ grid (because there are $7$ and $5$ primes in the interval $[3, 13]$ and $[3, 19]$ respectively) and we have to reach from bottom left to top right corner. This can be done in $\binom{10}{4}=210$ ways.