# Does there exist a general solution of this 'Counting numbers' game?

A few days ago, a friend of mine taught me a number-game. It may be famous, but I haven't known it. I'm going to show it to you.

Imagine that you have a kind of page-a-day calendar, and that you play a number-game every morning. The page on today' page says the following:

"8 11 2013.
How many $0$s are in this paper? The answer is $()$.
How many $1$s are in this paper? The answer is $()$.
How many $2$s are in this paper? The answer is $()$.
How many $3$s are in this paper? The answer is $()$.
How many $4$s are in this paper? The answer is $()$.
How many $5$s are in this paper? The answer is $()$.
How many $6$s are in this paper? The answer is $()$.
How many $7$s are in this paper? The answer is $()$.
How many $8$s are in this paper? The answer is $()$.
How many $9$s are in this paper? The answer is $()$."

This game is pretty simple. Just fill in the blanks. Of course, the answer is not the following.

"8 11 2013.
How many $0$s are in this paper? The answer is $(2)$.
How many $1$s are in this paper? The answer is $(4)$.
How many $2$s are in this paper? The answer is $(2)$.
How many $3$s are in this paper? The answer is $(2)$.
How many $4$s are in this paper? The answer is $(1)$.
How many $5$s are in this paper? The answer is $(1)$.
How many $6$s are in this paper? The answer is $(1)$.
How many $7$s are in this paper? The answer is $(1)$.
How many $8$s are in this paper? The answer is $(2)$.
How many $9$s are in this paper? The answer is $(1)$."

This game is pretty simple, but not very easy. The key point is that you have to count the numbers you write in the blanks as well! Then, I've been struggling to solve the today's game, and at last I got one of the answers.

"8 11 2013.
How many $0$s are in this paper? The answer is $(2)$.
How many $1$s are in this paper? The answer is $(7)$.
How many $2$s are in this paper? The answer is $(6)$.
How many $3$s are in this paper? The answer is $(3)$.
How many $4$s are in this paper? The answer is $(1)$.
How many $5$s are in this paper? The answer is $(1)$.
How many $6$s are in this paper? The answer is $(2)$.
How many $7$s are in this paper? The answer is $(2)$.
How many $8$s are in this paper? The answer is $(2)$.
How many $9$s are in this paper? The answer is $(1)$."

Just try and enjoy it. You'll notice how difficult it is! To be honest, I got this answer just by chance.

Then, here are my questions.

Question1: Does there exist a general solution of this game except by using computer?

Question2: Can we get an answer everyday?

Question3: Can we generalize this game?

My answer for Question3 is the following famous question:

Question: Find all integer-sequences $(x_0, x_1, \cdots, \ x_n)$ such that $x_j$ equals the number of $j$ appearing in the sequence for any $j\ (0 \le j\le n).$

The answer: $$(2, 0, 2, 0), (1, 2, 1, 0), (2, 1, 2, 0, 0), (p, 2, 1, 0, 0, \cdots, 0, 1, 0, 0, 0)$$ $\ (p \ge 3$ and $\:\text{the number of$0$s sandwiched by two$1$s is$p-3$})$

Proof: Suppose that the sequence $(x_1, x_2, \cdots, \ x_n)$ satisfies the condition. Since $x_j$ equals the number of $j$ appearing in the sequence, we get that $x_j$ is a non-negative integer and $x_j\le {n+1}$. Here, if there exists $i$ such that $x_i=n+1$, the number of $\ i\$s is $n+1$. In other words, every index is $i$. Then, we get a contradiction: $x_i=n+1=i\le n$. Hence, we get $0\le x_i\le n$ for any $i\ (0\le i\le n)$.

If $x_0=0$, then $x_0$ itself is $0$, so we get a contradiction. Hence, $x_0\gt0$. Let the number of the positive numbers in $x_1, x_2, \cdots, x_n$ be $m$. Supposing that $x_0=p\ (\ge1)$, we get $x_p\ge 1$. Hence, we get $m\ge 1$.Here, since $S=\sum_{i=1}^nx_i$ means counting the numbers$\ \ge1$ in the sequence, we get $S=m+1$. (this is because $x_0\gt 0$ and because we have $m$ indexes each of which is $1$ and over in $x_1, x_2, \cdots, x_n$.) Since $m$ positive indexes in $S$, we get that the one is $2$ and the other $m-1$ are $1$. Hence, we get that the index which is over $2$ is, even if it exists, only $x_0$, and that if $x_j\gt0$ for a $j\gt2$, we get $j=x_0$. Then, since the positive integers $j$ such that $x\ge1$ must be any of $j=1, 2, x_0$, we get $m\le3$. In the following, we separate three cases by the value of $m$. Note that the numbers of $1$s and $2$s are respectively $m-1$ and $1$, and the rests are all $0$ in $x_1, x_2, \cdots, x_n$. Let's call this notice A.

1. The case $m=1$. If $x_i=2$ for $i\not=2$, according to A, we have two different number $2, i$ in $x_1, x_2, \cdots, x_n$. This contradicts $m=1$. Hence, we get $x_2=2$. This sequence has only one $2$ except for $x_2$. However, according to A, every index of $x_1, x_2, \cdots, x_n$ is $0$ except for $x_2$, so we get $x_0=2$. Hence, we get $(2, 0, 2, 0)$.

2. The case $m=2$. We get $x_1=2$ or $x_2=2$. By the same argument as above, we get $(1, 2, 1, 0)$ and $(2, 1, 2, 0, 0)$ respectively.

3. The case $m=3$. We get $x_p\gt 0$ for a $p\ge 3$. Hence, we get $x_0=p, x_p=1$, so we get $x_1=2, x_2=1$. Since every positive index is determined, we get $$(p, 2, 1, 0, 0, \cdots, 0, 1, 0, 0, 0).$$ Note that the number of $0$s sandwiched by two $1$s is $p-3$.

Now the proof is completed.

-
+1 I'm guessing no to #1, since the thing being counted (number of appearances of digits in base 10) is so artificial. Things get even worse if any of the numbers can be double-digit. –  user7530 Aug 11 '13 at 7:25
@user7530: I think so. I'm afraid that math doesn't have any solution to this. –  mathlove Aug 11 '13 at 8:43
I added the proof of the last question. –  mathlove Aug 11 '13 at 14:30
@mathlove If your game is to have a solution for all dates, then your rules must allow you to write an incorrect answer during any revision of the answers. For example, whenever the answer to the question concerning digit $n$ is $n$, then the act of writing this answer makes the answer incorrect. –  Nick R Aug 12 '13 at 17:36
@mathlove Your generalization doesn't incorporate your game, but it has a nice result. To include the calendar game, you just have add that for some arbitrary given $p_j$ sequence, $x_j - p_j$ is the number of times $j$ appears in the sequence $x$. Of course, we are using a specific length sequence $(x_0,\ldots,x_9)$. (Well, except for double-digits :P) –  Evan Aug 29 '13 at 16:55

This is not an answer to all of your above questions. I attempt to formalize the problem thereby getting some insight into the structure of the solution. To that purpose let $D:=\{1,\ldots,9\}$ and $i\in D$. Consider the system of equations

$x_i = c_i + \sum_{j\in D} \delta_{x_j,i}$

with $\delta_{i,j}$ being the Kronecker delta. Your question 2 now translates to

Q2: Does this system have solutions $x_i\in D$ for given $c_i\in D$?

I understand @Nick R s comment in such a way that one can disprove existence for all inital values $c$ by a diagonal argument. However, for some choices of $c_i$ a solution might exist and your question 1 is to find such a solution without searching through all possibilities. Lets try to tackle that.

By summing we get the invariant

$I := \sum_{i\in D} x_i = 10 + \sum_{i\in D}c_i$

and inequalities like e.g.

$i x_i + (1-\delta_{x_i,i}) x_i \leq I.$

This can be used to reduce the search space considerably. In your example we have $c_0 := 2, c_1 := 4, c_2 := 2, c_3 := 2, c_4 = 1, c_5 = 1, c_6 = 1, c_7 = 1, c_8 = 2$ and $c_9 = 1.$ That yields $I = 27$. Since all of the $c_i$ are greater than zero we find $x_0 = 2$. The inequalities lead to strong constraints for large $i$. Let us consider $i=9$. We get

$9 x_9 + (1-\delta_{x_9,9}) x_9 \leq 27.$

This excludes $x_9 = 9$ and therefore $\delta_{x_9,9}=0$. Together with $x_i\geq c_i$ and since $x_i\in D$ we get

$1\leq x_9\leq 2.$

Admittedly I have not yet tried to tackle the whole problem, but it might be feasible to be solved with this strategy without a computer. Especially since the inequalities can probably with a little work be optimized.

Your last question about reasonable generalisations of the game can now be partially answered with help of the above formalism. One could e.g. use a different base $D$ or adjust the above equations for $x_i$ to have more than one digit.

-
Many thanks. Nice idea! –  mathlove Sep 5 '13 at 15:42