Largest smallest value in sudoku like puzzle












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 $3times3$ 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_{kell} = 2019 quad forall i,j = 1,...,5
$$

where $x_{ij}$ is the value in cell $(i,j)$.










share|cite|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


















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 $3times3$ 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_{kell} = 2019 quad forall i,j = 1,...,5
$$

where $x_{ij}$ is the value in cell $(i,j)$.










share|cite|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
















1












1








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 $3times3$ 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_{kell} = 2019 quad forall i,j = 1,...,5
$$

where $x_{ij}$ is the value in cell $(i,j)$.










share|cite|improve this question











$endgroup$




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



The grid must be filled while respecting a unique constraint : the sum of all $3times3$ 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_{kell} = 2019 quad forall i,j = 1,...,5
$$

where $x_{ij}$ is the value in cell $(i,j)$.







combinatorics number-theory recreational-mathematics puzzle






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 3 '18 at 9:16







Kuifje

















asked Dec 3 '18 at 9:06









KuifjeKuifje

7,1302725




7,1302725












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




















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


















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




$begingroup$
@Servaes : Yes exactly.
$endgroup$
– Kuifje
Dec 3 '18 at 9:13




2




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






$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












1 Answer
1






active

oldest

votes


















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} & 7end{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 & 7end{matrix}$$






share|cite|improve this answer









$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3023814%2flargest-smallest-value-in-sudoku-like-puzzle%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    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} & 7end{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 & 7end{matrix}$$






    share|cite|improve this answer









    $endgroup$


















      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} & 7end{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 & 7end{matrix}$$






      share|cite|improve this answer









      $endgroup$
















        0












        0








        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} & 7end{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 & 7end{matrix}$$






        share|cite|improve this answer









        $endgroup$



        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} & 7end{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 & 7end{matrix}$$







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 3 '18 at 10:27









        Peter TaylorPeter Taylor

        8,80312341




        8,80312341






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3023814%2flargest-smallest-value-in-sudoku-like-puzzle%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Mont Emei

            Province de Neuquén

            Journaliste