Maximizing row and column products in a 4x4 grid

Question

Using the numbers 1, 2, 3, ... 16 each exactly once, fill each square of a 4x4 grid so that the product of the numbers in each row is a multiple of $N$ and the product of the numbers in each column is also of multiple of $N$ where $N$ is a power of $2$. The goal is to maximize $N$.

Bonus question: Same as above except that $N$ is a positive integer not necessarily a power of $2$.

---

The above puzzle was inspired by the following 2016 Olympiad Cayley competition puzzle:

Dean wishes to place the positive integers 1, 2, 3, ..., 9 in the cells of a 3 × 3 square grid so that:

(i) there is exactly one number in each cell;
(ii) the product of the numbers in each row is a multiple of four;
(iii) the product of the numbers in each column is a multiple of four.

Is Dean's task possible? Prove that your answer is correct.

Answer 1

The base question is rather straightforward:

The maximal power of 2 that divides the product of numbers up to 16 is 8 + 4 + 2 + 1 = 15. Because there are 4 rows and columns, it's clear that the largest power of 2 that can be in N is 2 ^ (15 // 4) = 8.

A construction for N = 8:

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

For the bonus question, similarly notice that the maximal power of 3 that divides the product is 5 + 1 = 6, and the maximal power of 5 that divides the product is 3. Therefore, the largest possible value of N is 24.

A construction for N = 24:

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

Answer 2

For part one of the question, we only care about factors of 2 within the numbers spanning 1 to 16 and how to distribute them to maximize the minimum number of factors of two across the rows and columns. We find there are a total of 15 factors of 2 (16 has 4; 8 has 3; 4 and 12 have 2; 2, 6, 10, and 14 each have one), so we can allocate 3 factors of 2 to each row and column (i.e., N = 8). This could look like the following:

16
    8
        2  4
       10 12

with the rest filled out any way.

For the second part, we will look at other factors. For 5 or any higher prime, there are not even four within 1-16. For factors of 3, we have 6 (9 has 2; 3, 6, 12 and 15 have 1). so maximally one can go in each row and column. N becomes 8 * 3 = 24. We will fill in a few more squares:

16     15
  6  8
     3  4  2
       10 12

And the rest can be filled out any way. Sorry, I could't figure out better formatting.