20
$\begingroup$

Fill a $4\times4$ grid with positive integers so that:

  • Every cell has a different integer
  • The product of the numbers in each row is $5040$, and similarly for the columns

Source: This was an NPR weekly listener challenge, aired on 2005-10-09. See here.

$\endgroup$
22
$\begingroup$

A possible solution is:

10   8    3  21
12  15   14   2
 1   7   30  24
42   6    4   5

Strategy

$$5040=2^4 \times 3^2 \times 5 \times 7$$

First I decided where to put the multiples of $7$ and $5$. Then I multiplied proper exponents of $2$ and $3$ to each cell. I started with:

5 1 1 7
1 5 7 1
1 7 5 1
7 1 1 5

This formation ensures that the number of cells without a $5$ or $7$ stays minimum. There are other such formations. But this is the most simple.

Now, There are eight $1$'s, four each of $5$ and$7$. When adding exponents of $3$ my strategy was to half each number of repeatation. A simple pattern was:

1 1 3 3
3 3 1 1
1 1 3 3
3 3 1 1

Multiplying by this grid the previous one, we have:

 5  1  3 21
 3 15  7  1
 1  7 15  3
21  3  1  5

Now the repeatation pattern was like this (same color represents same powers of $3$, $5$, $7$ in factorization):

enter image description here

For any two cells with the same color I had to differentiate them by multiplying different powers of $2$. Note the red and yellow cells. There are four of each. Hence I needed at least four different powers of $2$, $2^4$ couldn't be chosen because putting $2^4$ in a red or yellow cell, forces two cells of the opposite color to have same powers of $2$, hence be same. So, the four red and yellow cells had to be multiplied with $2^0, 2^1, 2^2,2^3$ A bit of fiddling led to the pattern:

2 8 1 1
4 1 2 2
1 1 2 8
2 2 4 1

Multiplying by this grid, we get the desired solution.

$\endgroup$
  • $\begingroup$ Out of curiosity, how did you solve it? Was it just by brute force? $\endgroup$ – Bailey M Sep 10 '15 at 19:58
  • 1
    $\begingroup$ @BaileyM I was editing it when you asked. It was strategical guessing, I would say. $\endgroup$ – Rohcana Sep 10 '15 at 20:14
  • $\begingroup$ There is an error in your strategy description in 2 squares of the bottom right corner. $\endgroup$ – Sleafar Sep 10 '15 at 20:20
  • 3
    $\begingroup$ +1 For another method of construction (and other examples), check out this page. $\endgroup$ – Set Big O Sep 11 '15 at 0:10
10
$\begingroup$

Another solution (with diagonals as bonus):

10    4    6   21
18    7   20    2
28   12    3    5
 1   15   14   24

Things that multiply to 5040:

  • each of the four rows
  • each of the four columns
  • each of two diagonals
  • four center cells
  • four corner cells
  • two middle cells of the top row two middle cells of bottom row
  • two middle cells of the rightmost column and two middle cells of the leftmost column
  • each of the four corner 2x2 grids
$\endgroup$
  • $\begingroup$ Woah, what? Verified that rows, columns, diagonals, center 2x2, and corner 2x2s all work. $\endgroup$ – Ben Frankel Sep 10 '15 at 22:05
  • $\begingroup$ I was just trying to get the diagonals to work out, but it appears I stumbled into a multiplicative version of Durer's magic square $\endgroup$ – Tyler Seacrest Sep 10 '15 at 22:10
  • $\begingroup$ I've found a few other things to multiply to 5040 as well... $\endgroup$ – Ben Frankel Sep 10 '15 at 22:18
  • 1
    $\begingroup$ This isn't a good solution, it doesn't have 42 ;) $\endgroup$ – Rohcana Sep 10 '15 at 22:20
2
$\begingroup$

After unsuccessful manual fiddling with the prime factors I decided to write a program, unfortunately not fast enough. Here it is anyway. It should print all possible solutions, but will contain duplicates. And I have no idea how long it takes to run, there are many solutions.

public class Main {
    private static final int SIZE = 4;
    private static final int[] FACTORS = new int[] {2, 2, 2, 2, 3, 3, 5, 7};

    private static final ArrayList<int[]> perms = new ArrayList<>();

    private static void generateGrids(int depth, int[] grid) {
        if (depth < FACTORS.length) {
            for (int[] perm : perms) {
                for (int i = 0; i < SIZE; ++ i) {
                    grid[i * SIZE + perm[i]] *= FACTORS[depth];
                }
                generateGrids(depth + 1, grid);
                for (int i = 0; i < SIZE; ++ i) {
                    grid[i * SIZE + perm[i]] /= FACTORS[depth];
                }
            }
        } else {
            int[] tmp = new int[SIZE * SIZE];
            System.arraycopy(grid, 0, tmp, 0, tmp.length);
            Arrays.sort(tmp);
            for (int i = 0; i < tmp.length - 1; ++ i) {
                if (tmp[i] == tmp[i + 1]) {
                    return;
                }
            }
            System.out.println(Arrays.toString(grid));
        }
    }

    private static void generatePerms(int depth, int[] perm) {
        outer:
        for (int i = 0; i < SIZE; ++i) {
            for (int j = 0; j < depth; j++) {
                if (i == perm[j]) {
                    continue outer;
                }
            }
            perm[depth] = i;
            if (depth < SIZE - 1) {
                generatePerms(depth + 1, perm);
            } else {
                int[] tmp = new int[SIZE];
                System.arraycopy(perm, 0, tmp, 0, SIZE);
                perms.add(tmp);
            }
        }
    }

    public static void main(String[] args) {
        generatePerms(0, new int[SIZE]);
        int[] grid = new int[SIZE * SIZE];
        Arrays.fill(grid, 1);
        generateGrids(0, grid);
    }
}
$\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.