BdMO National Junior 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 Junior 2020 P10

Unread post by Mursalin » Thu Feb 04, 2021 12:38 am

সকাল দা সবচেয়ে বড় ধনাত্মক পূর্ণসংখ্যা \(n\) বের করার চেষ্টা করছে, যেন \(n\)-কে base-\(7\)-এ নিয়ে গেলে তা দেখতে base-\(10\)-এ \(2n\)-এর মতো হয়। তিনি দেখলেন যে, এমন একটি সংখ্যা হলো \(156\), কারণ \(156\)-এর base-\(7\) হলো \(312\)। সকালদার বের করা সংখ্যাটি কত?
(একটা সংখ্যাকে base-\(10\)-এ লেখার মানে হচ্ছে সেটাকে দশমিক সংখ্যা পদ্ধতিতে লেখা। দশমিক সংখ্যা পদ্ধতিতে, \(234 = 200 + 30 + 4 = 2\times 10^2 + 3\times 10 + 4\times 1\)। আবার যদি \(234\) base-\(7\)-এর একটা সংখ্যা হয়, তাহলে সেটাকে base-\(10\)-এ আনার জন্য আমাদের শুধু \(10\)-কে \(7\) দিয়ে পরিবর্তন করে দিলেই হবে। যেমন, base-\(7\)-এর \(234 = 2\times 7^2 + 3\times 7 + 4\times 1 =\) base-\(10\)-এ \(123\)।)


Sakal da is trying to find the largest positive integer \(n\), such that the base-\(7\) representation of \(n\) looks like a base-10 number which is exactly \(2n\). He noticed, one such number is \(156\), because \(156\) in base-\(7\) is \(312\). What is the number he came up with?

(Writing a number in base-\(10\) means writing it in the decimal system. So, \(234 = 200 + 30 + 4 = 2\times 10^2 + 3\times 10 + 3\times 1\). If we go to base-\(7\), we just change \(10\) to \(7\). So \(234\) in base-\(7\) would be \(2\times 7^2 + 3\times 7 + 4\times 1 = 123\) in base-\(10\).)
This section is intentionally left blank.

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

Re: BdMO National Junior 2020 P10

Unread post by Anindya Biswas » Mon Feb 08, 2021 9:09 pm

Every number written in this solution is in base-$10$.
We need to find $n$ such that $n=(d_kd_{k-1}\dots d_1d_0)_7$ and $2n=(d_kd_{k-1}\dots d_1d_0)_{10}$ where $d_i$ s are digits in the base-$7$ representation of $n$. So, for each $i$, $0\leq d_i\leq 6$.
We can write the whole thing with this equation:
$\sum_{i=0}^{k}10^id_i=2\sum_{i=0}^{k}7^id_i\Leftrightarrow\sum_{i=0}^{k}(10^i-2\cdot7^i)d_i=0$.
Let's call $2n$ a good number if $n$ has the desired properties given in this question.

Lemma-1 : For integer $m\geq3$, $10^m-2\cdot7^m>30$
Proof:
Base case : For $m=3$, $10^m-2\cdot7^m=314>30$, so our lemma is true for $m=3$.
Induction hypothesis : Let's assume the lemma is true for $m=j$.
Inductive step : For $m=j+1$,
$10^{j+1}-2\cdot7^{j+1}=3\cdot10^j+7(10^j-2\cdot7^j)>30$
So, our lemma is true for $m=j+1$, that completes our proof of this lemma using induction.

Claim-1 : There is no good number with more than $3$ digits in base-$10$
For this, we will assume that $k\geq3$ and prove that the minimum value of $S_k=\sum_{i=0}^{k}(10^i-2\cdot7^i)d_i>0$.
Proof :
To achieve the minimum value of $S_k$, we need $d_k=1$, since the most significant digit or the first digit is nonzero and as small as possible.
We also need $d_i=0$ when $i\neq k$ and $10^i-2\cdot7^i>0$ and $d_i=6$ when $10^i-2\cdot7^i<0$.
That means we will minimize the value of $d_i$ when we are adding a non-negative term and maximize it when we are adding a negative term to make sure we are adding the minimum possible and subtracting the maximum possible to get the minimum value of $S_k$.
But $10^i-2\cdot7^i<0$ only when $i\in\{0,1\}$. For $i=2$, $10^i-2\cdot7^i=2$ and the case $i>2$ has been explored in lemma-$1$
So, the minimum value of $S_k=(10^k-2\cdot7^k)\cdot1+(10^1-2\cdot7^1)\cdot6+(10^0-2\cdot7^0)\cdot6=(10^k-2\cdot7^k)-30$
By lemma-$1$, $S_k\geq min(S_k)=(10^k-2\cdot7^k)-30>0$ for $k\geq3$.
But $S_k=0$ is a neccessary condition for such a good number to exist and we just proved that this is not possible for $k\geq3$. Or, equivalently, there is no good number with more than $3$ digits. So, claim-$1$ is pretty much proved.

So, now we can finally and peachfully give all of our attention to $k=2$ case. :P :P
$S_2=2d_2-4d_1-d_0=0$
To get the largest possible number, let's take our most significant digit $d_2=6$ [Remember that $d_i$ is a digit in base $7$, so $0\leq d_i\leq 6$]
So, our equation becomes:
$12=4d_1+d_0$
Similarly, maximum possible value of $d_1$ is $3$ and this forces $d_0=0$.
That means, the largest good number $2n=630\Leftrightarrow n=315$.
It is easy to check that $n=315$ has the desired properties. [Actually it's already proven]

Bonus :
Here's a complete list of such numbers:
$0,51,102,105,153,156,207,210,258,261,312,315$. :cry:
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

204198
Posts:1
Joined:Fri Jun 04, 2021 7:59 pm

Re: BdMO National Junior 2020 P10

Unread post by 204198 » Wed Jun 09, 2021 4:03 pm

Well, if you think 726 as a 10 base number, then we get 363 as it's 7 base number. 726=2×363, so how can 315 be the required number?

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

Re: BdMO National Junior 2020 P10

Unread post by Anindya Biswas » Wed Jun 09, 2021 11:01 pm

204198 wrote:
Wed Jun 09, 2021 4:03 pm
Well, if you think 726 as a 10 base number, then we get 363 as it's 7 base number. 726=2×363, so how can 315 be the required number?
Read the question again
"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