BdMO Online Forum

সকাল দা সবচেয়ে বড় ধনাত্মক পূর্ণসংখ্যা \(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\).)

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

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?

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

whats the problem? if we think 363 as n then it fufills all the conditions

$363\times2=726$, it has a $7$ in it's digits. But a base $7$ number cannot have a $7$ in it.

oh i forgot that