BdMO National Higher Secondary 2020 P10

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Mursalin
Posts:68
Joined:Thu Aug 22, 2013 9:11 pm
Location:Dhaka, Bangladesh.
BdMO National Higher Secondary 2020 P10

Unread post by Mursalin » Mon Feb 08, 2021 4:04 pm

বৃষ্টি একটা বিশেষ সেট \(A\) বানাতে চায়। সে \(A=\{0, 42\}\) দিয়ে শুরু করে। যেকোনো ধাপে সে একটা পূর্ণসংখ্যা \(x\)-কে \(A\)-তে ঢুকাতে পারবে যদি \(x\), \(A\)-তে ইতোমধ্যে থাকা সংখ্যাগুলোকে সহগ হিসেবে ব্যবহার করে বানানো কোনো বহুপদীর মূল হয়। এভাবে সে \(A\)-এ নতুন নতুন পূর্ণসংখ্যা ঢুকাতেই থাকে। যখন সে \(A\)-এ আর ঢুকানোর মতো নতুন সংখ্যা খুঁজে পাবে না, তখন \(A\)-তে কয়টা সংখ্যা থাকবে?


Bristy wants to build a special set \(A\). She starts with \(A=\{0, 42\}\). At any step, she can add an integer \(x\) to the set \(A\) if it is a root of a polynomial that uses the already existing integers in \(A\) as coefficients. She keeps doing this, adding more and more numbers to \(A\). After she eventually runs out of numbers to add to \(A\), how many numbers will be in \(A\)?
This section is intentionally left blank.

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

Re: BdMO National Higher Secondary 2020 P10

Unread post by Mehrab4226 » Thu Apr 01, 2021 11:27 pm

Picking this up, as nationals are near, if there is any right time to post a solution to this problem, it must be now!
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é

nimon
Posts:8
Joined:Sat Mar 27, 2021 7:30 am

Re: BdMO National Higher Secondary 2020 P10laim

Unread post by nimon » Fri Apr 02, 2021 11:08 am

যেকোনো ধাপে সে একটা পূর্ণসংখ্যা x-কে A-তে ঢুকাতে পারবে যদি x, A-তে ইতোমধ্যে থাকা সংখ্যাগুলোকে সহগ হিসেবে ব্যবহার করে বানানো কোনো বহুপদীর মূল হয়।
Can you give more explaination to this line?

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

Re: BdMO National Higher Secondary 2020 P10laim

Unread post by Mehrab4226 » Fri Apr 02, 2021 11:16 am

nimon wrote:
Fri Apr 02, 2021 11:08 am
যেকোনো ধাপে সে একটা পূর্ণসংখ্যা x-কে A-তে ঢুকাতে পারবে যদি x, A-তে ইতোমধ্যে থাকা সংখ্যাগুলোকে সহগ হিসেবে ব্যবহার করে বানানো কোনো বহুপদীর মূল হয়।
Can you give more explaination to this line?
There are some integers in A. If you make a polynomial with coefficients are integers from A, and one of the roots of the polynomial is an integer $k \notin A$. Then you can add k in A.
For example,
$42x+42$is a polynomial with coefficients from A and root $-1$, but $-1$ is not in A, so we can add him in A. This process continues now $A=\{-1,0,42\}$. And other polynomials can also have degree more than 1.
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
Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO National Higher Secondary 2020 P10

Unread post by Anindya Biswas » Fri Apr 02, 2021 9:13 pm

Does $\pm14$ and $\pm21$ belongs to $A$? That's where I am stuck!
"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
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BdMO National Higher Secondary 2020 P10

Unread post by Mehrab4226 » Fri Apr 02, 2021 10:00 pm

Anindya Biswas wrote:
Fri Apr 02, 2021 9:13 pm
Does $\pm14$ and $\pm21$ belongs to $A$? That's where I am stuck!
I think we can only get the factors of $42$.
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
Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO National Higher Secondary 2020 P10

Unread post by Anindya Biswas » Fri Apr 02, 2021 10:14 pm

Mehrab4226 wrote:
Fri Apr 02, 2021 10:00 pm
Anindya Biswas wrote:
Fri Apr 02, 2021 9:13 pm
Does $\pm14$ and $\pm21$ belongs to $A$? That's where I am stuck!
I think we can only get the factors of $42$.
Yeah we can only get the factors of $42$ but I have no idea about this two factors, others somehow got into $A$.
"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:263
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO National Higher Secondary 2020 P10

Unread post by Anindya Biswas » Sun Apr 04, 2021 4:54 pm

Sorry, but I could not resist posting the solution!
Let $S$ be the final set.
We will show that $x\in S$ if and only if $x=0$ or $x|42$.
We will demonstrate for each case.
  1. $-1\in S$
    $42x+42=0\Longrightarrow x=-1$
  2. $6,-7\in S$
    $-x^2-x+42=0\Longrightarrow x^2+x-42=0\Longrightarrow(x-6)(x+7)=0\Longrightarrow x_1=6,x_2=-7$
  3. $2,-3\in S$
    $-x^2-x+6=0\Longrightarrow x^2+x-6=0\Longrightarrow (x-2)(x+3)=0\Longrightarrow x_1=2,x_2=-3$
  4. $-2,1\in S$
    $-x^2-x+2=0\Longrightarrow x^2+x-2=0\Longrightarrow (x-1)(x+2)=0\Longrightarrow x_1=1,x_2=-2$
  5. $14,21\in S$
    $-3x+42=0\Longrightarrow x=14$
    and $-2x+42=0\Longrightarrow x=21$
  6. $a\in S\Longrightarrow -a\in S$
    $x+a=0\Longrightarrow x=-a$
So far, we've got $M=\{0,\pm1,\pm2,\pm3,\pm6,\pm7,\pm14,\pm21,\pm42\}\subseteq S$
Here, observe that $x\in M$ if and only if $x=0$ or $x|42$.
Now we will show that $M=S$.
$\text{Proof :}$
Let's assume $a\in S$. Let $P$ be a polynomial such that $P(x)=x^k\cdot Q(x)$ where $k$ is a nonnegative integer and $Q$ is a polynomial with nonzero constant term and each coefficient of $P(x)$ is an element of $M$ and $P(a)=0$.
Now, if $a=0$ then $a\in M$
Now, let's assume $a\neq0$.
$\therefore Q(a)=0$.
Let $q$ be the constant term of $Q$.
By rational root theorem, we know that $a|q$. But since $q\in M$ and $q\neq0$, that means $q|42$. So, we conclude that $a|42$.
$\therefore a\in M\Longrightarrow S\subseteq M$
$\therefore S=M$
So, our answer should be $\boxed{|S|=17}$
Last edited by Anindya Biswas on Mon Apr 05, 2021 1:00 am, edited 1 time in total.
"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
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BdMO National Higher Secondary 2020 P10

Unread post by Mehrab4226 » Sun Apr 04, 2021 11:11 pm

Anindya Biswas wrote:
Sun Apr 04, 2021 4:54 pm
Sorry, but I could not resist posting the solution!
Let $S$ be the final set.
We will show that $x\in S$ if and only if $x=0$ or $x|42$.
We will demonstrate for each case.
  1. $-1\in S$
    $42x+42=0\Longrightarrow x=-1$
  2. $6,-7\in S$
    $-x^2-x+42=0\Longrightarrow x^2+x-42=0\Longrightarrow(x-6)(x+7)=0\Longrightarrow x_1=6,x_2=-7$
  3. $2,-3\in S$
    $-x^2-x+6=0\Longrightarrow x^2+x-6=0\Longrightarrow (x-2)(x+3)=0\Longrightarrow x_1=2,x_2=-3$
  4. $-2,1\in S$
    $-x^2-x+2=0\Longrightarrow x^2+x-2=0\Longrightarrow (x-1)(x+2)=0\Longrightarrow x_1=1,x_2=-2$
  5. $14,21\in S$
    $-3x+42=0\Longrightarrow x=14$
    and $-2x+42=0\Longrightarrow x=21$
  6. $a\in S\Longrightarrow -a\in S$
    $x+a=0\Longrightarrow x=-a$
So far, we've got $M=\{0,\pm1,\pm2,\pm3,\pm6,\pm7,\pm14,\pm21,\pm42\}\subseteq S$
Here, observe that $x\in M$ if and only if $x=0$ or $x|42$.
Now we will show that $M=S$.
$\text{Proof :}$
Let's assume $a\in S$. Let $P$ be a polynomial such that $P(x)=x^k\cdot Q(x)$ where $k$ is a nonnegative integer and $Q$ is polynomial with nonzero constant term and each coefficient of $P(x)$ is an element of $M$ and $P(a)=0$.
Now, if $a=0$ then $a\in M$
Now, let's assume $a\neq0$.
$\therefore Q(a)=0$.
Let $q$ be the constant term of $Q$.
By rational root theorem, we know that $a|q$. But since $q\in M$ and $q\neq0$, that means $q|42$. So, we conclude that $a|42$.
$\therefore a\in M\Longrightarrow S\subseteq M$
$\therefore S=M$
So, our answer should be $\boxed{|S|=17}$
Thank you, I was looking for a solution for a long time. :) :)
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é

Post Reply