8
$\begingroup$

I want to show that there is not an integer with digits of only $0$ and $1$ that has at least two $1$ and is a complete square number. I tried to prove it by induction, but I couldn't.

$\endgroup$
7
  • $\begingroup$ What did you try to induct on? The number of digits or the number of 1s? $\endgroup$
    – Randall
    Aug 14, 2017 at 16:57
  • $\begingroup$ The number of digits! @Randall if we add a 1 to the number, it will be $10a+1$ and if we add 0 it will be $10a$, where a is a number with n-1 digits,but I can't prove that it is not square! $\endgroup$
    – user192508
    Aug 14, 2017 at 16:59
  • $\begingroup$ You mean the question??? I think so... @ThomasAndrews $\endgroup$
    – user192508
    Aug 14, 2017 at 17:08
  • $\begingroup$ I meant, is there a reason you think there is no such number? For example, if it is from a problem set, there is often reason to believe it is true. :) $\endgroup$ Aug 14, 2017 at 17:10
  • 6
    $\begingroup$ Seems to be a rather hard question. $\endgroup$ Aug 14, 2017 at 17:40

1 Answer 1

2
$\begingroup$

Not an answer, just a bunch of necessary conditions. So suposse that $N$ has only zeros and ones, is a square but not a power of $10$:

  • If there exists such a number, then there exists one that ends with $1$. Indeed, if $N$ ends with zero, then it must have an even number of trailing zeros. If you remove them, the result must be a perfect square. From now, assume that $N$ ends with $1$.
  • $\sqrt N$ ends with $1$ or $9$, and begins with $3$ or $1$.
  • The number of ones, $k$, is congruent to $N$ modulo $9$. Then $k$ must be a square modulo $9$. That is $k\equiv 0,1,4\text{ or }7\pmod 9$.
  • The penultimate digit is $0$, because $11$ is not a square modulo $100$.
  • $\sqrt N\equiv \pm1\pmod{50}$ (thanks to Thomas Andrews).

I'll edit this "answer" if I find more of them.

An heuristic reasoning: the probability that a number of at most $n$ digits has only ones and zeros is $1/5^n$. And that it is a perfect square is $1/10^{n/2}$. Assuming that both events are independent, the probability that both conditions hold for the same number is $1/(5\sqrt{10})^n$, which is lesser than $1/10^n$. So... probably, the answer is no.

$\endgroup$
7
  • 1
    $\begingroup$ It actually ends in $01$. You have that $\sqrt{N}=50k\pm 1$. $\endgroup$ Aug 14, 2017 at 18:07
  • $\begingroup$ And you can show that $k$ is divisible by $5$. But it gets messier from there. $\endgroup$ Aug 14, 2017 at 18:08
  • $\begingroup$ @ThomasAndrews The $k$ of your second comment is my $k$ or your $k$? $\endgroup$
    – ajotatxe
    Aug 14, 2017 at 18:10
  • $\begingroup$ Sorry, my $k{}{}{}.$ $\endgroup$ Aug 14, 2017 at 18:11
  • $\begingroup$ Re: the heuristic, aren't there $9*10^{n-1}$ $n$-digit numbers? $\endgroup$
    – Ivoirians
    Aug 14, 2017 at 18:48

You must log in to answer this question.