5
$\begingroup$

Suppose we have 4 by 4 grid with numbers 1, 2, .., 16. Can we fill the grid so that the product of the first row is equal to the product of the first column, the product of the second row is equal to the product of the second column, ..., etc?

I have already gotten answer here for n=5:

Fill in a 5x5 multiplicative magic square

However, I am trying for n=4 and I can't to do it. Can someone find solution or explain why its not possible?

$\endgroup$
7
$\begingroup$

Again the short answer is

Such a grid exists

with the example of

16  3 12  4
 9 10 14  1
 8  7 11 15
 2  6  5 13

Quick evidence.


The analysis and most of the heuristic from my 5x5 solution works here as well, but I introduced a little more heuristic which was unused in 5x5.

First, prime factor analysis:

  • 2 appears as a prime factor 15 times in total (2, 4, ..., 16)
  • 3 appears 6 times (3, 6, 9, 12, 15)
  • 5 appears thrice, 7 twice, 11 and 13 once each.

Obviously, the 11 and 13 must be placed on the main diagonal. For the remaining two spots, I chose 16 and 10 because

  • using 5 once on the diagonal will force the remaining two at the mirror positions (which reduces the search space), and
  • I wanted to remove some of the 2s from the game early, so that I have a better chance to fit in the remaining 2s later (16 = 24 is likely to be especially problematic).

Current grid:

16  .  .  .
 . 10  .  .
 .  . 11  .
 .  .  . 13

Then I placed 7-14 and 5-15 pairs close to the main diagonal, in the way that the 2 from the 14 and the 3 from the 15 do not align:

16  .  .  .
 . 10 14  .
 .  7 11 15
 .  .  5 13

Time to consider the 3s. Using the exponent notation again (recap: write down the exponents of the prime factor under consideration, and ignore everything else; place the numbers so that each row sum equals that of the corresponding column), we have three ones (3, 6, 12) and a 2 (9) to place, and a 1 (15) is already on the board.

One way to place them is

 .  1  1  .
 2  .  .  .
 .  .  .  1
 .  1  .  .

(a way to quickly see why it works: it is a knight's 4-group plus a direct mirror image.)

As I did in the 5x5, I just place the 9 and leave 3, 6, 12 to solve the prime factor 2 together.

16  .  .  .
 9 10 14  .
 .  7 11 15
 .  .  5 13

Finally consider the prime factor 2 (main diagonal entries are ignored here):

 .  A  B  W
 .  . (1) X
 Y  .  .  .
 Z  C  .  .

A-C must contain 0-2 (for 3/6/12), and W-Z must contain 0-3 (for 1/2/4/8). I decided to put a 3 into Y (which forces B = 2 right away, and I guessed it would make a better chance to make the 1st row/col work).

Then A+C = 1, so X = 0. Since W ≠ Z, C ≠ X, and C = 1. The rest is forced, and the row/col sums nicely agree. The completed grid is at the top of this answer.

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