cotpi 50 - Two sequences of natural numbers

[cotpi]

There are two sequences of natural numbers. The first sequence
consists of all natural numbers that do not contain a particular
digit, in ascending order. The second sequence consists of all
the remaining natural numbers in ascending order. Every natural
number occurs exactly once in exactly one of the sequences.

How many terms are there in the first sequence such that each of
those terms is greater than the corresponding term at the same
position in the second sequence?

In other words, if (a_1, a_2, ...) is the first sequence and
(b_1, b_2, ...) is the second sequence how many elements a_i are
there in the first sequence such that a_i > b_i?

--
Originally posted at: http://cotpi.com/p/50/
Correct solutions will be archived at the URL mentioned above.
Solutions to 'Powers of ten': http://cotpi.com/p/49/#responses

Google+: http://plus.google.com/108698297184243273330

[cotpi]

On 05/06/2012 05:31 PM, Gnanasenthil G wrote:

> Does the problem statement mean a situation like this??
> for example first sequence does not contain 3,13,23,30 etc and the second sequence contains these numbers.

If we assume that the "particular digit" mentioned in the problem
statement is 5, then the first sequence is (1, 2, 3, 4, 6, 7, 8, ...)
and the second sequence is (5, 15, 25, 25, 35, 45, 50, ...).

[Ed Murphy]

Infinitely many.

Let f(n) and g(n) be the number of n-digit numbers in the first and
second sequence, respectively.

f(n) = 8 * 9^(n-1), or 9 * 9^(n-1) if the particular digit is zero
g(n) = 9 * 10^(n-1) - f(n)

The running total of g(n) catches up to that of f(n) somewhere in the
seven-digit range (or eight-digit if the particular digit is zero),
and continues to increase more rapidly past that point.

[Dr Nick]

It's a corollary of the counter-intuitive thing that, to any reasonable
approximation, the proportion of numbers that don't contain a 9 is zero.
Isn't it?
--
Online waterways route planner | http://canalplan.eu
Plan trips, see photos, check facilities | http://canalplan.org.uk

[Lone Learner]

On May 7, 12:03 pm, Dr Nick <3-nos...@temporary-address.org.uk> wrote:

I have similar question too. Is there a proof to show that the running
total of g(n) continues to increase or is it an observation of the
graphs?

[James Waldby]

On Wed, 16 May 2012 23:20:49 -0700, Lone Learner wrote:
> On May 7, 12:03 pm, Dr Nick ... wrote:
>> Ed Murphy ... writes:
>> > cotpi wrote:
>> > (someone) wrote:
...

>> > Let f(n) and g(n) be the number of n-digit numbers in the first and
>> > second sequence, respectively.
>>
>> > f(n) = 8 * 9^(n-1), or 9 * 9^(n-1) if the particular digit is zero
>> > g(n) = 9 * 10^(n-1) - f(n)
>>
>> > The running total of g(n) catches up to that of f(n) somewhere in the
>> > seven-digit range (or eight-digit if the particular digit is zero),
>> > and continues to increase more rapidly past that point.
>>
>> It's a corollary of the counter-intuitive thing that, to any reasonable
>> approximation, the proportion of numbers that don't contain a 9 is zero.
>> Isn't it?

...

> I have similar question too. Is there a proof to show that the running
> total of g(n) continues to increase or is it an observation of the
> graphs?

Yes. The "running total of g(n)" is 9 * 10^(n-1) - f(n)
or 9 * 10^(n-1) - 8 * 9^(n-1) [for non-zero digit k]
which is greater than 9 * 9^(n-1) - 8 * 9^(n-1) = 9^(n-1)
which steadily increases as n increases. For the k=0 case,
g(n) = 9 * (10^(n-1) - 9^(n-1)). It should now be obvious that
g(n) steadily increases with n, but if not, write the latter as
(9^n)*((10/9)^(n-1) - 1) which by binomial expansion is not less
than (9^n)*(1 + n/9 - 1) = n*9^(n-1), which steadily increases
with n.

--
jiw