6
$\begingroup$

Consider the following grid of numbers:

enter image description here

In machine readable form:

[[-3  2  2  2 -1  2  0  1  2 -1]
 [ 0  1 -2 -1 -1  1  3  3  1  3]
 [ 1 -3  0 -1  1  2  2 -2  0  3]
 [-1  0  1 -2  0  2  2 -2 -3  2]
 [-3  0 -3  1 -2  1 -3  3  0 -3]
 [-2 -1  0  2  1  3  1  2  2 -1]
 [ 0  3  1  0  1 -1 -1  2  2  2]
 [-2 -3  1  2 -1  3  3 -1 -1  2]
 [ 2  1  3  2  0  2 -1  1  2 -1]
 [-1  3 -2 -1  1  1 -2  1  2 -1]]

If you draw a straight line from one side to another of the grid, your score is the sum of all the numbers in squares where the middle (shown with blue dots) is on the side of the line including the top left corner of the grid. You are not allowed to start or end the line exactly in the top left corner.

What is the optimal line? You are aiming to maximize the score.

$\endgroup$
2
  • 1
    $\begingroup$ would. be nice to provide text/sheet version. $\endgroup$
    – Oray
    Dec 17, 2023 at 14:10
  • 3
    $\begingroup$ @Oray I made an addition. Is that better? $\endgroup$
    – Simd
    Dec 17, 2023 at 14:21

3 Answers 3

7
$\begingroup$

The sum of all the numbers in the grid is 38.

Color-coding the grid allows us to easily see favorable/unfavorable portions of the grid:

enter image description here

Our goal is then to remove the least favorable portion with a single straight cut.

I believe this may be optimal:

Removing a sum of -7 leaves us with a sum of 45.
enter image description here

$\endgroup$
4
  • $\begingroup$ A very nice answer. How did you draw the color coded grid? $\endgroup$
    – Simd
    Dec 17, 2023 at 20:00
  • 1
    $\begingroup$ @Simd I just used the bucket tool (flood fill) in Paint $\endgroup$ Dec 17, 2023 at 20:01
  • 1
    $\begingroup$ I confirmed optimality via integer linear programming. $\endgroup$
    – RobPratt
    Dec 21, 2023 at 2:53
  • 1
    $\begingroup$ @RobPratt Could you add the ilp you used? I would be interested $\endgroup$
    – Simd
    Dec 30, 2023 at 10:01
3
$\begingroup$

The maximum is

45,

achieved, for example, by

enter image description here

I solved the problem via mixed integer linear programming as follows. Let $a_{ij}$ be the given value in cell $(i,j)$. Let $\epsilon>0$ be a small constant tolerance. Let decision variables $\alpha$ and $\beta$ define the line $\alpha i + \beta j = 1$. Let binary decision variable $x_{ij}$ indicate whether cell $(i,j)$ is selected. The problem is to maximize $\sum_{i,j} a_{ij} x_{ij}$ subject to linear constraints \begin{align} x_{0,0} &= 1 \tag1\label1 \\ \alpha i + \beta j - 1 + \epsilon &\le M(1-x_{ij}) &&\text{for all $(i,j)$} \tag2\label2 \\ -\alpha i - \beta j + 1 + \epsilon &\le M x_{ij} &&\text{for all $(i,j)$} \tag3\label3 \end{align}

Constraint \eqref{1} selects the top left corner. Big-M constraint \eqref{2} enforces $x_{ij}=1 \implies \alpha i + \beta j \le 1 - \epsilon$ so that cell $(i,j)$ is on the same side of the line as $(0,0)$. Big-M constraint \eqref{3} enforces $x_{ij}=0 \implies \alpha i + \beta j \ge 1 + \epsilon$ so that cell $(i,j)$ is on the opposite side of the line.


For the $100 \times 100$ instance (with total sum $\sum_{i,j} a_{ij}=316$), I get a maximum of $449$ by excluding the following cells with sum $-133$: enter image description here

If I fix $x_{74,10}=x_{85,29}=x_{96,48}=1$ and $x_{74+1,10}=x_{85+1,29}=x_{96+1,48}=0$, I get a maximum of $440$ by excluding the following cells with sum $-124$: enter image description here

If I fix $x_{74,10}=x_{85,29}=x_{96,48}=0$ and $x_{74-1,10}=x_{85-1,29}=x_{96-1,48}=1$, I get a maximum of $441$ by excluding the following cells with sum $-125$: enter image description here

$\endgroup$
18
  • $\begingroup$ This is a very nice example of MILP. $\endgroup$
    – Simd
    Dec 30, 2023 at 22:24
  • $\begingroup$ If you scale the problem to 100 by 100 does your code still finish quickly? $\endgroup$
    – Simd
    Dec 31, 2023 at 5:22
  • $\begingroup$ @Simd That is 100x bigger, so probably not. Do you have example data for that? $\endgroup$
    – RobPratt
    Dec 31, 2023 at 14:50
  • $\begingroup$ I will next be by a real computer in two days but I would make the data with numpy.random.randint(-3, 4, size=(100, 100)). $\endgroup$
    – Simd
    Dec 31, 2023 at 15:55
  • 1
    $\begingroup$ @Simd For your 100 by 100 instance, I got an optimal objective value of 449 in 36 minutes. $\endgroup$
    – RobPratt
    Jan 5 at 18:18
1
$\begingroup$

I have found two solutions.

Both solutions sum to 45. The sum of all the cells is 38.

I permuted a line connecting every pair of blobs.
I then consider a parallel dividing line moved slightly to one side.

First, blobs passed through are excluded from the black blob's region.
Excluded cells are (-3) + (-2) + (0) + (-2 -3) + (+2 +1) + (-1 +3 -2) = -7.
This is the same as other answers.
enter image description here

Then, blobs passed through are included with the black blob's region.
Excluded cells are (-1) + (-3) + (-2) + (0) + (-2) + (2) + (-1) = -7.
This is a new solution.
enter image description here

$\endgroup$
2
  • $\begingroup$ Very nice Indeed. $\endgroup$
    – Simd
    Jan 6 at 12:11
  • $\begingroup$ I confirmed that these are the only two optimal solutions. $\endgroup$
    – RobPratt
    Jan 9 at 23:03

Your Answer

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

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