8
$\begingroup$

I found this currently unsolved problem in the AOPS site (link):

Let $n$ be a positive integer with exactly $d$ non-zero digits. Show that there is a multiple of $n$ which has exactly $d+1$ non-zero digits.

It seems to be quite challenging and I have no idea how to solve it. Any hints how to proceed?

$\endgroup$
  • $\begingroup$ Interesting problem! Could be out of reach. $\endgroup$ – Peter Aug 8 '18 at 22:35
  • $\begingroup$ How many digits does $n$ have? Is it $d$ or more? $\endgroup$ – user582949 Aug 10 '18 at 18:45
  • $\begingroup$ @user582949 $n$ can have more than $d$ digits: $d$ are nonzero and the others are zero. $\endgroup$ – Frank S Aug 10 '18 at 20:36
5
+50
$\begingroup$

You can combine three simple tricks to solve the problem:

  1. Take a digit greater than $1$, and split it into two nonzero digits by adding $10^t-10^s$.

  2. If each digit in your number $n$ is $0$ or $1$, replace $n$ by $2n$.

  3. In order to get rid of the prime factors $2$ and $5$, multiply $n$ by a power of $10$.


If $n$ has a digit greater than $1$ then let $m=n$. Otherwise, if each digit of $n$ are $0$ or $1$ then let $m=2n$. Hence $m$ is a multiple of $n$, it has the same nonzero digits as $n$, and $m$ has at least one digit grater than $1$.

Let $m=\sum_{i=0}^{k-1} a_i\cdot 10^i$ where $a_0,\ldots,a_{k-1}$ are the decimal digits of $m$ and let $g$ be an index with $a_g\ge2$.

Take two integers $t,s$ such that $s>g$, $t>s+k$ and $10^t\equiv 10^s\pmod{n}$, and choose $$ M = 10^{s-g}m + (10^t-10^s). $$ The factor $10^{s-g}$ shifts the digit $a_g$ to the $s$th position. The term $10^t-10^s$ replaces the digit $a_g$ by $a_g-1$ (which is nonzero), and adds a new leading digit $1$. Due to $t-s>k$, this leading $1$ is not added to the previous nonzero digits.

$\endgroup$
  • $\begingroup$ I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^s\equiv 10^t \pmod n$? $\endgroup$ – Allawonder Aug 15 '18 at 19:11
  • $\begingroup$ @Allawonder By the pigeonhole principle, in the infinite sequence $\{10^n\}_n$ there are infinite couples $(10^s,10^t)$ with $s\not=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$. $\endgroup$ – Robert Z Aug 15 '18 at 20:13
  • $\begingroup$ @RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $\underbrace{999...99}_{s-t \,\,\,9's}\underbrace{00...0}_{t\,\,\, 0's}.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense. $\endgroup$ – Allawonder Aug 19 '18 at 18:22
  • $\begingroup$ @Allawonder Note that $M = 10^t +10^{s-g}m -10^s$: $10^t$ increases the number of non-zero digits and $10^{s-g}m -10^s$ decreases by one the digit at $s$-position (which is at least $2$). $\endgroup$ – Robert Z Aug 20 '18 at 7:10
  • $\begingroup$ @RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^{t-s}-1).$ $\endgroup$ – Allawonder Aug 20 '18 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.