Number theory / decimal representation

Question

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

Answer 1

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.