# Maximizing row and column products in a 4x4 grid

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.

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

• +1 Nice answer. Concise and correct. Commented Jul 17 at 20:52

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.

• I've added the "better formatting" - check the edit to see how I did it. It's not perfect, because text preceded by a block of preformatted text shows through spoilers. Commented Jul 17 at 23:48
• the first solution should swap 2 and 4 to match the second solution (for now, column 3 is not a multiple of 8 in first solution) Commented Jul 18 at 8:35