BrainDen.com - Brain Teasers
• 0

Digits on the rise

Question

What do 15 489 1256 and 24578 have in common?

They are positive integers whose digits are strictly increasing left to right.

How many of them are there?

Recommended Posts

• 0

1. how many positive increasing-digit integers in {the set of all possible digit combinations in the stated problem} or
2. how many positive increasing-digit integers in {the set of all positive integers}

(I have a feeling it's the latter option...)

Edited by Dariusray
Share on other sites

• 0

Correct. The latter: positive integers whose digits are strictly increasing left to right.

Share on other sites

• 0

First, my thinking about some restrictions for the strictly-increasing-digit integers:

*No numbers may have a zero digit (beginning zeroes disappear and any other position of zero ruins the strictly-increasing pattern)
*No single-digit integers (not technically a digit increase)

Now, a brute-force count (2-digit number starting with 8, plus those starting with 7, etc.) for 2-digit and 3-digit permutations revealed a pattern that a number with [n] digits will need [10-n] addends to result in the total count of permutations...

Once I began the first few addends in my brute-force count for 4-digit permutations, I saw that aligning the addends revealed a vertical pattern that increased my new addends by the counts I had for my previous [n]-digit permutations. (This pattern is much easier for me to visualize than to explain)...

Once I saw the two patterns, I found it much easier to compute with far less brute force (I wish I could make a grid here for alignment):

2-digit integers==>(1+2+3+4+5+6+7+8+9) permutations==> 45 valid integers
3-digit integers==>(1+3+6+10+15+21+28) permutations==>84 valid integers [saw horiz. pattern here; # of addends decreased to 7]
4-digit integers==>(1+4+9+16+25+36) permutations==>91 valid integers [saw vert. pattern here; # of addends decreased to 6 and values increased by 3, then 6, then 10, etc. from counts directly above]
5-digit integers==>(1+5+13+25+41) permutations==>85 valid permutations [now 5 addends & increases of 1, 4, 9, etc. from counts directly above]
6-digit integers==>(1+6+18+38) permutation==>63 valid permutations [continuing horiz. & vert. patterns from here]
7-digit integers==>(1+7+24) permutations==>32 valid permutations
8-digit integers==>(1+8) permutations==>9 valid permutations
9-digit integers==>(1) valid permutation

TOTAL strictly-increasing-digit integers possible==>(45+84+91+85+63+32+9+1)==>410

Provided my patterned computations are accurate, I believe there are 410 valid integers
Share on other sites

• 0

First group it by number of digits (so group 1 will be 1 digit, group 2 will be 2 digits, etc). Then each group will be the functional equivalent of asking, "what are the possible combinatorics for n numbers?" where n is the group number. The reason for this is that any combination of (non-repeating) digits can be ordered from lowest to greatest, and the combination function (nCr) basically takes this into account (as opposed to a permutation, in which the order of items creates unique possibilities). So the final solution will be

SUM (from n=1 to n=9) of 9Cn

=511

Share on other sites

• 0
There's an even simpler observation that immediately gives the correct answer.
Share on other sites

• 0

There's an even simpler observation that immediately gives the correct answer.

I assumed there is,

2

9-1
, but I'm not sure right now why that is.
Share on other sites

• 0

There's an even simpler observation that immediately gives the correct answer.

I assumed there is,

2

9-1
, but I'm not sure right now why that is.

The power set (the set of all subsets) of a set of n objects has size 2n. For 9 digits, n=9. Then subtract off the empty set.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.