BdMO Regional 2021 Secondary P4

Forum rules
Please don't post problems (by starting a topic) in the "X: Solved" forums. Those forums are only for showcasing the problems for the convenience of the users. You can always post the problems in the main Divisional Math Olympiad forum. Later we shall move that topic with proper formatting, and post in the resource section.
User avatar
Pro_GRMR
Posts:46
Joined:Wed Feb 03, 2021 1:58 pm
BdMO Regional 2021 Secondary P4

Unread post by Pro_GRMR » Tue Mar 30, 2021 1:58 am

Tiham and Shakur are playing a game. First, Tiham chooses any positive integer $a$ with $1<a\le58$. Then, Shakur chooses a positive integer $b$ with $b<a$. Let $f(a,b)$ be the smallest positive integer such that $\frac{bf(a,b)}{a}$ is an integer. Tiham's goal is to make $f(a,b)$ as large as possible while Shakur's goal is to make $f(a,b)$ as small as possible. What value should Tiham choose for $a$?
Or,
Tonmoy and Raiyan are playing a game. First, Tonmoy chooses any positive integer $n$ with $1<n\le50$. Then, Raiyan chooses a positive integer $d$ with $d<n$. $T(n,d)$ is the smallest positive integer such that $n$ divides $T(n,d) \times d$. Tonmoy's goal is to make $T(n,d)$ as large as possible while Raiyan''s goal is to make $T(n,d)$ as small as possible. What value should Tonmoy choose for $n$?
"When you change the way you look at things, the things you look at change." - Max Planck

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BdMO Regional 2021 Secondary P4

Unread post by Mehrab4226 » Tue Mar 30, 2021 12:06 pm

Pro_GRMR wrote:
Tue Mar 30, 2021 1:58 am

Tonmoy and Raiyan are playing a game. First, Tonmoy chooses any positive integer $n$ with $1<n\le50$. Then, Raiyan chooses a positive integer $d$ with $d<n$. $T(n,d)$ is the smallest positive integer such that $n$ divides $T(n,d) \times d$. Tonmoy's goal is to make $T(n,d)$ as large as possible while Raiyan''s goal is to make $T(n,d)$ as small as possible. What value should Tonmoy choose for $n$?
The 2nd one came in my regional question, so I am going to just write the solution of the 2nd one.
We claim that Tonmoy should choose $47$.
Because if Tonmoy chooses a number greater than $47$, then he chooses a composite number let $n$. This will allow Raiyan to choose a factor of that number that is greater than $\sqrt{n}$. So $T(n.d)$ will be a factor of n less than $\sqrt{n}$. Going with 47 is his best bet. As this will make $T(n,d)=47$. And Raiyan won't be able to change it.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

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

Re: BdMO Regional 2021 Secondary P4

Unread post by Pro_GRMR » Tue Mar 30, 2021 12:51 pm

Mehrab4226 wrote:
Tue Mar 30, 2021 12:06 pm
Pro_GRMR wrote:
Tue Mar 30, 2021 1:58 am

Tonmoy and Raiyan are playing a game. First, Tonmoy chooses any positive integer $n$ with $1<n\le50$. Then, Raiyan chooses a positive integer $d$ with $d<n$. $T(n,d)$ is the smallest positive integer such that $n$ divides $T(n,d) \times d$. Tonmoy's goal is to make $T(n,d)$ as large as possible while Raiyan''s goal is to make $T(n,d)$ as small as possible. What value should Tonmoy choose for $n$?
The 2nd one came in my regional question, so I am going to just write the solution of the 2nd one.
We claim that Tonmoy should choose $47$.
Because if Tonmoy chooses a number greater than $47$, then he chooses a composite number let $n$. This will allow Raiyan to choose a factor of that number that is greater than $\sqrt{n}$. So $T(n.d)$ will be a factor of n less than $\sqrt{n}$. Going with 47 is his best bet. As this will make $T(n,d)=47$. And Raiyan won't be able to change it.
We can generalize this by saying that they need to choose the largest prime number possible. Because, $T(n, d) = \frac{n}{gcd(n,d)}$. If we choose a prime number the $gcd$(n, d) will always be $1$, because $d < n$. By choosing the largest prime we can also maximize the value of $n$.
Thus, we get $\boxed{53}$ for the first one and $\boxed{47}$ for the second.
Last edited by Pro_GRMR on Tue Mar 30, 2021 2:48 pm, edited 2 times in total.
"When you change the way you look at things, the things you look at change." - Max Planck

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO Regional 2021 Secondary P4

Unread post by Anindya Biswas » Tue Mar 30, 2021 1:18 pm

The first question also appeared as P4 of Higher Secondary category.
Here's the solution :
$f(a,b)$ is the smallest positive integer for which $\frac{b}{a}\times f(a,b)$ is a positive integer.
Let's simplify the fraction $\frac{b}{a}$,
$\frac{b}{a}=\frac{b/gcd(a,b)}{a/gcd(a,b)}$, which is the most simplified form.
So, $f(a,b)=\frac{a}{gcd(a,b)}$
Now, Tiham should maximize $a$ and he should also consider that no matter which number $b$ shakur chooses, $f(a,b)$ must not get smaller. And best choice for that is prime numbers. Since if $a$ is prime, then for all positive integer $b<a, gcd(a,b)=1$. So Tiham should choose $53$ which is the largest prime not exceeding $58$. (Remember, $57$ is not a prime number!) We can manually check $54,55,56,57,58$, they all produces smaller number than $53$. So, the answer is $\boxed{53}$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply