Like I said, I do not have a proper (2 min) solution...still thinking...
However, I applied some heuristics and lots of good old brute force to calculate the answer.
WARNING: This is very very ugly solution and is certainly not recommended, but this is all I could do in about 2 hours I spent on this LOL
Apologies for the length of the post...
Alright let's start...man, this is gonna hurt
Solution:The highest sum for a 3 digit number is 27 (9 + 9 + 9).
So, I started playing by listing the combinations for sum 1,2, and 3.
Sum = 1:
For the sum to be equal to 1, the 3 digits must be different combinations of 0,0,1
To find the number of combinations, we can see that we are arranging 0 and 1 in three slots, but there are 2 zeros.
Number of unique ways to arrange 3 items where 2 of the items are identical is: 3!/2! = 3 (Number of items!/number of identical items!)
So we have 3 unique combinations: 001, 010, 100
Now, we have added complexity of each uniques combination combining with any other combination on either side of a 6 digit number.
That is, 001 010 is different from 010 001.
So, let us list the combinations:
001 001 010 001 100 001
001 010 010 010 100 010
001 100 010 100 100 100
Arranging the 3 unique combinations in 2 (left/right) slots when each combination can also combine with itself (001 001) is 3^2= 9
Sum = 2
The digits that can be used to get sum of 2, are 002, 011
002 : 3!/2! = 3 (number of ways to arrange 3 items when 2 are identical)
011 : 3!/2! = 3 (number of ways to arrange 3 items when 2 are identical)
Total ways: 3+3 = 6
Accounting for left/right combinations: 6^2 = 36
Sum = 3
The digits that can be used to get sum of 3, are 003, 021, 111
003 : 3!/2! = 3
021 : 3! = 6 (no identical digits)
111 : 3!/3! = 1
Total ways: 3+6+1 = 10
Accounting for left/right combinations: 10^2 = 100
Wait a minute..... Sum: 1 : Total Ways = 3
Sum: 2 : Total Ways = 6
Sum: 3 : Total Ways = 10
Ways(Sum: 1) = Ways(Sum: 0) + 2 = 3 [Ways(Sum: 0) = 3!/3! = 1 (only combination 000)]
Ways(Sum: 2) = Ways(Sum: 1) + 3 = 3 + 3 = 6
Ways(Sum: 3) = Ways(Sum: 2) + 4 = 4 + 4 = 10
Could it be, that the difference between the number of ways for consecutive sum, is one more than the difference between the previous two number of ways.
That is, Ways(Sum: x) = Ways(Sum: x-1) + [Ways(Sum:x-1) - Ways(Sum:x-2) + 1]
Ok let's try Sum:4
Ways(Sum: 4) = Ways(Sum: 3) + [Ways(Sum:3) - Ways(Sum:2) + 1]
Ways(Sum: 4) = = 10 + [10-6+1] = 15
Is it??...let's check...
Sum = 4
The digits that can be used to get sum of 4, are 004, 031, 022, 211
004 : 3!/2! = 3
031 : 3! = 6 (no identical digits)
022 : 3!/2! = 3
211 : 3!/2! = 3
Total ways: 6+3+3+3 = 15 = which is what our pattern formula gave above!
So using the pattern, we can now find the number of ways for the rest of the sums...
SUM Number of Ways
0 1
1 3
2 6
3 10
4 15
5 21
6 28
7 36
8 45
9 55
10 66 (not true)
But I thought that it wouldn't continue forever, cos when we get to Sum: 10, we will no longer have our first combination with zeros! that is we don't have 0010 like we had 009.
So we have to subtract 3 ways from the total number of ways: 66-3 = 63
SUM Number of Ways
10 63
Now I didn't knew how to continue for 11, so I just calculated combinations for Sum: 11:
Which gave:
SUM Number of Ways
11 69
Looking at the difference between Ways(Sum:10) and Ways(Sum:9) and Ways(Sum:11) and Ways(Sum:10):
Ways(Sum:10) - Ways(Sum:9) = 63 - 55 = 8
Ways(Sum:11) - Ways(Sum:10) = 69 - 63 = 6
Looks like the increment in number of ways is slowing down.
Is the difference between Ways(Sum:12) and Ways(Sum:11) = 4??
that is, Ways(Sum:12) = 73 [yes it is!]
Right then, we have a pattern
SUM Number of Ways
12 73 [difference of 4 from sum:11]
13 75 [difference of 2 from sum:12]
14 75 [difference of 0 from sum:13]
But now for Sum:15, what do I do?? Does it start to reverse?? I checked 15 and 16 and yes it does...so
SUM Number of Ways
15 73
16 69
17 63
18 55
19 45
20 36
21 28
22 21
23 15
24 10
25 6
26 3
27 1
Square all number of ways and add them all together to get: 55,252 combinations!
It's not an ideal solution by any means, still hoping to find (or ask timetrader LOL ) for the neater/more elegant solution
_________________
The three most significant times in your life are:
1. When you fall in love
2. The birth of your first child
3. When you prepare for your GMAT