# Largest smallest value in sudoku like puzzle

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.

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

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

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}$$