Determine the smallest integer $n \geq 0$ for which
- the decimal digit sum of n is a multiple of 17
- the decimal digit sum of $n+1$ is a multiple of 17.
No computers! The puzzle has a nice direct solution.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ i understand the first requirement of this puzzle but i dont understand n+1 thing... :\ $\endgroup$– manshuCommented Feb 15, 2016 at 11:07
-
1$\begingroup$ @manshu you have to find a number and its successor (e.g. 120 and 121 or maybe 255 and 256) and both numbers must each fulfil the condition "the sum of digits is a multiple of 17" $\endgroup$– FalcoCommented Feb 15, 2016 at 14:04
-
$\begingroup$ @Falco ah..thanks. I thought it was "(decimal digit of sum of n) + 1 is a multiple of 17", which was quite impossible. $\endgroup$– manshuCommented Feb 15, 2016 at 14:39
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
3
We know that the digit sum of $n$ is a multiple of $17$, let us write that as ($d_1$ being the least significant digit): $$d_m + d_{m-1} + ... + d_2 + d_1 = x * 17$$ If $d_1$ would be smaller than $9$ then the digit sum of $n+1$ would be $$x * 17 + 1$$ which is obviously not divisible by $17$, so $d_1$ must be $9$. If $d_2$ would be smaller than $9$, then the digit sum of $n + 1$ wold be $$x * 17 - 9 + 1 = x * 17 - 8$$ which is not divisible by $17$ again, so $d_2$ is must be $9$ well. If $d_3$ would be smaller than $9$, then the digit sum of $n + 1$ would be $$x * 17 - 9 - 9 + 1 = x*17 - 17$$ which is divisible by $17$. This means we look for the smallest number with digit sum divisible by $17$ with the last 2 digits equal $9$ and the third last digit lower than $9$. This is obviously: $$8899$$.
-
$\begingroup$ This method would generalize to a version of the puzzle where instead of multiples of 17, you wanted multiples of $9m - 1$ for integer $m$ (8, 17, 26, 35, ...) I don't think the puzzle would have solutions for multiples of any numbers that were equal to 8 (mod 9). $\endgroup$ Commented Feb 15, 2016 at 22:14
-
$\begingroup$ @MichaelSeifert Actually all numbers equal to 8 (mod 9) and their divisors will have a solution. The numbers which definitely won't have a solution are multiples of 9, because 9m-1 will be never divisible by 9. $\endgroup$– SleafarCommented Feb 16, 2016 at 6:58
-
1$\begingroup$ Good point. In fact, I think any number that's relatively prime to 9 (i.e., not a multiple of 3) will be a divisor of 9m - 1 for some m. $\endgroup$ Commented Feb 16, 2016 at 13:16
$\begingroup$
$\endgroup$
The integer in question must end with a bunch of 9s to leave the "ones to carry" to the previous digit. Hence it can be written as $abc..A9...9$ with $n$ 9s at the end and $A$ as the last digit less than 9. When we add 1 to this, it equals $abc..[A+1]0...0$, making the difference between both numbers' digit sums $9n-1$. 2 is the smallest value of $n$ allowing that expression to be divided by 17, so $n$ can be everything written as $17k+2$. Before bothering with over-17-digit numbers or something, we can simply settle for $n=2$ and fill in the few blanks we have. 9*2=18=17+1, so we at least need a bunch of digits with the sum 16, which can be the sum of 8+8 (7+9 is not allowed).
So the smallest solution is:
8899.
$\begingroup$
$\endgroup$
This is how I arrived at the solution, less formal more intuitive.
The solution is:
8899
Both numbers are only 1 apart, but need to have a digit sum which is the same or 17 (or 34,51...) apart. If you take 100 and 101 the digit sums are 1 and 2, only 1 apart, the same for 8 and 9 - in fact the only way I can get another difference than 1 in the digit sums, is when the digits swap from
xxx9 to xxx0 - e.g. 9 -> 10 (digit sums 9 and 1)
But a difference of 8 is not enough so try another 9
99 -> 100 (digit sums 18 and 1)
They are 17 apart, so this can work - the second number is just 16 short of being a multiple of 17, so I have to add digits with a sum of 16, like 8+8. This gives the result of
8899 -> 8900 (digit sums 34 and 17)
And this is also the smallest solution, since I can form a digit sum of 16 only with more digits, or as 97 or 79. And the number 9799 is bigger than 8899 and 7999 does not work, because another 9 rolls over and the successor is 8000.
$\begingroup$
$\endgroup$
2
889,999,999,999,999,999,999
... is one solution. I can't find a smaller one, is this proof enough? ;)
-
6$\begingroup$ Considering that the other answers have a smaller number, it's not proof enough :P $\endgroup$– f''Commented Feb 15, 2016 at 2:26
-
$\begingroup$ I surely agree! Although my difference to the solution is relatively simple, just remove the trailing seventeen $9$s. $\endgroup$– bersCommented Feb 15, 2016 at 14:39
$\begingroup$
$\endgroup$
N=458
Because:
4 + 5 + 8 = 17
and:
N + 1 = 459 = 17 * 27
