6
$\begingroup$

How can we fill $4*4$ Matrix with distinct positive integers such that product of the entries in each row & column is equal to $4320$ ?

My Strategy:
$$4320=2^5 \times 3^3 \times 5$$ First I filled the Matrix in such a way that each column and row gets one $5$
One such way of doing so is as follows:

5 1 1 1
1 5 1 1
1 1 5 1
1 1 1 5  

Now,There are twelve 1's & four 5's .

Then,I started to fill the three 3's in such a way that
i) It reduces maximum possible number of repetition,&
ii) product of the entries in each row & column is $27$
One Such way of doing so is as follows:

1 9 3 1
1 1 9 3
3 1 1 9
9 3 1 1  

Multiplying by this grid the previous one, we have:

$$ 5 \quad 9 \quad 3 \quad 1 $$ $$ 1 \quad 5 \quad 9 \quad 3 $$ $$ 3 \quad 1 \quad 5 \quad 9 $$ $$ 9 \quad 3 \quad 1 \quad 5 $$ Now,There are four 1's , four 5's , four 9's & four 3's.

Now the repetition pattern was like this:
$\color{green}{\text{Green}} \text{ represents } 5$
$\color{red}{\text{Red}} \text{ represents } 1$
$\color{yellow}{\text{Yellow}} \text{ represents } 3$
$\color{blue}{\text{Blue}} \text{ represents } 9$
enter image description here
Here, same color can't have same powers of 2
and also upper limit of 2's power in any box is 3 as product of the entries in each row & column should be equal to $2^5$
$\implies$ we have to fill the same color of boxes using $0,1,2 \& 3$ ; where $0$ represents $2^0$ , and so on...
I started filling the powers of 2 in the same color but could not find any such combination that will satisfy our problem.So any help please...

$\endgroup$

2 Answers 2

6
$\begingroup$

Here's one way to do it

\begin{matrix} 16&10&27&1 \\ 18&8&2&15 \\ 3&6&20&12 \\ 5&9&4&24\end{matrix}

Strategy

The weakness I saw in your strategy above was dividing up $3^3$ into $3$ and $9$ in every single row. I think this leaves you with limited options about where to place the powers of $2$ at the end. In fact, I don't think it's solvable from where you finished. Instead, I decided to start by placing the powers of $2$ first. This took a little bit of playing around with but this seemed to be the most promising outcome. Notice that each row has a different distribution of powers of $2$ and that you don't want any one number to appear too often - $1$ appears six times here which is right on the boundary of what can be tolerated for the next step.
\begin{matrix} 16&2&1&1 \\ 2&8&2&1 \\ 1&2&4&4 \\ 1&1&4&8 \end{matrix}
Next, I wanted to place the $5$s. If you try this out a bit, you realise you need to be a bit careful in order to give yourself enough room to manoeuvre when placing powers of $3$. In particular, the $5$s must be placed on a $1$, $1$, $2$, $4$ to give you the best option for the next step.
\begin{matrix} 16&10&1&1 \\ 2&8&2&5 \\ 1&2&20&4 \\ 5&1&4&8 \end{matrix}
After that, there are some necessary moves - one of the $1$s must be multiplied by $27$ and I think this has to be in the top row. One each of the $4$, $5$ and $8$ must be multplied by $3$ and this leads naturally to the fourth column having a $3$ on each of the $5$, $8$ and $4$. You find that you are forced into the placement of the rest of the $3$s after this step.
\begin{matrix} 16&10&27&1 \\ 18&8&2&15 \\ 3&6&20&12 \\ 5&9&4&24 \end{matrix}

$\endgroup$
3
  • 2
    $\begingroup$ Note that you have used the smallest 16 divisors of 4320, meaning that if you would use another set of divisors, the product of all these divisors gets too large (it has to be $4320^4$). This also proves that indeed the method proposed by @Suresh won't work, since then you can't get a 27. $\endgroup$
    – Reinier
    Commented Mar 30, 2019 at 20:26
  • $\begingroup$ @Reinier That is a great observation, I had not noticed. This really nails how restrictive the choices are. $\endgroup$
    – hexomino
    Commented Mar 30, 2019 at 21:06
  • $\begingroup$ @Reinier Sorry I can't get your point; could you please elaborately explain your statement with examples... $\endgroup$
    – Suresh
    Commented Apr 1, 2019 at 4:39
1
$\begingroup$

My answer is

I found 3 distinct ways to arrange the same 16 numbers, but no other numbers.
They are not rotations, reflections, or row/column swapping.
Although the second and third have only two pairs of cells swapped.
I solved this programmatically using C language.

 3  8 10 18
6 20 9 4
15 1 24 12
16 27 2 5
 3  8  9 20
6 4 15 12
10 27 16 1
24 5 2 18
 3  8 15 12
6 4 9 20
10 27 16 1
24 5 2 18
Although another answer was posted before I could complete this, it was found independently.
Strangely, I missed the solution given in that answer.

Step 1.
Find all the permutations of the prime factors and their powers which can be a cell value.
Each must also be a divisor of $4320$.
The largest of these is $720$ because $1 \times 2 \times 3 \times 720 = 4320$.
There were $43$ such numbers.
Using brute force to permute these in the magic square isn't feasible, so...

Step 2.
Find all the sets of 4 of these numbers whose product is $4320$.
There were $152$ distinct sets.

Step 3.
Every set must intersect with another set.
So keep those sets whose numbers all appear in at least one other set.
This reduced the 4-number sets to $146$ distinct sets.

Step 4.
Make a table of sets which can intersect, and their intersection points.
This reduced the number of perms for each set to between $60$ and $92$ other sets.

Step 5.
For each set as the top row of the magic square.
There is no need to permute this row because columns of the square can be swapped.
For each set that can intersect the top row, as the left column of square.
There is no need to permute this column because rows of the square can be swapped.
Just align the intersecting number with the top left corner.
Do the same for the other 3 columns, but permute the $9 \times 9$ square bottom right.
Finally check each of rows 2 to 4 has the right product.


Edit: I later found

9 distinct solutions

  ————————————————   ————————————————   ———————————————— 
|   1   8  20  27  |   1   8  20  27  |   1   8  20  27  |
|                  |                  |                  |
|  10   3   9  16  |  10   9   3  16  |  12  10  18   2  |
|                  |                  |                  |
|  18  12   4   5  |  18   4  12   5  |  15   6   3  16  |
|                  |                  |                  |
|  24  15   6   2  |  24  15   6   2  |  24   9   4   5  |
  ————————————————   ————————————————   ———————————————— 
|   1   8  20  27  |   1  10  16  27  |   1  10  16  27  |
|                  |                  |                  |
|  12  18   4   5  |  12   3   6  20  |  12   3  15   8  |
|                  |                  |                  |
|  15   3   6  16  |  15   8   9   4  |  18  24   2   5  |
|                  |                  |                  |
|  24  10   9   2  |  24  18   5   2  |  20   6   9   4  |
  ————————————————   ————————————————   ———————————————— 
|   1  10  16  27  |   1  10  16  27  |   1  10  16  27  |
|                  |                  |                  |
|  12   6   3  20  |  12   6  15   4  |  12  24   3   5  |
|                  |                  |                  |
|  15   8  18   2  |  18  24   2   5  |  18   2  15   8  |
|                  |                  |                  |
|  24   9   5   4  |  20   3   9   8  |  20   9   6   4  |
  ————————————————   ————————————————   ———————————————— 

Here is the code for the "Edit" part of the answer.

// simpler code producing (unformatted) magic squares
// based on the information from earlier tests that only 16 numbers will work

#include <stdio.h>
#include <string.h>

#define MAGIC   4320

int possy[] = { 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 27 };
int history[16];
int symmtry[16];
char used[16];
int solrows[20000][16];
int solcols[20000][16];

int result;

void recur(int level)
{
    switch (level) {
        // premature truncaction of search when impossible
        case 3: if(history[0] * history[1] * history[2] > MAGIC) return;
                break;
        case 4: if(history[0] * history[1] * history[2] * history[3] != MAGIC) return;
                break;
        case 7: if(history[4] * history[5] * history[6] > MAGIC) return;
                break;
        case 8: if(history[4] * history[5] * history[6] * history[7] != MAGIC) return;
                break;
        case 9: if(history[0] * history[4] * history[8] > MAGIC) return;
                break;
        case 10:if(history[1] * history[5] * history[9] > MAGIC) return;
                break;
        case 11:if(history[8] * history[9] * history[10] > MAGIC) return;
                if(history[2] * history[6] * history[10] > MAGIC) return;
                break;
        case 12:if(history[8] * history[9] * history[10] * history[11] != MAGIC) return;
                if(history[3] * history[7] * history[11] > MAGIC) return;
                break;
        case 13:if(history[0] * history[4] * history[8] * history[12] != MAGIC) return;
                break;
        case 14:if(history[1] * history[5] * history[9] * history[13] != MAGIC) return;
                break;
        case 15:if(history[12] * history[13] * history[14] > MAGIC) return;
                if(history[2] * history[6] * history[10] > MAGIC) return;
                break;
        // check solution
        case 16:if(history[12] * history[13] * history[14] * history[15] != MAGIC) return;
                if(history[3] * history[7] * history[11] * history[15] != MAGIC) return;

                // check if same rows already found in diff order
                for(int k=0; k<result; k++) {
                    int match = 0;
                    for(int i=0; i<16; i+=4) {
                        for(int j=0; j<16; j+=4) {
                            if(memcmp(&history[i], &solrows[k][j], 4 * sizeof history[0]) == 0)
                                match++;
                        }
                    }
                    if(match == 4) return;
                }
                for(int k=0; k<result; k++) {
                    int match = 0;
                    for(int i=0; i<16; i+=4) {
                        for(int j=0; j<16; j+=4) {
                            if(memcmp(&history[i], &solcols[k][j], 4 * sizeof history[0]) == 0)
                                match++;
                        }
                    }
                    if(match == 4) return;
                }

                // check if same cols already found in diff order
                symmtry[ 0] = history[ 0];
                symmtry[ 1] = history[ 4];
                symmtry[ 2] = history[ 8];
                symmtry[ 3] = history[12];

symmtry[ 4] = history[ 1]; symmtry[ 5] = history[ 5]; symmtry[ 6] = history[ 9]; symmtry[ 7] = history[13];
symmtry[ 8] = history[ 2]; symmtry[ 9] = history[ 6]; symmtry[10] = history[10]; symmtry[11] = history[14];
symmtry[12] = history[ 3]; symmtry[13] = history[ 7]; symmtry[14] = history[11]; symmtry[15] = history[15]; for(int k=0; k<result; k++) { int match = 0; for(int i=0; i<16; i+=4) { for(int j=0; j<16; j+=4) { if(memcmp(&symmtry[i], &solcols[k][j], 4 * sizeof symmtry[0]) == 0) match++; } } if(match == 4) return; } for(int k=0; k<result; k++) { int match = 0; for(int i=0; i<16; i+=4) { for(int j=0; j<16; j+=4) { if(memcmp(&symmtry[i], &solrows[k][j], 4 * sizeof symmtry[0]) == 0) match++; } } if(match == 4) return; } // print & store for(int j=0; j<16; j+=4) { for(int i=0; i<4; i++) { printf("%3d", history[j+i]); } printf("\n"); } printf("\n"); memcpy(solrows[result], history, sizeof history); memcpy(solcols[result], symmtry, sizeof symmtry); result++; return; }
// recursion for(int i=0; i<16; i++) { if(used[i] == 0) { used[i] = 1; history[level] = possy[i]; recur(level + 1); used[i] = 0; } } } int main(void) { // generate perms for top row int a = 0; history[0] = possy[a]; used[0] = 1; for(int b=a+1; b<16; b++) { history[1] = possy[b]; used[b] = 1; for(int c=b+1; c<16; c++) { history[2] = possy[c]; used[c] = 1; for(int d=c+1; d<16; d++) { history[3] = possy[d]; used[d] = 1; // other cells recur(4); used[d] = 0; } used[c] = 0; } used[b] = 0; } printf("result=%d\n", result); }

$\endgroup$
2
  • $\begingroup$ Can you please share your C program source code... $\endgroup$
    – Suresh
    Commented Mar 31, 2019 at 11:53
  • 1
    $\begingroup$ @Suresh I have added the code used for the later "edit". The code for the first part was 5 distinct exercises, each generating arrays as source code for the next step, and is too large and messy to show. $\endgroup$ Commented Mar 31, 2019 at 12:36

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.