Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
i understand the first requirement of this puzzle but i dont understand n+1 thing... :\ – manshu Feb 15 at 11:07
1  
@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" – Falco Feb 15 at 14:04
    
@Falco ah..thanks. I thought it was "(decimal digit of sum of n) + 1 is a multiple of 17", which was quite impossible. – manshu Feb 15 at 14:39
up vote 21 down vote accepted

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

share|improve this answer
    
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). – Michael Seifert Feb 15 at 22:14
    
@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. – Sleafar Feb 16 at 6:58
1  
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. – Michael Seifert Feb 16 at 13:16

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.

share|improve this answer

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.

share|improve this answer

889,999,999,999,999,999,999

... is one solution. I can't find a smaller one, is this proof enough? ;)

share|improve this answer
6  
Considering that the other answers have a smaller number, it's not proof enough :P – f'' Feb 15 at 2:26
    
I surely agree! Although my difference to the solution is relatively simple, just remove the trailing seventeen $9$s. – bers Feb 15 at 14:39

N=458

Because:

4 + 5 + 8 = 17

and:

N + 1 = 459 = 17 * 27

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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