Solution to Puzzle #86: Add The Digits and Count

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!

This entry was posted in Solution and tagged , , , . Bookmark the permalink.

One Response to Solution to Puzzle #86: Add The Digits and Count

  1. Girish Tutakne says:

    I must confess that I tried and couldn’t solve the problem and am now struggling to understand the solution posted above as well. 😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s