A 10-digit number whose $n$th digit gives the number of $(n-1)$s in it

Question

There is a ten-digit number $X$ such that its first (left-most) digit is equal to the number of $0$s in $X$, the second digit gives the number of $1$s in $X$, and so on. The last (right-most) digit gives the number of $9$s in $X$. Find $X$.

Aren't there a lot of possibilities for a solution?

Answer 1

No. There is exactly one.

+1 to Amulya for an interesting question.

+1 to ipoteka for doing it the hard way :)

/*
      There is a ten digit number X such that 
          its first (left-most) digit is equal to the number of 0s in X, 
          the second digit gives the number of 1s in X, 
          and so on. 
          The last (right-most) digit gives the number of 9s in X. Find X. 
          isn't there a lot of probabilities to the solution?
*/

#include <iostream>

int main
(
    void
)
{
    std::cout << "Working" << std::endl;
    const int N = 10;
    int digits[N] = { 0 };

    for (int a = 0; a < N; a++)    {   digits[a]++;    std::cout << "progress " << a << std::endl;
    for (int b = 0; b < N; b++)    {   digits[b]++;
    for (int c = 0; c < N; c++)    {   digits[c]++;
    for (int d = 0; d < N; d++)    {   digits[d]++;
    for (int e = 0; e < N; e++)    {   digits[e]++;
    for (int f = 0; f < N; f++)    {   digits[f]++;
    for (int g = 0; g < N; g++)    {   digits[g]++;
    for (int h = 0; h < N; h++)    {   digits[h]++;
    for (int i = 0; i < N; i++)    {   digits[i]++;
    for (int j = 0; j < N; j++)    {   digits[j]++;



    if
    (
        (a == digits[0]) &&
        (b == digits[1]) &&
        (c == digits[2]) &&
        (d == digits[3]) &&
        (e == digits[4]) &&
        (f == digits[5]) &&
        (g == digits[6]) &&
        (h == digits[7]) &&
        (i == digits[8]) &&
        (j == digits[9])
    )
    std::cout << a << b << c << d << e << f << g << h << i << j << std::endl;

    digits[j]--;    }
    digits[i]--;    }
    digits[h]--;    }
    digits[g]--;    }
    digits[f]--;    }
    digits[e]--;    }
    digits[d]--;    }
    digits[c]--;    }
    digits[b]--;    }
    digits[a]--;    }

    std::cout << "Complete" << std::endl;

    return 0;
}

Output:

Working
progress 0
progress 1
progress 2
progress 3
progress 4
progress 5
progress 6
**6210001000**
progress 7
progress 8
progress 9
Complete
Press any key to continue . . .

Answer 2

It looks like you can solve it recursively.

1. The first number can't be 0, because then the number of zeros isn't 0
2. Can it be 9? => 9,000, 000,00? NO
3. Can it be 8? => 8,?00,000,010 NO- but there is contradiction
4. Can it be 7? => 7,?00,000,100 NO
5. Can it be 6? => 6,210,001,000 Yes
6. Can it be 5? => 5,???,???,???

And you play this way a little bit. I guess the solution is the only one

Answer 3

You can use constraint programming.

There is the obvious constraint, namely the definition: every element must be the number of occurrences of that number. That already gives a simple pruning rule: the sum of the items must be n (why? well there are n items, and whatever number they are they will be counted somewhere).

But we can go one step further. A number x in place i means there will be x i's (not surprising so far), this means that actually the sum of array[i] * i (over all i) will also be n, which is (mostly) a stronger pruning rule (except for zero).

Most of them (for 7 and higher) end up looking like this:

n-4 2 1 .... 1 ...

With the second 1 located at the index n-4. This pattern doesn't work for some small n's, namely 6 and below, most of which have no valid pattern. 4 and 5 are special cases:

4: 1 2 1 0
5: 2 1 2 0 0

Answer 4

We can solve this mathematically for the general case, which includes n = 10.

Let's call our solution s, and p the subset of s, where s[i] > 0, that is, the set of represented numbers (any zero is a number or index that is not represented).

We can say that n = sum of all frequencies = sum p

Now let's call p' the subset of p without s[0], which are frequencies only of numbers greater than zero.

Clearly sum p' = sum p - s[0] = length p, which is simply the count of how many numbers in s are greater than zero.

Remember that length p = length p' + 1. Now if length p > 4, we know that sum p' > 4 and we are left with an m length partition (p') that must sum to m+1, where m > 3. The only way this can be done is with (m-1) 1's and one 2, e.g., [1,1,1,2] in the case of m=4 (by definition there are no zeros in p'). Such a partition could not make sense as a solution to our problem, and so we see that p, or the subset of numbers greater than zero in our solution, must have less than 5 elements.

Now we can solve for specific cases:

Every solution must have s[0] > 0 since a zero in the zero column would invalidate the solution.

length p = 1 would only be possible if s[0] could be both zero and greater than zero at the same time.

length p = 2 implies p' = [2], and so there are two zeros and two 2's, s=[2,0,2,0]

length p = 3 implies p' = [1,2]. Since we know there is only one more s[i], which is s[0] > 0, the 2 in p' must either refer to itself, in which case we have s=[2,1,2,0,0]; or to two 1's and therefore s=[1,2,1,0]

length p = 4, p' = [2,1,1]. In this case the 2 could only be referring to the two 1's and we must assume s[0] > 2, which also means sum p >= (3+2+1+1 = 7). This is the final / general case: s[1]=2, s[2]=1. The last 1 refers to s[0] and so its index equals s[0]. Remembering that sum p - s[0] = length p, we get, s[0] = n - 4, and the solution, for length p = 4, n > 6: s=[n - 4,2,1...1,0,0,0]