BdMO Online Forum

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$?

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.

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.

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}$.