8
$\begingroup$

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.

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

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
12
  • $\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, 2014 at 12:38
  • $\begingroup$ Actually, you're right. A smaller, trivial solution exists. $\endgroup$
    – user88
    Jul 12, 2014 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, 2014 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$
    – user88
    Jul 12, 2014 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$ Jul 12, 2014 at 22:09

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.