BdMO National Higher Secondary 2020 P10

[Mursalin]

বৃষ্টি একটা বিশেষ সেট \(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\)?

[Mehrab4226]

Picking this up, as nationals are near, if there is any right time to post a solution to this problem, it must be now!

[nimon]

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

[Mehrab4226]

যেকোনো ধাপে সে একটা পূর্ণসংখ্যা 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.

[Anindya Biswas]

Does $\pm14$ and $\pm21$ belongs to $A$? That's where I am stuck!

[Mehrab4226]

Does $\pm14$ and $\pm21$ belongs to $A$? That's where I am stuck!

I think we can only get the factors of $42$.

[Anindya Biswas]

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

[Anindya Biswas]

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

[Mehrab4226]

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.