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

Improve this question
$\endgroup$
  • $\begingroup$ Just to be clear; your observation is that there is always a number less than $5$? $\endgroup$ – Servaes Dec 3 '18 at 9:12
  • $\begingroup$ @Servaes : Yes exactly. $\endgroup$ – Kuifje Dec 3 '18 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$ – achille hui Dec 3 '18 at 9:16
  • $\begingroup$ Also just to be clear; all entries must be positive integers? $\endgroup$ – Servaes Dec 3 '18 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 Dec 3 '18 at 9:18
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}$$

Improve this answer
$\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.