9
$\begingroup$

I have a 3x3 square filled with numbers. You can select a sub-rectangle^ and I will tell you the sum of all the numbers inside that rectangle. The penalty for doing this is $10-X$, where $X$ is the area of the selected sub-rectangle. How can you find all the numbers while incurring the smallest total penalty?

^ Note the sub-rectangle can be square.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Are the secret numbers unique, or can there be duplicates? $\endgroup$
    – Bass
    Nov 16, 2021 at 12:26
  • $\begingroup$ There can be duplicates. But if you have a nice solution that assumes uniqueness then please post it too! $\endgroup$
    – Dmitry Kamenetsky
    Nov 16, 2021 at 12:40

1 Answer 1

Reset to default
17
$\begingroup$

I think the best penalty we can do is

41

Reasoning

To determine nine unknown numbers requires nine linearly independent simultaneous equations, so I need to ask about nine sub-rectangles. The best way to optimize the penalty is then to pick the largest subrectangles I can and hope that the associated equations are linearly independent.
I can first pick the whole 3x3 square, then each of the four possible 2x3 (or 3x2) subrectangles, then each of the four possible 2x2 squares.
Luckily, Wolfram alpha tells me that the associated matrix for this linear system has non-zero determinant so this will allow me to compute all the numbers.
The total penalty is, therefore, $(10-9) + 4\cdot(10-6) + 4\cdot(10-4) = 41$

Improve this answer
$\endgroup$
6
  • $\begingroup$ Very nice! Does this work in all cases, eg. if all numbers are 0? $\endgroup$
    – Dmitry Kamenetsky
    Nov 16, 2021 at 13:38
  • 2
    $\begingroup$ It reminds me a bit of Rubik's Clock. $\endgroup$
    – Jaap Scherphuis
    Nov 16, 2021 at 13:41
  • 3
    $\begingroup$ @DmitryKamenetsky For an explicit calculation, you can use $a = (abcdefghi-defghi)-(bcefhi-efhi)$ for a corner cell, and $b = (abdegh-degh)+(bcefhi-efhi)-(abcdefghi-defghi)$ for an edge cell, where the cells are labelled $a$ to $h$. The other corner and edge cells are found similarly by symmetry. $\endgroup$
    – Jaap Scherphuis
    Nov 16, 2021 at 14:14
  • 3
    $\begingroup$ I came up with a solution with a larger penalty than hexomino so I was curious to see their solution. Turns out mine was the same! I think hexomino has made an error in the penalty calculation: >!the 2x2 rectangles should contribute a penalty of 6 (not 5). I would have made this a comment, but I have insufficient reputation. $\endgroup$
    – Michael Clase
    Nov 16, 2021 at 21:28
  • 2
    $\begingroup$ @JaapScherphuis: Extending that, the center cell is (I believe) the $3 \times 3$ sum, plus the sums of all four $2 \times 2$ rectangles, minus the sums of all four $3 \times 2$ rectangles. $\endgroup$
    – Michael Seifert
    Nov 17, 2021 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.