## BdMO National Secondary 2020 P10

Mursalin
Posts:68
Joined:Thu Aug 22, 2013 9:11 pm
BdMO National Secondary 2020 P10
রাহুল স্থানাংক তলে $(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)$?
This section is intentionally left blank.

Thephysimatician
Posts:6
Joined:Sun Dec 13, 2020 6:51 pm

### Re: BdMO National Secondary 2020 P10

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
Posts:1
Joined:Tue Apr 20, 2021 5:03 pm

### Re: BdMO National Secondary 2020 P10

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
Posts:1
Joined:Fri Jan 27, 2023 11:09 am

### Re: BdMO National Secondary 2020 P10

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

asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
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.