19
$\begingroup$

Professor Halfbrain has spent his entire weekend by filling $10\times10$ tables with the digits $0,1,2,3,4,5,6,7,8,9$ so that each digit occurs exactly $10$ times. According to the professor, such fillings are called legal fillings. Halfbrain detected oodles and oodles of fascinating legal fillings, and he derived two extremely deep theorems on them:

Professor Halfbrain's first theorem: In every legal filling of a $10\times10$ table, there exists a row or a column that contains at least two different digits.

Professor Halfbrain's second theorem: There exists a legal filling of a $10\times10$ table, in which every row and every column contain at most ten different digits.

This puzzle asks you to improve the two theorems of professor Halfbrain and to make them even deeper. Find an integer $x$, so that "at least two different digits" in the first theorem may be replaced by "at least $x$ different digits", and so that "at most ten different digits" in the second theorem may be replaced by "at most $x$ different digits" (again yielding true statements, of course).

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ In the second theorem, surely "at most ten" means exactly ten since there are only ten digits to play with? $\endgroup$
    – Rand al'Thor
    Mar 23, 2015 at 9:54
  • $\begingroup$ It must be two different integers $x$ that replace 2 in the first theorem and 10 in the second, right? Maybe you could rephrase the last paragraph a little to make this clear. $\endgroup$
    – Rand al'Thor
    Mar 23, 2015 at 9:58
  • 2
    $\begingroup$ 1. In the second theorem, the term "at most ten" yields a correct statement. (I have seen professor Halfbrain's proof, and it was clear and correct.) --- 2. The last paragraph refers to a single integer x, and it of course is the same x in both statements. $\endgroup$
    – Gamow
    Mar 23, 2015 at 10:03
  • $\begingroup$ Ah, so the maximum $x$ such that the first theorem holds is also the minimum $x$ such that the second holds. I get it now. Nice puzzle! Maybe the [sudoku] tag? $\endgroup$
    – Rand al'Thor
    Mar 23, 2015 at 10:09
  • $\begingroup$ 1. Yes, that's correct. --- 2. No, it got nothing to do with sudoku. $\endgroup$
    – Gamow
    Mar 23, 2015 at 10:11

2 Answers 2

Reset to default
21
$\begingroup$

We can fill the grid so that every row and column has at most

$4$

different digits as follows:

enter image description here

This is optimal. Here's why we can't do better.

Say each row and column had at most $3$ distinct digits. Label each row and column with those digits. There are at most $60$ digit labels, so some digit appears in most $6$ labels, say $r$ row labels and $c$ column labels. Since only those rows and columns may contain that digit, it appears at most $rc$ times in the grid. But since $r+c\leq 6$, we must have $rc\leq 9$ (maximized for $r=c=3$), so that digit can't appear $10$ times in the grid. Contradiction.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't question your answer but could you explain how you came to 60 labels and why that automatically means at most 6 labels? I don't understand it. Also, how did you find the filling? Was some strategy involved or just trial and error? $\endgroup$
    – Ivo
    Mar 23, 2015 at 11:09
  • 5
    $\begingroup$ @IvoBeckers 10 rows + 10 columns = 20 Labels. And each Label consists of at most 3 digits! So If I write all of my labels down they consists of at most 3x20 = 60 digits. We have 10 digits - if each digit would appear 7 times we would need 70 digit-spaces in these labels. So not every digit can appear 7 or more times in the labels. So there has to be 1 digit, which only appears 6 or fewer times... This digit will hence only be present in 5 rows and 1 column, or 4 rows and 2 columns or 3 rows and 3 columns. None of which are enough spaces to appear 10 times! $\endgroup$
    – Falco
    Mar 23, 2015 at 12:42
  • 1
    $\begingroup$ @Falco Thanks for the explanation. I know understand $\endgroup$
    – Ivo
    Mar 23, 2015 at 12:44
  • $\begingroup$ This (your original answer) proves theorem 2 for x = 4. Interestingly, your proof of why x > 3 for theorem 2 also shows that x > 3 in theorem 1. So x = 4 satisfies both theorems. $\endgroup$
    – Lawrence
    Mar 23, 2015 at 14:35
  • 1
    $\begingroup$ @IvoBeckers I liked 2x5 blocks for being compact and not having anything stick out, so I tried placing them lots of different ways. The spiral-ish pattern was nice for having lines cross blocks both the short way and the long way. $\endgroup$
    – xnor
    Mar 23, 2015 at 21:29
6
$\begingroup$

for an $M$ by $M$ table where $M$ is of the form $n*n$ then it would be $x = n$ I think. So for $M=9$ then $x=3$ and this is a solution:

111222333
111222333
111222333
444555666
444555666
444555666
777888999
777888999
777888999

since 10 has no integer square root my guess it would be the square root rounded up. So my guess is $x=4$. I have no solution (yet) though

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ great intuitive approach! $\endgroup$
    – Falco
    Mar 23, 2015 at 12:46

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.