11
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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 . . .
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It's not .... the last digit should at least be one for the nine in the start.... $\endgroup$ – JuniorCompressor Apr 18 '15 at 0:35
  • 2
    $\begingroup$ To Keep for the generations to come to see the sorts of mistakes that I make, or the call of sweet oblivion.... Sigh $\endgroup$ – EvilTeach Apr 18 '15 at 0:38
  • $\begingroup$ I misread the question. Thank you JC. Here is a program to atone for my sins. $\endgroup$ – EvilTeach Apr 18 '15 at 1:18
  • 1
    $\begingroup$ It was a pleasant way. For a moment i felt what a lisp machine feels :3 $\endgroup$ – ipoteka Apr 18 '15 at 1:27
  • $\begingroup$ Euler 5 is similar in some respects $\endgroup$ – EvilTeach Apr 18 '15 at 1:31
4
$\begingroup$

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]

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I arrived at the same conclusion, but I don't really follow your line of reasoning for the n>6 case $\endgroup$ – harold Apr 18 '15 at 1:31
  • $\begingroup$ @harold which part are you having trouble following? $\endgroup$ – גלעד ברקן Apr 18 '15 at 6:20
  • $\begingroup$ The end, that sum p - length p deal, why does that have n-4 as solution? $\endgroup$ – harold Apr 18 '15 at 8:05
  • $\begingroup$ @harold Simple arithmetic: sum p was stated equal to n early on; length p is defined as 4 for the last case I examined. So s[0] = n - 4. length p must be less than 5 was explained earlier. Are you having trouble understanding sum p' = sum p - s[0] = length p ? $\endgroup$ – גלעד ברקן Apr 18 '15 at 12:11
  • $\begingroup$ Oh nevermind, I just got lost in all those definitions $\endgroup$ – harold Apr 18 '15 at 12:16
2
$\begingroup$

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
| cite | improve this answer | |
$\endgroup$

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.