Following this question, consider the case where we change the number of digits and formulate the task like this:

Write the statement like "This statement contains $M_0$ 0's, $M_1$ 1, ..., $M_N$ N's", which is true. You must write about all digits, which statement includes: that all $M_i (i = 0, .., N)$ must be written with $0, .., N$ digits only.

What is the smallest $N$ possible here?

Similarly to the given answer for $N=9$:

1 0's, 7 1's, 3 2's, 2 3's, 1 4's, 1 5's, 1 6's, 2 7's, 1 8's, and 1 9's.

I can construct answer for $N=6$:

1 0's, 4 1's, 3 2's, 2 3's, 2 4's, 1 5's, 1 6's.

but the same approach fails for $N=5$. Meanwhile this doesn't prove that $N \le 5$ is not possible to achieve.

  • $\begingroup$ Your approach for $N = 5$ fails because it's known that there's no solution to $N = 5$. $\endgroup$ – Joe Z. Jul 12 '14 at 12:25

I've seen this problem for numbers from $1$ to $N$ before, but not for $0$ to $N$.

If the statements are from $1$ to $N$, the minimum you can have is $4$, as follows:

This statement contains 2 1's, 3 2's, 2 3's, and 1 4.

Now note that in the case from $0$ to $N$, you're guaranteed that there is only ever one $0$, because there is never $0$ of any other number. So, a trivial solution exists for $N = 0$:

This statement contains 1 0.

And for $N = 1$:

This statement contains 1 0 and 2 1's.

And for $N = 2$:

This statement contains 1 0, 3 1's, and 1 2.

However, what these statements all have in common is that they involve writing a number greater than the maximum number being counted, which means that the sentence only describes some of the numbers, not all of them. The smallest statement that fits your new criterion is indeed $N = 3$:

This statement contains 1 0, 2 1's, 3 2's, 2 3's, and no other numbers.

  • $\begingroup$ So you are saying that $N=5$ doesn't have an solution and $N=4$ doesn't, and $N\le2$ doesn't? Could you prove it? $\endgroup$ – klm123 Jul 12 '14 at 12:38
  • $\begingroup$ Actually, you're right. A smaller, trivial solution exists. $\endgroup$ – Joe Z. Jul 12 '14 at 13:19
  • $\begingroup$ Oh. Good catch. I missed this moment. I corrected the question to exclude trivial solutions. I am interested in something different (what you showed before for $N=3$). Sorry. $\endgroup$ – klm123 Jul 12 '14 at 13:26
  • $\begingroup$ That's why this problem is generally formulated from $1$ to $N$ - so you don't have the awkwardness with $0$ allowing overflows. $\endgroup$ – Joe Z. Jul 12 '14 at 13:27
  • 1
    $\begingroup$ @JoeZ. Are you sure you can only have 1 zero in the $0$ to $N$ case? What about something like This statement has 2 0's, 10 1's, 11111111 2's, .... $\endgroup$ – Calvin's Hobbies Jul 12 '14 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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