0
$\begingroup$

The question is from here

Let the set of numbers $N = \{1, 2,\ldots , 9\}$. Let the set of cells $C = N × N$.

A Sudoku solution $f$ is a function $f : C \to  N$ satisfying the following properties:

  • For all $i, j,$ and $j′,$ if $j ≠ j′$ then $f(i, j)≠f(i, j′)$
  • For all $i, i′,$ and $j,$ if $i ≠ i′$ then $f(i, j)≠f(i′,j)$
  • For all $c1$ and $c2 \in C$, if $c1 ≠ c2$ and $square(c1)=square(c2)$, then $f(c1)≠f(c2)$.

$square(i, j)$ is the number of the large box that contains the $(i, j)$ cell, where we number the large $9x9$ grids as follows:

1 4 7
2 5 8
3 6 9

The claim is: if f is a sudoku solution compatible with the board below (that is, if $f(2, 2)=1, f(1, 5)=8, f(2, 5)=5$ and so on), then $f(9, 3)=1$.

board

And the given proof is:
There must be a $1$ somewhere in box $3$ (in other words, there exists some $(i, j)$ such that $square(i, j)=3$ and $f(i, j)=1$). By rule $2$, $j$ cannot be $1$, because $f(4, 1)=1$. Similarly, since $f(2, 2)=1$, $j$ cannot be $2$. Thus $j$ must be $3$; and $f(7, 3)\ne 1$, and $f(8, 3)\ne 1$. The only cell left is $(9, 3)$, so $f(9, 3)$ must be $1$.

It is suggested that it's not a good proof. But why? And what should be a good proof like to this problem?

$\endgroup$
0
$\begingroup$

One issue with the proof as given is that you start with the assertion that:

There must be a $1$ somewhere in box $3$

which has not yet been proven. It's "obvious", but not quite obvious enough to simply state it. And that result is going to be useful, so worth proving out in a general way that for any $k, m \in N$, there must be some $c \in C$ such that $square(c) = k$ and $f(c)=m$

Then the discussion of the other entries with a $1$ in the first two columns needs to mention that those entries are not in square $3$. Again "obvious" but in order to use the rules as stated, that should be pointed out, perhaps by noting that $square(i,j)=3 \implies i \in \{1,2,3\}$ and $ j\in \{7,8,9\}$

$\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.