Author |
Topic: A Sum Of Digits Puzzle (Read 1606 times) |
|
K Sengupta
Senior Riddler
Gender: 
Posts: 371
|
 |
A Sum Of Digits Puzzle
« on: May 30th, 2006, 8:38pm » |
 Quote  Modify
|
Determine all possible two digit positive integers N
for which the sum of digits of 10N - N is divisible by 170.
What would be the solution if the number of digits of N is 3 instead of 2?
|
|
 IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: A Sum Of Digits Puzzle
« Reply #1 on: Jun 5th, 2006, 7:41pm » |
Quote Modify
|
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
|
| « Last Edit: Jun 5th, 2006, 7:42pm by Noke Lieu » |
IP Logged |
a shade of wit and the art of farce.
|
|
|
K Sengupta
Senior Riddler
Gender:
Posts: 371
|
|
Re: A Sum Of Digits Puzzle
« Reply #2 on: Jun 9th, 2006, 11:35am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 9th, 2006, 11:44am by K Sengupta » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Sum Of Digits Puzzle
« Reply #3 on: Jun 9th, 2006, 11:47am » |
Quote Modify
|
on Jun 9th, 2006, 11:35am, 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
|
|
IP Logged |
--SMQ
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: A Sum Of Digits Puzzle
« Reply #4 on: Jun 12th, 2006, 5:23am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: A Sum Of Digits Puzzle
« Reply #5 on: Jun 14th, 2006, 10:35am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print