1
$\begingroup$

In this post, a sudoku like math puzzle is proposed.

The grid must be filled while respecting a unique constraint : the sum of all $3\times3$ sub-squares must equal $2019$.

It is not that difficult to complete the grid, and there are many different solutions. I have noticed empirically that in every solution, the smallest value (among all cells) is at most $4$.

Question : is there an algebraic reason for this ?

The grid is in the picture below.

enter image description here

Note : the statement is easy to prove with a linear solver. Solving the following problem shows that the largest smallest possible value is indeed $4$. $$ \max \left\{ \min{ \{x_{ij}\} } \right\} $$ subject to $$ \sum_{k=i}^{i+2}\sum_{\ell=j}^{j+2} x_{k\ell} = 2019 \quad \forall i,j = 1,...,5 $$ where $x_{ij}$ is the value in cell $(i,j)$.

$\endgroup$
9
  • $\begingroup$ Just to be clear; your observation is that there is always a number less than $5$? $\endgroup$
    – Servaes
    Commented Dec 3, 2018 at 9:12
  • $\begingroup$ @Servaes : Yes exactly. $\endgroup$
    – Kuifje
    Commented Dec 3, 2018 at 9:13
  • 2
    $\begingroup$ The number in middle cell of the bottom row is $4$. So the smallest value of any solution has to be at most $4$. $\endgroup$ Commented Dec 3, 2018 at 9:16
  • $\begingroup$ Also just to be clear; all entries must be positive integers? $\endgroup$
    – Servaes
    Commented Dec 3, 2018 at 9:17
  • $\begingroup$ @achillehui : aaaaa yes....of course. Thanks :) But how do you know another cell does not take value $3$ for example ? $\endgroup$
    – Kuifje
    Commented Dec 3, 2018 at 9:18

1 Answer 1

0
$\begingroup$

fleablood's answer to the previous question fills in some more cells. Labelling the remaining ones with variables we get $$\begin{matrix}10 & a_{12} & a_{13} & 8 & a_{15} & a_{16} & 11 \\ a_{21} & a_{22} & a_{23} & a_{24} & a_{25} & a_{26} & a_{27} \\ a_{31} & a_{32} & a_{33} & a_{34} & a_{35} & a_{36} & a_{37} \\ 7 & a_{42} & a_{43} & 5 & a_{45} & a_{46} & 8 \\ a_{51} & a_{52} & a_{53} & a_{54} & a_{55} & a_{56} & a_{57} \\ a_{61} & a_{62} & a_{63} & a_{64} & a_{65} & a_{66} & a_{67} \\ 6 & a_{72} & a_{73} & 4 & a_{75} & a_{76} & 7\end{matrix}$$ Then the constraints on the 3x3 subsquares give 25 0-1 linear equations, each involving 8 unknowns, and there are 40 unknowns in total so the system is very underdetermined. Write them all out as a matrix, perform row reduction, and some rows drop out as linear combinations of others, leaving 21 rows in row-reduced echelon form, many of which are the original constraints. The simpler equations relate pairs: e.g. $a_{21} + a_{31} + 2 = a_{24} + a_{34}$. But none of the remaining unknowns is determined, and there's nothing stopping them all from being approximately $\frac{2000}{8} = 250$. For example, working by hand with one particular rref filling in 250s where not otherwise constrained I get a solution

$$\begin{matrix}10 & 246 & 250 & 8 & 246 & 250 & 11 \\ 251 & 262 & 250 & 253 & 262 & 250 & 250 \\ 250 & 250 & 250 & 250 & 250 & 250 & 250 \\ 7 & 249 & 250 & 5 & 249 & 250 & 8 \\ 251 & 262 & 250 & 253 & 262 & 250 & 250 \\ 250 & 250 & 250 & 250 & 250 & 250 & 250 \\ 6 & 250 & 250 & 4 & 250 & 250 & 7\end{matrix}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .