Barcallica Posted August 22, 2014 Report Share Posted August 22, 2014 How many natural numbers are there, whose digits increase left to right? (this is from a book, so some of you might already know this one) Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted August 22, 2014 Report Share Posted August 22, 2014 Let's disallow leading zeros - e.g. disallow 0123456789, permitting only 9 digits. Then we start with 123456789 (no digits missing) - 1 Then go to numbers like 12_456789 (one digit missing) - 9 Proceeding to 12_456_89 (two digits missing) and so forth. The answer immediately becomes 2^{9}. Why? Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit. Since there are 2^{n} n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers) there are 2^{9} nine-digit binaries, and thus 2^{9} natural numbers with (strictly) increasing digits. Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted August 22, 2014 Report Share Posted August 22, 2014 Since the natural numbers are countable, any subset of them can be no more than countable. Here is a countably infinite subset of those whose digits increase left to right: 1, 12, 123, 1234, ... ah, we have to stop at 123456789. Assuming strict increase and disallowing 1, 11, 12, 112, 122, 123, and numbers like that with repeats in them. OK so it's finite, and they are of the form 123456789 with various digits removed. I'll think about it. Quote Link to comment Share on other sites More sharing options...

0 Perhaps check it again Posted August 22, 2014 Report Share Posted August 22, 2014 bonanova, I see no sense in you disallowing 12 or 123, because each of those numbers have strict increases in their digits. Quote Link to comment Share on other sites More sharing options...

0 Barcallica Posted August 22, 2014 Author Report Share Posted August 22, 2014 bonanova, I see no sense in you disallowing 12 or 123, because each of those numbers have strict increases in their digits. He didn't disallow 12 or 24, he correctly disallowed 112, 224 etc. Without strcict increase, the asnwer would be infinite. Quote Link to comment Share on other sites More sharing options...

0 Perhaps check it again Posted August 22, 2014 Report Share Posted August 22, 2014 Barcallica. the quoted pair of numbers in question are 12 and 123, not 12 and 24 as you stated. And here is bonanova's pertinent quote so you can see to which am referring: "Assuming strict increase and disallowing 1, 11, 12, 112, 122, 123, and numbers like that with repeats in them." Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted August 22, 2014 Report Share Posted August 22, 2014 [disallowing ... a sequence such as this .... that has ... ] numbers like that with repeats in them You didn't understand? Seriously? Quote Link to comment Share on other sites More sharing options...

0 k-man Posted August 22, 2014 Report Share Posted August 22, 2014 Let's disallow leading zeros - e.g. disallow 0123456789, permitting only 9 digits. Then we start with 123456789 (no digits missing) - 1 Then go to numbers like 12_456789 (one digit missing) - 9 Proceeding to 12_456_89 (two digits missing) and so forth. The answer immediately becomes 2^{9}. Why? Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit. Since there are 2^{n} n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers) there are 2^{9} nine-digit binaries, and thus 2^{9} natural numbers with (strictly) increasing digits. That's a cool solution, but a small correction is required... Zero is not a natural number, so if single digit numbers are permitted then the answer is 2^{9}-1. Otherwise, 2^{9}-10. Quote Link to comment Share on other sites More sharing options...

0 Perhaps check it again Posted August 22, 2014 Report Share Posted August 22, 2014 (edited) bonanova, you communicated wrong. You included 12 and 123. Those are strictly numbers and not parts of sequences of numbers. If you wanted numbers that began with those digits, then you need to put ellipses after those, as in: "Assuming strict increase and disallowing 1..., 11..., 12..., 112..., 122..., 123..., and numbers like that with repeats in them." Next time you can type out the word "sequence" or put in the ellipses so you don't pass on the wrong information. And no single digit numbers should be included, because they do not consist of numbers where the digits are increasing from left to right. Edited August 22, 2014 by Perhaps check it again Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted August 22, 2014 Report Share Posted August 22, 2014 Let's disallow leading zeros - e.g. disallow 0123456789, permitting only 9 digits. Then we start with 123456789 (no digits missing) - 1 Then go to numbers like 12_456789 (one digit missing) - 9 Proceeding to 12_456_89 (two digits missing) and so forth. The answer immediately becomes 2^{9}. Why? Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit. Since there are 2^{n} n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers) there are 2^{9} nine-digit binaries, and thus 2^{9} natural numbers with (strictly) increasing digits. That's a cool solution, but a small correction is required... Zero is not a natural number, so if single digit numbers are permitted then the answer is 2^{9}-1. Otherwise, 2^{9}-10. You're right. Good catch. Quote Link to comment Share on other sites More sharing options...

## Question

## Barcallica

How many natural numbers are there, whose digits increase left to right? (this is from a book, so some of you might already know this one)

## Link to comment

## Share on other sites

## 9 answers to this question

## Recommended Posts

## Join the conversation

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