Jump to content
BrainDen.com - Brain Teasers
  • 0

Digits on the rise


bonanova
 Share

Question

7 answers to this question

Recommended Posts

  • 0

Please clarify if you mean

  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
Link to comment
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)
*The highest integer with [n] digits must start with [10-n] digit (highest 2-digit number must start with 8 and highest 9-digit number must start with 1)

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
Link to comment
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

Link to comment
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...