Barcallica 2 Report post 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) Share this post Link to post Share on other sites

0 bonanova 81 Report post 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. Share this post Link to post Share on other sites

0 bonanova 81 Report post 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. Share this post Link to post Share on other sites

0 Perhaps check it again 22 Report post 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. Share this post Link to post Share on other sites

0 Barcallica 2 Report post 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. Share this post Link to post Share on other sites

0 Perhaps check it again 22 Report post 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." Share this post Link to post Share on other sites

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

0 k-man 26 Report post 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. Share this post Link to post Share on other sites

0 Perhaps check it again 22 Report post 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 Share this post Link to post Share on other sites

0 bonanova 81 Report post 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. Share this post Link to post Share on other sites

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)

## Share this post

## Link to post

## Share on other sites