9
$\begingroup$

If x was a positive 4 digit number and you divide it by the sum of its digits to get the smallest value possible, what is the value of x? For example (1234 = 1234/10)

I got 1099 as my answer however I don't know if this is right or how to prove it.

$\endgroup$
  • 2
    $\begingroup$ Computer search shows that if you ask the question for k digit numbers you get the sequence $1,19,199,1099,10999,109999,1099999 ... $ I've verified the pattern out to $k = 8$ (after which I no longer have the patience to run my code). There is a natural conjecture, which could perhaps be proved by induction. $\endgroup$ – John Coleman Apr 28 at 12:25
  • 1
    $\begingroup$ The initial $1$ in the sequence $1, 19, 109, 1099, 10999, ..$ is of course arbitrary since all non-zero 1-digit numbers give the same answer. It isn't too hard to see that the argument that @OldBoy gives below generalizes to all cases which are 4 digits or more. $\endgroup$ – John Coleman Apr 28 at 14:21
  • 1
    $\begingroup$ As a possibly interesting aside, it looks like $1098$ gives the smallest integer quotient when divided by the sum of its digits. $\endgroup$ – Barry Cipra Apr 29 at 15:37
  • $\begingroup$ @BarryCipra That is an interesting observation (where by integer quotient you only count cases where the sum of the digits divides the number). For 4,5,6,7 digits the solutions are $1098, 10989, 109888, 1078999$. No clear pattern, although they are all less than the corresponding solutions for real-valued quotients. By the way -- I liked your "Misteaks" book and have recommended it to some of my calculus students on more than one occasion. $\endgroup$ – John Coleman Apr 29 at 16:36
  • $\begingroup$ @JohnColeman, thanks! Your sequence in response to my comment is oeis.org/A034727 at OEIS. $\endgroup$ – Barry Cipra Apr 29 at 17:58
27
$\begingroup$

Let $x$ be the 4-digit number ending in digit not equal to 9 with the sum of digits equal to $s$. If you increase the last digit by one, the number becomes $x+1$ and the sum of digits becomes $s+1$.

You can easily prove that:

$$\frac xs>\frac{x+1}{s+1}$$

This is true because $x>s$. So to reduce the ratio as much as possible, the last digit has to be as big as possible, which is $9$.

Now consider number $x$ with the third digit not eqaul to 9. Increase the third digit by one and the number becomes $x+10$ and the sum increases by 1. Again, you can show that:

$$\frac xs>\frac{x+10}{s+1}$$

This is true because $x>10s$. So the third digit also has to be as big as possibe. So the last two digits must be equal to 9.

Consider now the first digit and decrease it by one. The number becomes $x-1000$ and the sum becomes $s-1$.

$$\frac xs>\frac{x-1000}{s-1}$$

This is true because it is equivalent to:

$$x<1000s$$

...and you know that $s$ is certainly greater than 18 (the last two digits must be 9). So the first digit has to be as small as possible i.e. 1 and the number is of the form:

$$1a99$$

The ratio you want to minimize now becomes:

$$\frac{100a+1099}{a+19}=100-\frac{801}{a+19}$$

Minimum value is reached for minumum value of $a$ which is 0. So the solution is: 1099.

$\endgroup$
4
$\begingroup$

The answer 1099 is confirmed by the following MiniZinc model:

%  decision variable array
array[1..4] of var 0..9: digits;

var int: objective = sum([digits[i] * pow(10, i-1) | i in 1..4]) div sum(digits);

constraint digits[4] > 0; % otherwise, there would be less than 4 digits

solve minimize objective;
$\endgroup$
3
$\begingroup$

I used Python to prove that shortest posible value is '1099'.

m = []

for eve in range(1000, 10000):

    nums = list(map(int, list(str(eve))))
    m.append((nums, eve / sum(nums)))

m.sort(key=lambda x: x[1])

print(m[0])
$\endgroup$
  • 3
    $\begingroup$ Golfed: print(min((n/sum(int(d)for d in str(n)),n)for n in range(1000,10000))[1]) 73 bytes :) $\endgroup$ – Daniel Apr 29 at 4:15
  • 3
    $\begingroup$ I believe that Daniel was only aiming to make a joke linked to codegolf.stackexchange.com, since he put a smiley in the end of the comment. I don't think that post aimed to say that the code was better, $\endgroup$ – Ertxiem Apr 29 at 11:33
  • $\begingroup$ @Daniel If you haven't done so already, perhaps you could post this as a question on Code Golf. I suspect that something like J could get this down to less than 10 bytes. $\endgroup$ – John Coleman Apr 29 at 13:59
3
$\begingroup$

Write the $4$-digit number as $x = 1000a+100b+10c+d$, where $a,b,c,d$ are integers from $0$ to $9$ (and $a \neq 0$.)

You want to minimize $A = \dfrac{1000a+100b+10c+d}{a+b+c+d}$, which can be written as $$ \begin{align*} A &= \dfrac{999a+99b+9c}{a+b+c+d}+1\\ &\geq \dfrac{999a+99b+9c}{a+b+c+9} + 1 & \text{(since the numerator} > 0\text{, set } d = 9)\\ &= \dfrac{990a+90b-81}{a+b+c+9} + 10\\ &\geq \dfrac{990a+90b-81}{a+b+9+9} + 10 & \text{(since the numerator} > 0\text{, set } c = 9)\\ &= \dfrac{900a-18\times90-81}{a+b+9+9} + 100\\ &= \dfrac{900a-1701}{a+b+18} + 100\\ &\geq \dfrac{900\times 1-1701}{1+b+18} + 100 & \text{(since the } \textbf{denominator} > 0\text{, set } a = 1)\\ &\geq \dfrac{900-1701}{1+0+18} + 100, & \text{(since the numerator} < 0\text{, set } b = 0)\\ \end{align*} $$ and the minimum attains when $x = 1099$.

$\endgroup$
  • $\begingroup$ +1 and this method answers the question for $n$ digit numbers. $\endgroup$ – Ethan Bolker Apr 28 at 21:59
  • 1
    $\begingroup$ Since $18 \cdot 90 + 81 = 1620 + 81 = 1701$, shouldn't you have $\frac{900a - 1701}{a + b + 18} + 100$? $\endgroup$ – N. F. Taussig Apr 29 at 9:50
  • $\begingroup$ Ahh you’re right. Thanks. $\endgroup$ – Jerry Chang Apr 29 at 10:36

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.