3
$\begingroup$

Prove that for any $n\in\mathbb{N}$ there exists a number $m\in\mathbb{N}$ such that the decimal representation of $m^2$ has $n$ ones at the beginning and some combination of $n$ ones and twos at the end.


This is the high school olympiad problem and nothing else is given. I can only show some results on the first part of the problem. Here is what I have so far:

Given $n$, there exists an integer $p$ such that the decimal representation of $p$ starts with $n$ ones.

Proof. Take $c = \underbrace{111\!\dots\!11}_{n \text{ times}}\cdot 10^k$ and $d = \underbrace{\!111\!\dots\!1\!\!}_{n-1 \text{ times}}\ 2\!\cdot 10^k = c + 10^k$, $k$ is a positive integer. Then $$ \sqrt{c} - \sqrt{d} = \dfrac{c-d}{\sqrt{c} + \sqrt{d}} \approx \frac{10^{k}}{2\cdot 10^{(n-1+k)/2}}> \frac{10^k}{2\cdot 10^{k-1}}>1 $$ The last estimate holds as long as $k>n+1$, because $10^{(n-1+k)/2}<10^{k-1} \implies \frac{n+1}{2}<\frac{k}{2}$.

In this way, there is an integer number $p$ such that $\sqrt{c}<p<\sqrt{d}$ and $p^2 = \underbrace{111\!\dots\!11}_{n \text{ times}}\cdot 10^k + S$, where $0<S<10^k$.


How to approach the second half, the one about $n$-long combination of 1 and 2 at the end of $m^2$?

$\endgroup$
3
  • $\begingroup$ This is false for $n=1$. Neither 11 nor 12 is a square. Is there any more information? $\endgroup$
    – user208649
    Commented May 23, 2015 at 5:35
  • 3
    $\begingroup$ For $n=1$ we have $k = 1 \implies k^2=1$. In this case the first digit is also the last digit and equals to 1. $\endgroup$
    – user242823
    Commented May 23, 2015 at 5:41
  • $\begingroup$ In this question I tell the origin of the problem and give my calculations Why was it put on hold? $\endgroup$
    – user242823
    Commented May 23, 2015 at 8:48

1 Answer 1

1
$\begingroup$

For the first part: Take $T_n:=3333....333333$ n+1 times, then $T_n^2=1111...1111 0 88888....8888 9$, with $n$ times the 1, and $n$ times the 8.

For the second part: take $b_1=1$, $b_0=1$. Then $k_2=11=\sum_{i=0}^1 b_i 10^i$, and $k_2^2\equiv 121\mod 1000$.

Now take $b_2:=5$. Then $k_3=511=\sum_{i=0}^2 b_i 10^i$ and $k_2^2\equiv 1121\mod 10^4$.

Now take $b_3:=5$. Then $k_3=5511=\sum_{i=0}^3 b_i 10^i$ and $k_3^2\equiv 71121\mod 10^5$.

Now take $b_4:=2$. Then $k_4=25511=\sum_{i=0}^4 b_i 10^i$ and $k_4^2\equiv 811 121\mod 10^6$.

Now take $b_5:=2$. Then $k_5=225511=\sum_{i=0}^5 b_i 10^i$ and $k_5^2\equiv 5 211 121\mod 10^7$.

Now take $b_6:=3$. Then...

In general, assume you have constructed $$k_r=\sum_{i=0}^r b_i 10^i$$ such that $k_r^2\equiv \sum_{j=0}^{r+1}a_j 10^j\mod 10^{r+2}$ with $a_i\in\{1,2\}$ for $i=0,\dots,r$. Then take $b_{r+1}$ such that $a_{r+1}+2b_{r+1}\in\{11,12\}$.

Then $$k_{r+1}=\sum_{i=0}^{r+1} b_i 10^i$$ satisfies $k_{r+1}^2\equiv \sum_{j=0}^{r+2}a_j 10^j\mod 10^{r+3}$ with $a_i\in\{1,2\}$ for $i=0,\dots,r+1$.

Finally take $m=T_n 10^{n+1}+k_n$. Then the decimal representation of $m^2$ has $n$ ones at the beginning and some combination of $n$ ones and twos at the end.

$\endgroup$

You must log in to answer this question.