## BdMO National Junior 2020 P10

Mursalin
Posts:68
Joined:Thu Aug 22, 2013 9:11 pm
BdMO National Junior 2020 P10
সকাল দা সবচেয়ে বড় ধনাত্মক পূর্ণসংখ্যা $$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.

Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Contact:

### Re: BdMO National Junior 2020 P10

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

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?

Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm