BdMO National 2021 Higher Secondary Problem 9

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
BdMO National 2021 Higher Secondary Problem 9

Unread post by Anindya Biswas » Sun Apr 11, 2021 10:31 am

একটা ধনাত্মক পূর্ণসংখ্যা \(n\)-কে মনোরম বলা হবে যদি এটার কমপক্ষে \(3\)-টা প্রকৃত উৎপাদক থাকে এবং এটা তার সবচেয়ে বড় তিনটা প্রকৃত উৎপাদকের যোগফলের সমান হয়। যেমন \(6\) একটা মনোরম সংখ্যা কারণ \(6\)-এর সবচেয়ে বড় তিনটা প্রকৃত উৎপাদক হলো \(3\), \(2\), \(1\) এবং \(6=3+2+1\)। \(6000\)-এর চেয়ে বড় না, এমন কতগুলো মনোরম সংখ্যা আছে?

A positive integer $n$ is called nice if it has at least $3$ proper divisors and it is equal to the sum of its three largest proper divisors. For example, $6$ is nice because its largest proper divisors are $3,2,1$ and $6=3+2+1$. Find the number of nice integers not greater than $6000$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

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

Solution :

Unread post by Anindya Biswas » Sun Apr 11, 2021 11:11 am

Let me start with an exercise. Find three distinct positive integers $a,b,c$ where $a<b<c$ such that \[\frac1a+\frac1b+\frac1c=1\] You may post the solution below.
Well, the only solution to this equation is $(a,b,c)=(2,3,6)$.

Let's assume, $n$ is a nice integer. Let $\frac{n}{x},\frac{n}{y},\frac{n}{z}$ be the largest three proper divisor of $n$ where $\frac{n}{x}>\frac{n}{y}>\frac{n}{z}$. Then we got,
$n=\frac{n}{x}+\frac{n}{y}+\frac{n}{z}\Longleftrightarrow \frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1$
$\therefore x=2,y=3,z=6$
So, $n$ is divisible by $2,3,6$. Also, $n$ is not divisible by $4,5$ since otherwise $\frac{n}{4}$ or $\frac{n}{5}$ would be one of the largest three proper divisors which is not the case. So, we can consider this system of linear congruences to solve for $n$:
\[\begin{array} \ n\equiv0\pmod3 \\ n\equiv2\pmod{4} \\ n\equiv r\pmod{5} \end{array}\] Where $r\in\{1,2,3,4\}$
By Chinese Remainder Theorem, this congruences has unique solutions modulo $60$. So, for each value of $r$, we get a unique number between $1$ and $60$ which is nice. So, there are $4$ nice integers less than or equal to $60$.
So, there are $\boxed{400}$ nice integers not greater than $6000$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

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

Re: BdMO National 2021 Higher Secondary Problem 9

Unread post by Pro_GRMR » Sun Apr 11, 2021 2:32 pm

Anindya Biswas wrote:
Sun Apr 11, 2021 10:31 am
A positive integer $n$ is called nice if it has at least $3$ proper divisors and it is equal to the sum of its three largest proper divisors. For example, $6$ is nice because its largest proper divisors are $3,2,1$ and $6=3+2+1$. Find the number of nice integers not greater than $6000$.
This also came as Secondary Problem 10.
"When you change the way you look at things, the things you look at change." - Max Planck

User avatar
Ohin01
Posts:5
Joined:Sun Feb 14, 2021 10:04 pm

Re: Solution :

Unread post by Ohin01 » Wed Apr 14, 2021 7:09 pm

Anindya Biswas wrote:
Sun Apr 11, 2021 11:11 am
Let me start with an exercise. Find three distinct positive integers $a,b,c$ where $a<b<c$ such that \[\frac1a+\frac1b+\frac1c=1\] You may post the solution below.
Well, the only solution to this equation is $(a,b,c)=(2,3,6)$.

Let's assume, $n$ is a nice integer. Let $\frac{n}{x},\frac{n}{y},\frac{n}{z}$ be the largest three proper divisor of $n$ where $\frac{n}{x}>\frac{n}{y}>\frac{n}{z}$. Then we got,
$n=\frac{n}{x}+\frac{n}{y}+\frac{n}{z}\Longleftrightarrow \frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1$
$\therefore x=2,y=3,z=6$
So, $n$ is divisible by $2,3,6$. Also, $n$ is not divisible by $4,5$ since otherwise $\frac{n}{4}$ or $\frac{n}{5}$ would be one of the largest three proper divisors which is not the case. So, we can consider this system of linear congruences to solve for $n$:
\[\begin{array} \ n\equiv0\pmod3 \\ n\equiv2\pmod{4} \\ n\equiv r\pmod{5} \end{array}\] Where $r\in\{1,2,3,4\}$
By Chinese Remainder Theorem, this congruences has unique solutions modulo $60$. So, for each value of $r$, we get a unique number between $1$ and $60$ which is nice. So, there are $4$ nice integers less than or equal to $60$.
So, there are $\boxed{400}$ nice integers not greater than $6000$.
I just realised something :cry:
I did a similar solution like this...
Every nice integer is of this format-
6*k where k is not a multiple of 2 and 5
Which results there is 400 nice integers inside 6000 range

But unfortunately I submitted the values of 'k' for which '6k' is "not" a nice integer.I gave 600 as the answer....now I realised I absolutely forgot to substract it from 1000(there are 6000/6=1000 total values of k) to get the real answer :"(

Online national cost me a P10(Secondary) :cry:

Post Reply