Alok Goyal's Puzzles Page

This was a difficult puzzle, and I got only one response and a correct one from Ganesh Ramani, my friend from IITD Comp Science and now in Tokyo – well done!

To arrive at the solution, lets begin with Variation 1:

An easy way to think about the solution for this is to assume that you have 9 (sum) + 3 (number of digits) = 12 balls that you have to divide into 3 non-zero partitions, which if you try to calculate will be  (12-1) C (3-1) = 11 C 2 = 55. From each of these partitions, subtract 1 to arrive at the number. For example, one way to divide 12 into 3 partitions is 10, 1, 1 ==> the number is 900. Another way would be 5,3,4 ==> the number will be 423. Each of these numbers will have digits that add up to 9. 11 C 2 = 55, which is the answer for this variation.

Lets use this principle to arrive at the answer for Variation 2:

We can use the above principle to arrive at all the possible ways of 3 digits totaling up to 18 by doing (18+3-1) C (3-1) = 20 C 2 = 190.

However, the problem is that some of the digits could be 10 or above as well, which is not valid. We, therefore, need to subtract from 190 all the numbers where any of the digits is turning out to be 10 or more. Let’s assume that the first digit is 10 or more, that will imply that the sum of the last two digits is 8 or less, which is the same as all three digits number with a total of 8, which is equal to (8+3-1) C (3-1) = 10 C 2 = 45. Since any of the three digits can be 10 or above, we need to multiply 45 by 3 to arrive at all the possibilities where one of the digits is more than 10, i.e. 3 x 45 = 135.

therefore the number of solutions where the digits add up to 18 = 190 – 135 = 55.

Notice that there is a trivial way to arrive at this answer by doing the following:

– There is only one number where the first digit is 0, and the remaining two add up to 18, which is 099

– There are two numbers where the first digit is 1, and the remaining add up to 17, which are 189 and 198

– Similarly if the first digit is 2, then there are 3 possibilities…all the way up to the first digit being 9, when there are 10 solutions.

therefore the total is 1+2+3+….+10 = 55

This method, however, is brute force and does not scale when the numbers get larger.

Original version can be figured out in the same way as Variation 2:

Since there are 6 digits here, the answer will be 23 C 5 – (6 x (13 C 5)) = 33649 – 6*1287 = 25927

Hope you enjoyed the puzzle!