Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are ten questions on a piece of paper. Your task is to fill in each blank with a positive integer less than 10 such that there is no contradiction. You can reuse any digit.

The question is as follows:

  • Digit 0 appears __ times on this paper.
  • Digit 1 appears __ times on this paper.
  • Digit 2 appears __ times on this paper.
  • Digit 3 appears __ times on this paper.
  • Digit 4 appears __ times on this paper.
  • Digit 5 appears __ times on this paper.
  • Digit 6 appears __ times on this paper.
  • Digit 7 appears __ times on this paper.
  • Digit 8 appears __ times on this paper.
  • Digit 9 appears __ times on this paper.

How to solve it?

Edit 1:

I am not sure this question can be done without computer.

share|improve this question

3 Answers 3

up vote 15 down vote accepted

The question was asked by xport in the comments to Mike's solution as to whether this solution is unique.

There are no doubt many ways to case bash an answer to this, and here is one, proving that Mike's solution is indeed unique.

Let $x_i$ be the number of times the digit $ i $ appears on the paper, then we must have

$$ \sum_{i=0}^9 x_i = 20 \quad \text{and} \quad \sum_{i=0}^9 ix_i = 45+20=65,$$

since there are $20$ digits on the completed paper and the first column sums to $45.$

All the digits appear at least once therefore $x_i \ge 1 $ for all $ i $ and $x_0=1.$ Thus from the above equations we obtain

$$\sum_{i=1}^9 x_i = 19 \quad (1) \quad \text{and} \quad \sum_{i=2}^9 (i-1)x_i = 46. \quad (2)$$

Since $\sum_{i=1}^8 i = 36$ it follows from $(2)$ that $(i-1)x_i \le 46 - (36-(i-1)),$ and so $$ x_i \le \left \lfloor \frac{i+9}{i-1} \right \rfloor \quad \text{for} \quad i \ge 2.$$

Hence

$$ x_6 \le 3, \, x_7 \le 2, \, x_8 \le 2 \quad \text{and} \quad x_9 \le 2. \quad (3)$$

Now suppose $ x_i > 1 $ for some $ i > 2 $ then, since $i$ occurs in at least three places, we must have $x_j=i$ for some $j \ne i.$

And further suppose $j \ge 2,$ then from $(2)$ we obtain

$$(i-1)x_i + (j-1)i + (36-(i-1)-(j-1)) \le 46,$$

which gives

$$ x_i \le \frac{2i+8}{i-1} - j.$$

Hence when $j \ge 2$ we must have

$$x_6 \le 2 \quad \text{and} \quad x_7=x_8=x_9=1. \quad (4)$$

We now do some case bashing.

From $(3)$ we know $x_9 \le 2,$ so suppose $x_9=2$ then $(4)$ implies $x_1=9,$ which again by $(4)$ implies $x_7=x_8=1,$ since if $x_1=9,$ then $x_1$ cannot equal $7$ or $8.$

Putting $x_1=9, x_7=1, x_8=1$ and $x_9=2$ in $(1)$ and $(2)$ we obtain

$$x_2+x_3+ \cdots + x_6=6$$

and

$$x_2 + 2x_3 + \cdots + 5x_6 = 17.$$

The former clearly only has solution $\lbrace 1,1,1,1,2 \rbrace, $ which satisfies the latter equation only when $x_3=2$ and the other $x_i$ are $1.$ But $3$ does not appear twice in this "solution." Hence we have a contradiction and so $$x_9=1.$$

Similary, suppose $x_8=2,$ then $(4)$ implies $x_1=8,$ which again by $(4)$ implies $x_7=x_9=1,$ since if $x_1=8,$ then $x_1$ cannot equal $7$ or $9.$

Putting $x_1=8, x_7=1, x_9=1$ and $x_8=2$ in $(1)$ and $(2)$ we obtain

$$x_2+x_3+ \cdots + x_6=7$$

and

$$x_2 + 2x_3 + \cdots + 5x_6 = 18.$$

The former equation only has solutions $\lbrace 1,1,1,1,3 \rbrace $ (which does not satisfy the latter equation) and $\lbrace 1,1,1,2,2 \rbrace,$ which only satisifes the latter equation when $x_2=x_3=2$ and the other $x_i$ are $1.$ But again $3$ does not appear twice in this "solution." Hence we have a contradiction and so $$x_8=1.$$

Similary, suppose $x_7=2,$ then $(4)$ implies $x_1=7,$ which again by $(4)$ implies $x_8=x_9=1,$ since if $x_1=7,$ then $x_1$ cannot equal $8$ or $9.$

Putting $x_1=7, x_8=1, x_9=1$ and $x_7=2$ in $(1)$ and $(2)$ we obtain

$$x_2+x_3+ \cdots + x_6=8$$

and

$$x_2 + 2x_3 + \cdots + 5x_6 = 19.$$

The former equation only has solutions $\lbrace 1,1,1,1,4 \rbrace $ (which does not satisfy the latter equation) and $\lbrace 1,1,2,2,2 \rbrace$ (which also does not satisfy the latter equation) and $\lbrace 1,1,1,2,3 \rbrace, $ which only satisifes the latter equation when $x_2=3, x_3=2,x_4=1,x_5=1$ and $x_6=1,$ and this is the solution given in Mike's answer.

Hence we have a unique solution when $x_7=2,$ otherwise we must have $x_7=x_8=x_9=1.$

To complete the proof we need only show that when $x_7=1$ we must have $x_6=1.$ That would give us at least six $1's$ on the paper, implying that one of the numbers $\lbrace 6,7,8,9 \rbrace$ must be repeated, which is a contradiction since we have $x_6=x_7=x_8=x_9=1.$

So suppose $x_7=1$ and $x_6=3$ (the maximum possible from $(3)$) then $(4)$ implies $x_1=6.$ And since $x_8=x_9=1,$ from $(1)$ and $(2)$ we obtain $$x_2+ x_3 + x_4 + x_5=7$$

and

$$x_2 + 2x_3 + 3x_4 + 4x_5 = 10.$$

These have no solutions since the latter equation implies $x_2=x_3=x_4=x_5=1,$ which does not satisfy the former equation.

So suppose $x_7=1$ and $x_6=2,$ then since $x_8=x_9=1,$ from $(1)$ and $(2)$ we obtain $$x_1+x_2+ x_3 + x_4 + x_5=14 \quad (5) $$

and

$$x_2 + 2x_3 + 3x_4 + 4x_5 = 15. \quad (6)$$

Now $(6)$ implies $x_5 \le 2,$ but if $x_5=2$ then we must have $x_2 \ge 3$ (since $x_5=x_6=2$ there are at least $3$ occurrences of $2$) and so the LHS of $(6)$ must be at least $16,$ a contradiction. Hence $x_5=1.$

But now we have $x_0=1,x_5=1,x_6=2,x_7=1,x_8=1$ and $x_9=1,$ and since $x_6=2$ some number must occur 6 times but we do not have enough undetermined $x_i$ for this to occur unless $x_1=6.$

Substituting $x_1=6$ and $x_5=1$ in $(5)$ and $(6)$ we obtain
$$x_2+ x_3 + x_4=7 \quad (7) $$

and

$$x_2 + 2x_3 + 3x_4 = 11. \quad (8)$$

and subtracting $(7)$ from $(8)$ we obtain

$$x_3+2x_4=4. \quad (9)$$ However, since we cannot have any more $1's$ (as $x_1=6$) we must have $x_3 \ge 2$ and $x_4 \ge 2,$ which contradicts $(9).$

Thus we have shown that when $x_7=1$ we must have $x_6=1,$ which as noted above completes the proof that the unique solution is given by

$x_0=1,x_1=7,x_2=3,x_3=2,x_4=1,x_5=1,x_6=1,x_7=2,x_8=1$ and $x_9=1.$

share|improve this answer
    
+1: I had wondered if my solution was unique. Nice "case bashing," Derek! (Aside: That's a new term for me.) –  Mike Spivey Jan 27 '11 at 17:03

Here's an answer:

0 appears 1 time
1 appears 7 times
2 appears 3 times
3 appears 2 times
4 appears 1 time
5 appears 1 time
6 appears 1 time
7 appears 2 times
8 appears 1 time
9 appears 1 time

The logic is roughly as follows. Since the numbers in the blanks must be less than 10, 0 must appear only 1 time. Also, since you can't have most of the large numbers appearing more than once, 1 appears $x$ times, where $x$ is one of the larger numbers. That means $x$ probably appears twice. But then 2 can't appear 2 times, as then there would be 3 instances of 2. So perhaps 2 appears 3 times. Then 3 would appear 2 times, and from there you can determine that $x = 7$.

share|improve this answer
    
thanks. You did by trial and error? –  xport Jan 26 '11 at 11:23
    
@xport: There was some reasoning behind it, with judicious guesses in a couple of places. I've added my thought process to my answer. –  Mike Spivey Jan 26 '11 at 11:25
    
The solution is not unique? There are more solutions? –  xport Jan 26 '11 at 11:54
1  
In one of Douglas Hofstadter's columns, he discussed problems like this. Often it works to put relatively random numbers into the blanks, count up and put the new numbers in, and iterate to convergence. –  Ross Millikan Jan 26 '11 at 12:05
1  
@xport: I don't know if the solution is unique. I stopped when I found a solution. –  Mike Spivey Jan 26 '11 at 15:04

0 appears 1 time

1 appears 11 times

2 appears 2 times

3 appears 1 time

4 appears 1 time

5 appears 1 time

6 appears 1 time

7 appears 1 time

8 appears 1 time

9 appears 1 time

share|improve this answer
1  
Details?$\phantom{}$ –  J. M. Jul 19 '12 at 7:50
    
Just another solution if we do not limit the numbers to less than 10. Thus showing that there are more than 1 solutions to this question. –  AejE Jul 19 '12 at 9:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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