wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> A Sum Of Digits Puzzle
        
(Message started by: K Sengupta on May 30^th, 2006, 8:38pm)

Title: A Sum Of Digits Puzzle
Post by K Sengupta on May 30^th, 2006, 8:38pm

Determine all possible two digit positive integers N
for which the sum of digits of 10^N - N is divisible by 170.
What would be the solution if the number of digits of N is 3 instead of 2?

Title: Re: A Sum Of Digits Puzzle
Post by Noke Lieu on Jun 5^th, 2006, 7:41pm

I suspect that this has been left alone because people are suspicious of it being easy...

Being just smart enough to suspect it's a trap, but not know why, here is my effort.

we only have to look at the first couple of mulitples of 170, 340, 510, 680, 850.
The digits will comprise chiefly 9s.
Thus
18 x 9 +8
37 x 9 +7
56 x 9 +6
75 x 9 +5
94 x 9 +4

for two digit N 10N - N yeilds a string of (N-2) nines

Title: Re: A Sum Of Digits Puzzle
Post by K Sengupta on Jun 9^th, 2006, 11:35am

On Jun 5th, 2006, 7:41pm, Noke Lieu wrote.

Quote:

................ here is my effort.

Bravo, NL.

The raison d'etre of your solution precisely corresponds to that of my proposed resolution of the puzzle and the full textual representation of the foregoing is furnished below.

Let, f(x) = 10^x – x and g(x) = 99…….99( x-2 times).
Then, f(N) = 100*g(N) + u(N); where u(N) = 100 – N.
Let, the minimum value of N, for 10< = N < = 99, be given by N= r.
Then, f(r) = 100*g(r) + 10*s +t; where 10*s + t = 100 –r.
So, s.o.d.(f(r)) = 9(r-2) + s+ t.
Also, f(r+19) = 100*g( r+19) + 10(s-2)+(t+1);
giving, s.o.d.(f(r+19)) = 9(r-2)+ 9*19 + s+t-1 = s.o.d.(f(r)) + 170.
Hence, by induction s.o.d.(f(r + 19p)) = s.o.d.(f(r)) + 170*p, where p is a positive integer, whereby r+19p<=99.
Hence, s.o.d.(f(r + 19*p)) is divisible by 170 iff s.o.d.(f(r)) is divisible by 170, whenever r+19*p <=99.
But, 170 = 9*18 +8.
Since, 10(10-8) +0 = 20 = 18+2; it follows that r=20, giving N = 20+19*p.
Accordingly, N = 20, 39, 58, 77 and 96 are the only two digit integers satisfying all the conditions of the problem under reference.

(Note: I must confess that I am not completely certain of the veracity of our solutions).

Now, if we could derive a similar formula for 3 digit positive integers or prove the non-feasibility of a solution.

Title: Re: A Sum Of Digits Puzzle
Post by SMQ on Jun 9^th, 2006, 11:47am

on 06/09/06 at 11:35:45, K Sengupta wrote:

(Note: I must confess that I am not completely certain of the veracity of our solutions).

I have verified your solutions by brute-force computer search. I also have the answer to the 3-digit variant by the same means, but I won't give it away until someone proposes an analytical solution.

--SMQ

Title: Re: A Sum Of Digits Puzzle
Post by Sjoerd Job Postmus on Jun 12^th, 2006, 5:23am

We have several equations:

10^n - n = 100*(10^(n-2)-1) + 100 - n
SumOfDigits(10^n - n) = (n-2)*9 + SumOfDigits(100 - n)

SumOfDigits(...) must be divisable by 170. Now, at first, we notice that 170 = 2 * 5* 17, which makes it tough ;)

Now, here's a divis. test for 17:
Test for divisibility by 17. Subtract five times the last digit from the remaining leading truncated number. If the result is divisible by 17, then so was the first number. Apply this rule over and over again as necessary.
Example: 3978-->397-5*8=357-->35-5*7=0. So 3978 is divisible by 17.

So, we have (n-2)*9 + 100 - n
Which should be divisable by 170...
Ok, let's pay a bit more attention...

Let's first note that if n = 21, (n-2)*9 = 170 + 1 (close ;) )

n | (n-2) | (n-2)*9 % 170
21 | 19 | 1
40 | 38 | 2
59 | 57 | 3
78 | 76 | 4
97 | 95 | 5

Ok... I don't know why I've done this, but who cares ;)

Ok, so, we know that (n-2)*9 + 100 - n must be a multiple of 170, so it must end in a 0.

9n - 18 + sumOfDigits(100 - n)

The hard part is the sum of the last two digits... Can we express that as a function of n?

Anyhow, we know that 1 (0+1) <= sumOfDigits(100-n) <= 18 (8+9)
Using this knowledge, we can probably discard quite a lot of numbers. Take - for example - n = 26.
The first couple of digits would evaluate to 216, and the remaining two digits would have to exceed over 120, no chance!

So, we can already make some upper/lower bounds... ;)

Let's take several multiples of 170.
170
340
510
680
850
The following numbers would yield something too large!

Now, let's denote S as the Sum Of Digits, and establish some possible bounds
152 <= S <= 170
322 <= S <= 340
492 <= S <= 510
662 <= S <= 680
832 <= S <= 850

Then, analyse these situations:
152 <= S <= 170. This would leave 18.88 <= n <= 20.88
Now, this gives us n = 19, or n = 20.
n = 19 => n-2 = 17 => (n-2)*9 = 153
Now, let's get SumOfDigits(100-n). We stated: n = 19, so the sum will be 9. Which is obviously wrong.
Let's glance over 20 then.
n = 20 => n-2 = 18 => (n-2)*9 = 162
SumOfDigts(100-n) = SumOfDigits(80) = 8
162 + 8 = 170. D'oh! This works. Adding to list ;)

322 <= S <= 340
37.77 <= n <= 39.77
This leaves n = 38 and n=39. Using same method as above, we find that n=39 does the job.

Doing the same for the other bounds for S, giving bounds for n, giving another solution after checking only two answers, we find that all the solutions are 19 apart.
I think it might make some sense.
If we increase n by 19, we increase the sum of the first (n-2) nines by 171. On the other hand, we also substract one from the sum of the remaining digits.

n = 20
n = 39
n = 58
n = 77
n = 96

Title: Re: A Sum Of Digits Puzzle
Post by Sjoerd Job Postmus on Jun 14^th, 2006, 10:35am

Just curious, to any readers that might have read it...

What do you think of my explenation? Does it make sense? Is it easy to understand? And how is it in relation to the other method?

There are parts that're just plain wrong though, and it could probably be summarized into a shorter post having only the right parts... leading to an easy road.

I'll probably be posting an all-correct post soon too, just to make sure my method is also clear.

:) again: I'd like to hear your honest opinions.