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?

  • $\begingroup$ "in any order" means (1, 23, 203, ...) would be illegal, correct? $\endgroup$
    – DevOfZot
    Jan 28, 2015 at 1:16
  • $\begingroup$ @DevOfZot Yes, that's correct $\endgroup$ Jan 28, 2015 at 1:18

2 Answers 2


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


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


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.

  • 1
    $\begingroup$ You may be interested in Dickson's Lemma: en.wikipedia.org/wiki/Dickson%27s_lemma $\endgroup$ Jan 28, 2015 at 12:56
  • $\begingroup$ I think you can use the infinite Ramsey theorem to prove your conjecture. $\endgroup$
    – Lopsy
    Jan 28, 2015 at 13:35
  • $\begingroup$ Have we left the realm of PuzzlingSE and entered MathsSE by now? $\endgroup$
    – BmyGuest
    Jan 28, 2015 at 21:33
  • $\begingroup$ @BmyGuest It's a mathematical puzzle. What do you expect? $\endgroup$
    – KSmarts
    Jan 28, 2015 at 22:32
  • $\begingroup$ @BmyGuest You might be right. I think this stretches the boundary of math puzzles as opposed to math problems. But I could see the result being surprising, and perhaps my proof attempt is needlessly technical and in fact there's a more intuitive argument. $\endgroup$
    – xnor
    Jan 29, 2015 at 3:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.