Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What would be the most efficient way of solving the following problem? -

A toy set contains blocks showing the numbers from 1 to 9. There are plenty of blocks showing each number and blocks showing the same number are indistinguishable. We want to examine the number of different ways of arranging the blocks in a sequence so that the displayed numbers add up to a fixed sum. For example, suppose the sum is 4. There are 8 different arrangements:

1 1 1 1

1 1 2

1 2 1

1 3

2 1 1

2 2

3 1


The rows are arranged in dictionary order (that is, as they would appear if they were listed in dictionary). In each of the cases below, you are given the desired sum S and a number K. You have to write down the Kth line when all arrangements that add up to S are written down as described above. For instance, if S is 4 and K is 5, the answer is 2 1 1. Remember that S may be large, but the numbers on the blocks are only from 1 to 9.

(a) S = 9, K = 156 (b) S = 11, K = 881 (c) S = 14, K = 4583


Source - Zonal Informatics Olympiad 2012 Question Paper

share|cite|improve this question
I've tried to construct the answer to the bigger problem through answers to smaller problems, but that didn't quite work out due to different dictionary arrangements. And brute-force doesn't appear to be a pragmatic approach... – 7Aces Oct 29 '12 at 23:19
up vote 1 down vote accepted

Hint: the first lines all start with 1. They are 1 followed by all the ways of writing S-1, in dictionary order. Then you get the ones that start with 2, which are 2 followed by writing S-2. If you can figure out how many total lines there are to write $n$, you can figure out the first number and recurse.

share|cite|improve this answer
Thanks! I re-applied my approach "to construct the answer to the bigger problem through answers to smaller problems" with some edits & it yielded the correct answer... Cheers!! – 7Aces Oct 29 '12 at 23:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.