4
$\begingroup$

You are given a 4x6 square grid. Each square of the grid should be filled with different positive integers. The gcd (greatest common divisor) of any two adjacent (horizontally or vertically) squares should be greater than one.

What is the minimum sum of such 24 integers?

$\endgroup$

1 Answer 1

4
$\begingroup$

366:

  9 15  5 20 22 11
  3 24 10  4 18 33
 39 12  8 16 14  6
 13 26  2 28  7 21

Another solution, with smallest possible maximum entry subject to minimizing the sum:

  9 21  7 14 22 11
  3 12 28  4 18 33
 24 16  2  8 20 15
 27  6 26 10 25  5

If you ignore the sum, the smallest possible maximum entry is smaller by $1$:

 28  7 21 18 20  5
 22 14 12 10 30 25
 16  4  8  6  3 15
  2 32 26 24  9 27

$\endgroup$
2
  • $\begingroup$ thanks for your solution. Did you find it using a computer? $\endgroup$
    – ThomasL
    Apr 13, 2021 at 21:45
  • 1
    $\begingroup$ Yes, I solved it via integer linear programming. $\endgroup$
    – RobPratt
    Apr 13, 2021 at 22:38

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.