BrainDen.com - Brain Teasers
• 0

# How many are there?

## Question

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)

## Recommended Posts

• 0

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 29. Why?

Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit.

Since there are 2n n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers)

there are 29 nine-digit binaries, and thus 29 natural numbers with (strictly) increasing digits.

##### Share on other sites

• 0

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 on other sites

• 0

bonanova,

I see no sense in you disallowing 12 or 123, because each of those numbers have strict increases

in their digits.

##### Share on other sites

• 0

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 on other sites

• 0

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 on other sites

• 0

[disallowing ... a sequence such as this .... that has ... ] numbers like that with repeats in them

You didn't understand?

Seriously? ##### Share on other sites

• 0

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 29. Why?

Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit.

Since there are 2n n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers)

there are 29 nine-digit binaries, and thus 29 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, 29-10.
##### Share on other sites

• 0

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 by Perhaps check it again
##### Share on other sites

• 0

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 29. Why?

Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit.

Since there are 2n n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers)

there are 29 nine-digit binaries, and thus 29 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, 29-10.

You're right. Good catch.

## 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.