11
$\begingroup$

https://puzzling.stackexchange.com/questions/23554/self-referential-puzzles made me wonder. How many solutions are there to the below box when multiple digits are allowed? I don't know the answer myself, so a good proof of your answer is appreciated. We're counting characters, so 11 is considered as two 1's and not as one 11.

\begin{array}{|cc|} \hline \text{The number of 0's in this box is} & \text{_______} \\ \text{The number of 1's in this box is} & \text{_______} \\ \text{The number of 2's in this box is} & \text{_______} \\ \text{The number of 3's in this box is} & \text{_______} \\ \text{The number of 4's in this box is} & \text{_______} \\ \text{The number of 5's in this box is} & \text{_______} \\ \text{The number of 6's in this box is} & \text{_______} \\ \text{The number of 7's in this box is} & \text{_______} \\ \text{The number of 8's in this box is} & \text{_______} \\ \text{The number of 9's in this box is} & \text{_______} \\ \hline \end{array}

Improve this question
$\endgroup$
7
  • $\begingroup$ One possible solution is 11121111111.However,I'm not sure how many solution exists. $\endgroup$
    – Roby5
    Oct 26, 2015 at 15:24
  • 3
    $\begingroup$ It's not super-easy to parse answers of the form "11121111111". For clarity, the solution proposed by @Roby5 is "1_11_2_1_1_1_1_1_1_1". $\endgroup$
    – Ian MacDonald
    Oct 26, 2015 at 16:07
  • $\begingroup$ My idea of crux of the proof would be to restrict the number of 1s to some number/s and then get all frequency of the remaining numbers.However,I can't seem to find a proof on the restriction part. $\endgroup$
    – Roby5
    Oct 26, 2015 at 16:08
  • $\begingroup$ This sentence employs two a’s, two c’s, two d’s, twenty-eight e’s, five f’s, three g’s, eight h’s, eleven i’s, three l’s, two m’s, thirteen n’s, nine o’s, two p’s, five r’s, twenty-five s’s, twenty-three t’s, six v’s, ten w’s, two x’s, five y’s, and one z. $\endgroup$
    – Darrel Hoffman
    Oct 26, 2015 at 19:28
  • 2
    $\begingroup$ I would, but I stole it from Wikipedia. I was going to preface the comment with a note to the fact, but then I'd have to recalculate all the letter counts, etc. $\endgroup$
    – Darrel Hoffman
    Oct 26, 2015 at 19:37

2 Answers 2

Reset to default
12
$\begingroup$

(assuming numbers with leading zeros, ex "05" are forbidden)

Part 1. Establishing an upper boundary for digit size

Suppose there exists a solution where the largest blank is filled in with three digits.
Then the box must contain at least 108 digits, so one blank must contain at least 9 digits. But the largest blank contains only three digits, which is a contradiction.
So there can't be a solution whose largest blank is three digits.

Suppose there exists a solution where the largest blank is filled in with four digits.
Then the box must contain at least 1008 digits, so one blank must contain at least 99 digits. But the largest blank contains only four digits, which is a contradiction.
So there can't be a solution whose largest blank is four digits.

...

This pattern of contradiction continues upwards forever. So, if a solution exists, its largest blank must have no more than two digits.

Part 2. Establishing an upper boundary for number of two-digit slots

Suppose there exists a solution where exactly two blanks are filled with two digits.
The total number of digits in the entire box is 10 + 8*1 + 2*2 = 22.
The sum of the numbers in each blank must exactly equal the total number of digits in the entire box.
But the minimum theoretical sum of all numbers in each blank is 1*8 + 2*10 = 28
So there can't be a solution where exactly two blanks are filled with two digts.

Suppose there exists a solution where exactly three blanks are filled with two digits.
The total number of digits in the entire box is 10 + 7*1 + 3*2 = 23.
The sum of the numbers in each blank must exactly equal the total number of digits in the entire box.
But the minimum theoretical sum of all numbers in each blank is 1*7 + 3*10 = 37.
So there can't be a solution where exactly three blanks are filled with two digts.

...

This pattern of contradictions continues upwards forever. So, if a solution exists, it can have no more than one blank slot with two digits.

In the previous question, the solution that has zero two-digit slots was already found, so the remainder of this post will search for a solution containing exactly one blank slot with two digits.

Part 3. Determining which slot has two digits

Suppose there exists a solution where exactly one blank is filled in with two digits.
the total number of digits in the entire box = 10 + (9*1) + (1*2) = 21.
The sum of the numbers in each blank must exactly equal the total number of digits in the entire box.

Due to the existing labels, the number in each blank must be at least 1.
No single-digit blank may contain a digit larger than 3, because then the sum of the numbers in each blank would exceed 21.
The two-digit blank may not exceed 12, because then the sum of the numbers in each blank would exceed 21.

Because none of them appear in any blanks, The blanks in slots 4, 5, 6, 7, 8, and 9 are all "1".
The digit in blank slot 1 must be at least 7.
If blank slot 1 is not the two-digit slot, the minimum theoretical sum of numbers in each blank is 7+10+(1*8) = 25. But this is larger than 21, so blank slot 1 must contain two digits.

Part 4. Finding the value of the two digit slot

Blank slot 1 can't contain "12", because once you account for the "1" in "12" and the "1" in the label, you need to fit ten "1"s in nine remaining slots.
Blank slot 1 can't contain "10", because blank slot 0 will be at least 2, and the slot corresponding to 0's number will be at least 2, and you'll need to fit eight "1"s in the seven remaining slots.

So blank slot 1 must contain "11".

Part 5. Finding the remaining values

Accounting for the "11" in the two-digit slot, and the "1" in the label, eight slots must contain "1". Exactly one blank slot contains a single digit other than 1.
The blank slot not containing a 1 must be equal to 21 - (11 + 8*1) = 2.
That will be the second "2" to appear in the box, so it must go in slot 2.

So the only multi-digit solution is [1, 11, 2, 1, 1, 1, 1, 1, 1, 1].

Appendix. Brute-forcing all one digit solutions

The digits in the one-digit solution add up to 20, and no slot contains a 0. Using this information, you can iterate through all possible configurations and find the self-referential ones. Sample Python implementation:

from collections import Counter
import functools

def iter_ways(x, nums):
    if x == 0:
        return
    if nums == 1:
        if 1 <= x<= 9:
            yield [x]
        return
    for i in range(1,10):
        if i <= x:
            for rest in iter_ways(x-i, nums-1):
                yield [i] + rest

def valid(seq):
    c = Counter()
    for i in range(10):
        c[i] = seq[i]
    digit_str = "0123456789" + "".join(map(str, seq))
    digits = map(int, digit_str)
    return c == Counter(digits)

for seq in iter_ways(20,10):
    if valid(seq):
        print seq

Result:

[1, 7, 3, 2, 1, 1, 1, 2, 1, 1]

So the only one-digit solution is [1, 7, 3, 2, 1, 1, 1, 2, 1, 1].

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is not the only solution. The question asks for the number of possible solutions when multiple digits are allowed, not required. $\endgroup$
    – Ian MacDonald
    Oct 26, 2015 at 17:27
  • $\begingroup$ Yeah, I kind of handwaved away the one-digit solution at the end of part 2 by saying that [1, 7, 3, 2, 1, 1, 1, 2, 1, 1] was already found in the previous question. I am working to exhaustively prove that it's the only one-digit solution, but it's quite... Exhausting ;-) Still working on it. $\endgroup$
    – Kevin
    Oct 26, 2015 at 17:34
  • $\begingroup$ I'll add in my one-digit solution brute force finder, so the question is technically complete. I would still like to find a more elegant proof besides "I tried all combinations and only this one worked", even though it's still technically a proof. $\endgroup$
    – Kevin
    Oct 26, 2015 at 18:01
1
$\begingroup$

Answering the original problem:

An alternative lateral thinking answer:

one
one
one
one
one
one
one
one
one
one

From what it seems, this doesn't break the rules.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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