8
$\begingroup$

I've encountered a problem that seems very simple, but turned out to just be frustrating, and now I seek math experts to help me. I've got a square table with Light Blue, White, Red and Green blocks.

Magic Table Puzzle - Empty

The Light Blue blocks cuts the table in two equal parts diagonally from the top left to bottom right. The bottom left half of the table is a mirror image of the top right, but the Red/Green boxes are inverted / opposites.

Rules of the puzzle:

  1. Only whole numbers allowed and you can only put numbers in red and green blocks.
  2. Red blocks must contain negative numbers
  3. Green blocks must contain positive numbers
  4. All the white blocks and light blue blocks count as 0 and this is not allowed to change
  5. Boxes that are mirror opposites must add up to 0

Aim of the puzzle:

In the end all the columns must add up to 0 and all the rows must add up to to 0

I would appreciate solutions to this puzzle, but what I really would like is if some math expert out there could give me the smallest whole number solution.

What I mean is: If I have two solutions, and I add up the numbers in all the green blocks for both of them, then the solution with the lower sum would be "smaller".

Even better would be if someone could explain to me how to find the smallest whole number solution for other tables, with different red/green configurations or different sizes, that work in the same way.

I would like to find a general optimal solution, if such a solution actually exists in reality.

Here's an attempted solution:

Magic Table Puzzle - Try

Here are solutions I've found so far:

Solution 1:

Magic Table Puzzle - Solution 1

Solution 2:

Magic Table Puzzle - Solution 2

Any help would be appreciated.

$\endgroup$
13
  • 2
    $\begingroup$ By the way, welcome to the Mathematics Stack Exchange! Congratulations on your first question! You have asked a good question! $(+1)$ $\endgroup$ – Mr Pie May 24 '18 at 11:30
  • 1
    $\begingroup$ :) Thanks @user477343 $\endgroup$ – Shiasu-sama May 24 '18 at 11:31
  • 1
    $\begingroup$ Small observation: if you have a solution, and then double all the red/green entries, it's still a solution. In your example, you're constrained in the lower right by "if I put a positive number in this green cell, I'll have to change some red cell to zero." But if all the numbers started out relatively large, you'd have more "room to move". Of course, the row/column sums would tend to be larger as well, but maybe finding a "large" solution and working to decrease it might be worthwhile. This is roughly the "convert feasible soln of constrain problem to optimal" approach to linear programming. $\endgroup$ – John Hughes May 24 '18 at 12:09
  • 1
    $\begingroup$ Overall, this is just an integer linear programming problem, for which there are lots of algorithms, few suited for hand-solution on a large case like this. Sigh. $\endgroup$ – John Hughes May 24 '18 at 12:10
  • 2
    $\begingroup$ This is an interesting puzzle. One way to start on a research problem like this is to work out all the possible cases by hand for small puzzles. There are just two $2 \times 2$ - one is all zeroes, the other has $\pn 1$ for entries off the diagonal. What about all $3 \times 3$ puzzles? Do them all (not too many). You can skip those with a whole row of white/blue. Perhaps thoughts and patterns will emerge. Some larger puzzles may split in two. $\endgroup$ – Ethan Bolker May 24 '18 at 13:45
5
$\begingroup$

This can be formulated as an Integer Programming or Constraint Programming problem. Let $x_{ij} \in \mathbb{Z}$ be the value of cell $(i,j)$, then

$$\begin{align} &x_{i,j} = 0 && \text{white and blue cells}\\ &x_{i,j} \ge 1 && \text{green cells}\\ &x_{i,j} \le -1 && \text{red cells}\\ &x_{i,j}= -x_{j,i} && \forall i<j\\ &\sum_i x_{i,j} = 0 &&\forall j\\ &\sum_j x_{i,j} = 0 &&\forall i\\ \end{align}$$

These are all linear constraints. (The model can be reformulated by skipping all white/blue cells: that would make the problem smaller).

I tried your problem, and if I made no errors transcribing the data, the problem does not have a feasible solution. (Well, I made some errors. See below for updated results).

Update

After fixing my input data, and adding the objective: $$\min \sum_{(i,j) \in Green} x_{i,j}$$ I get:

enter image description here

The total value of the green cells is 87 (this is the optimal value: no better solution exists). This solution was found in 0.28 seconds.

$\endgroup$
9
  • $\begingroup$ :D @ErwinKalvelagen Could you explain to me where / how you transcribed all the problems linear constraints and objective to get you this brilliant solution in 0.28 seconds? $\endgroup$ – Shiasu-sama May 24 '18 at 21:48
  • 1
    $\begingroup$ I used the MIP formulation from my answer. I expressed the model in GAMS and and solved it with Cplex. I think it can be solved quickly with any decent MIP solver. $\endgroup$ – Erwin Kalvelagen May 24 '18 at 22:00
  • $\begingroup$ Thank you :). I really appreciate it. I'll check it out and maybe add some more linear constraints. $\endgroup$ – Shiasu-sama May 24 '18 at 22:08
  • $\begingroup$ I guess a by-hand method to get to this same solution is far out of reach huh? $\endgroup$ – Shiasu-sama May 24 '18 at 22:15
  • $\begingroup$ Don't know if there are good strategies to do this by hand or analytically. $\endgroup$ – Erwin Kalvelagen May 24 '18 at 22:18
1
$\begingroup$

After tedious trial and error I found two solutions:

Solution 1:

Magic Table Puzzle - Solution 1

Solution 2:

Magic Table Puzzle - Solution 2

Solution 1 is better because when I add up all the green block values; I get 520; which is lower than Solution 2's 565.

What's really interesting is the lowest number used in Solution 1 is 2 and the lowest number used in Solution 2 is 1, but Solution 1 is a "smaller" solution.

So either Solution 1 is the "smallest" / optimal solution (which I doubt greatly) or there is a "smaller" solution out there.

I would really appreciate any help / feedback.

$\endgroup$
0
$\begingroup$

I've now written software that can find solutions to these types of problems. It has led me to find this solution:

enter image description here

The highest integer this solution uses is 5

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