How long can this list of numbers get?

Question

One afternoon, you start writing some whole numbers on a (very large) sheet of paper. First you write a one-digit number, then a two-digit, and so on, with each number one digit longer than the last. Every number is written in base 10.

To make this otherwise dull activity more interesting, you decide never to write a number using all of the digits in any previously written number (in any order). It easy to write numbers at first, but it gets harder and harder as you go.

Will you ever be forced to stop writing, and if so how many numbers might you need to write before this happens?

Answer 1

I think that the list must terminate, but a strategy like this is optimal:

1
22
233
2344
23455
234566
2345677
23456788
234567899
2345678900
23456780000
234567999999
2345679999900
23456799990000
234567999000000
2345679900000000
23456790000000000
234567000000000000
2345688888888888888
23456888888888888899
234568888888888888900
...

Each time, remove a copy of the largest digit present (call it x). If x is 9, add two 0s to the end of the number. Otherwise, remove all 0s and fill the rest of the length with (x+1)s. This results in a list with a length on the order of A(10,1), where A is the Ackermann function. This is because f(x,y), defined as the length of a list of expanding numbers using this strategy where x is the number of digits available and y is the length of the first entry obeys a recursion very similar to the definition of the Ackermann function.

I have no proof that the list can't continue indefinitely, but it might be related to the "hydra game".

Answer 2

I suspect this can be proven by the theory of posets. Here's a sketch/outline of a proof, though it's missing the key proof ingredient.

We can associate each number with a vector $v$ in $\mathbb{N}^{10}$ whose entries $(v_0,v_1,\dots,v_9)$ are non-negative integers that count the number of each digit $0$ through $9$ that appears. We have the condition that no entry $w$ dominates another entry $v$, meaning has every entry at least as large $w_i\geq v_i$.

Let's think of $\mathbb{N}^{10}$ as a partially ordered set (poset) under the domination relation $\preceq$. In fact, it is exactly the poset Cartesian product $\mathbb{N}\times\cdots\times \mathbb{N}$ of $10$ copies of $\mathbb{N}$, the ordered set of natural numbers.

To prove there's no infinite sequence as required, it would prove to show that $\mathbb{N}^{10}$ has no infinite antichain, which is a collection of elements no two of which are comparable. We'll call this property finite-width.

We'll proceed by induction. It's clear that $\mathbb{N}$, being totally ordered, has finite width.

False claim: If $A$ and $B$ are finite-width posets, then so is $A\times B$.

Its falsity is witnessed by the example of $A=\mathbb{N}$ and $B=\mathbb{\bar{N}}$, the natural numbers under the reversed order. There, the set of all $\{(i,i)\}$ is an infinite antichain. So, we'll need some stronger condition to make this carry through.

I think this condition is that the natural number are well-ordered, meaning that they have no infinite downward chains, which are infinite sequences of elements, each smaller than the previous. The natural numbers have this property, but the reversed natural numbers do not. The property is preserved by product

Claim: If $A$ and $B$ are well-ordered posets, then so is $A\times B$.

This is easy to see in that any infinite downward chain in $A\times B$ corresponds to an infinite downward chain in $A$ (and also $B$).

So, $\mathbb{N}^{k}$ is a well-ordered poset for any finite $k$. I believe this suffices to prove the claim we want, but don't yet have a proof.

Conjecture: If $A$ and $B$ are well-ordered with finite width, then so is $A\times B$ has finite width.