Product Grid

Is it possible to fill a 2017 × 2017 2017 \times 2017 square grid with 201 7 2 2017^2 distinct positive integers such that the product of the numbers in each row and each column is the same?

Yes No

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Mark Hennings
Oct 8, 2017

Let the number in row i i , column j j be equal to p a ( i , j ) p^{a(i,j)} , where p p is prime and a ( i , j ) a(i,j) are the numbers in a 2017 × 2017 2017 \times 2017 magic square of ordinary type. There are plenty of algorithms for finding a magic square using the numbers 1 , 2 , 3 , . . . , 201 7 2 1,2,3,...,2017^2 , so we are done.

I don't see any reason p needs to be prime. It just needs to be a number that is not zero or 1.

By making sure p is not zero or 1, you are ensuring each number is distinct if it has a different exponent. By making it an exponent, you are ensuring the numbers from the magic square add.

Stephen Weinberg - 3 years, 7 months ago

Log in to reply

No reason. The question asked whether it was possible. I showed it was.

Mark Hennings - 3 years, 7 months ago

This was the solution I had in mind. Any other algorithm ideas not based on magic squares?

Eli Ross Staff - 3 years, 8 months ago

Log in to reply

I think this works. Put x i , j = A u B v 1 I , j N x_{i,j} \; = \; A^uB^v \hspace{2cm} 1 \le I,j \le N where 1 u , v N 1 \le u,v \le N are the uniquely chosen integers such that i j u i + j v ( m o d N ) i - j \; \equiv \; u \hspace{1cm} i + j \; \equiv \; v \hspace{1cm} \pmod{N} and A , B A,B are coprime positive integers. The common row/column product is then ( A B ) 1 2 N ( N + 1 ) (AB)^{\frac12N(N+1)} . This is because the elements of each row/column contain the factors A j A^j , B k B^k for 1 j , k N 1 \le j,k \le N multiplied together in A B AB -pairs in some order.

This works for N N odd, but that is OK for N = 2017 N=2017 .

Mark Hennings - 3 years, 8 months ago

Log in to reply

The u u 's and v v 's form two orthogonal Latin squares. (Each of them forms a Latin square, and no two cells are identical; if two cells have equal u u 's, then they have different v v 's.) It's well-known that a pair of orthogonal Latin squares exist for all N 2 , 6 N \neq 2, 6 , so this solution works for those N N 's; in particular, N = 2017 N = 2017 .

Ivan Koswara - 3 years, 8 months ago

Log in to reply

@Ivan Koswara as a note (for those who get lost in terminology). Orthogonal Latin square = Graeco-Latin square. My (improved) answer was inspired from this comment of Mark.

Antoine G - 3 years, 7 months ago

1st cheap variation: (of Mark Hennings solution): consider a Graeco-Latin square (see https://en.wikipedia.org/wiki/Graeco-Latin_square ). Associate to the corredponding Roman and Greek letters the same number (e.g. a a and α 1 \alpha \to 1 , b b and β 2 \beta \to 2 , etc...). Pick two coprime numbers A and B. Put the number A a B α A^a B^\alpha (and so forth) in the square a α a \alpha , etc... Graeco-Latin squares are known to exist for any number 3 \geq 3 except 6, but I honestly don't know how exlpicit the proof is.

2nd cheap variation: take any solutions (i.e. p p as base and the magic square entries as exponents, or A and B as base and the Graeco-Latin square entries as exponent). As long as the bases of the exponents are all coprime, you can multiply square-wise the two solutions and get a new solution.

3rd cheap variation: pick two lists of numbers a 1 , a 2 , , a 2017 a_1, a_2, \ldots , a_{2017} and b 1 , b 2 , , b 2017 b_1, b_2, \ldots , b_{2017} . All those numbers should be coprime to each other. instead of sending the Graeco latin pair ( x , y ) (x,y) to A x B y A^x B^y , send them to a x a y a_x a_y . Actually "coprime" is a bit overkill, some weaker hypothesis would do...

Antoine G - 3 years, 7 months ago

I have an idea which could be worked up into a solution. It does not rely on any prior knowledge of magic or Latin squares.

Let p n p_n be the n t h n^{th} prime number. Here is how my solution would look for a three by three square -

p 1 p 4 p 2 p 6 p 3 p 5 p 2 p 5 p 3 p 4 p 1 p 6 p 3 p 6 p 1 p 5 p 2 p 4 \begin{array}{ccc} p_1 p_4 & p_2 p_6 & p_3 p_5 \\ p_2 p_5 & p_3 p_4 & p_1 p_6 \\ p_3 p_6 & p_1 p_5 & p_2 p_4 \end{array}

Each row and each column contain the first six prime numbers and so they all have the same magic product 2 × 3 × 5 × 7 × 11 × 13 2 \times 3 \times 5 \times 7 \times 11 \times 13 . Moreover, by the fundamental theorem of arithmetic, all of the nine entries in the square are different.

Explicitly; For the 2017 by 2017 square the first multiplicands in each column cycle through the first 2017 prime numbers starting with the first prime number in the first place in the first column, the second prime number in the first place in the second column and so on. The second multiplicands in each column cycle backwards from the 403 4 t h 4034^{th} to the 201 8 t h 2018^{th} prime numbers starting from the bottom of the column and again changing the starting point for each new column as shown in the three by three example.

For this construction we get the (ridiculously large) magic product

1 4034 p i \prod_{1}^{4034}p_i

Peter Macgregor - 3 years, 7 months ago

Log in to reply

Each component ( p 1 , p 2 , p 3 p_1,p_2,p_3 and p 4 , p 5 , p 6 p_4,p_5,p_6 ) forms a Latin square (basically all entries in each row/column are distinct). In order to guarantee that no duplicates occur on the whole board, the two Latin squares must be orthogonal, which is precisely the definition (no two cells have the exact same content on both Latin squares, they must differ on at least one Latin square). So yeah, that's basically rephrasing the known definitions in your own words, but that's definitely helpful for people that don't know about the terms yet.

Ivan Koswara - 3 years, 7 months ago

Unless I am mistaken, a magic square satisfys the condition that the sums in each row and column are equal, without any requirements of the products for each row or column. A magic square algorithm isn’t useful to us for this reason.

We are required to find the product of each list be equal by this problem.

Brian Dearing - 3 years, 7 months ago

Log in to reply

True, but if the elements of a magic square are the indices, to the same base, of the entries in our square, then the products of the elements in the rows and columns (and the main diagonals) of that new square are all the same, because the index sums are all the same.

Mark Hennings - 3 years, 7 months ago

Taking the exponent of sums gives products. If

8 1 6
3 5 7
4 9 2

is a magic square with equal sums, then taking 2 to the power of them:

256 2 64
8 32 128
16 512 4

is a magic square with equal products.

Ivan Koswara - 3 years, 7 months ago

The question asks if the "products" of rows and columns, not the sums....

Ronald Agee - 3 years, 7 months ago

Log in to reply

By taking powers, sums of the exponents become products of the powers.

Arjen Vreugdenhil - 3 years, 7 months ago
Antoine G
Oct 16, 2017

Here is a small variation (of Mark Hennings solution) using a Graeco-Latin square (see https://en.wikipedia.org/wiki/Graeco-Latin_square ).

Associate to the corresponding Roman and Greek letters the same number (e.g. a a and α 1 \alpha \to 1 , b b and β 2 \beta \to 2 , etc...). You could pick any sequence of distinct positive integers in this association, the important part is that the Roman and the Greek symbol are sent to the same value.

Pick two coprime numbers A and B. In the square labelled by the symbols (now numbers) x , y x,y put the number A x B y A^x B^y . Graeco-Latin squares are known to exist for any number 3 \geq 3 except 6.

Note: you can relax the hypothesis on the coprimality of A and B. In fact, if A = p a q b A = p^aq^b and B = p c q d B = p^cq^d all you need is that the matrix ( a b c d ) \left( \begin{array}{cc} a & b \\ c & d \end{array} \right) is invertible. So it's even thinkable to have a case where A divides B.

A cheap way to construct more solutions: take any solutions (i.e. p p as base and the magic square entries as exponents as in the Answer by Mark Hennings, or A and B as base and the Graeco-Latin square entries as exponent as in this answer). If the bases are all coprime, you can multiply square-wise the two solutions and get a new solution.

[ Edit: from here onwards is the old and off-topic answer (I misread the question!). I'm leaving it so that the comments below are not out of context. ]

Take the multiplication table of a group of order 2017. Relabel the elements of the group with any positive integers you like. Because each row and each column contains all the elements exactly once, the product will be the same.

Since 2017 is prime there is only one group (the cyclic group) so this amounts to

1st row : a 1 , a 2 , a 3 , , a 2016 , a 2017 a_1, a_2, a_3 , \ldots, a_{2016}, a_{2017}

2nd row : a 2017 , a 1 , a 2 , , a 2015 , a 2016 a_{2017}, a_1, a_2 , \ldots, a_{2015}, a_{2016}

3rd row : a 2016 , a 2017 , a 1 , , a 2014 , a 2015 a_{2016}, a_{2017}, a_1 , \ldots, a_{2014}, a_{2015}

etc...

The product of each row and each column is i = 1 2017 a i \prod_{i=1}^{2017} a_i . Taking a i = i a_i = i one gets a product of 2017 ! 2017! .

Shouldn't all the numbers be distinct? Not sure if this answer applies in that case.

Pranav Desai - 3 years, 7 months ago

Log in to reply

perfectly right, I misread the question!

Antoine G - 3 years, 7 months ago

You do not have 201 7 2 2017^2 distinct numbers. You have 2017 2017 distinct numbers, each repeated 2017 2017 times.

Mark Hennings - 3 years, 7 months ago

Log in to reply

You could use the first 2017 primes, then use the same table but in the other direction with the next 2017 primes. Multiply the values and it should work

Manuel Salazar - 3 years, 7 months ago

Log in to reply

No you couldn't. The proposed pattern uses primes p 1 , p 2 , . . . , p 2017 p_1,p_2,...,p_{2017} , with the prime in the ( m , n ) (m,n) position being p m + n 1 p_{m+n-1} where the index is calculated modulo 2017 2017 . If you try to run this pattern "the other direction", namely by columns instead of rows, you get exactly the same pattern. Multiplying two of these patterns together would still result with equal numbers on some diagonals.

Mark Hennings - 3 years, 7 months ago

correct, I misread the question!

Antoine G - 3 years, 7 months ago

I am confused.Somewhere, just below 2017*2017 is a prime number. Since this number can only be in one column (and row) because all numbers are distinct, how can any other column or row have the same product?

Richard Rowlands - 3 years, 7 months ago

Log in to reply

We are no saying that you have to use the numbers from 1 1 to 201 7 2 2017^2 . You just have to use 201 7 2 2017^2 distinct positive integers

Mark Hennings - 3 years, 7 months ago

As Mark Hennings said, you only have 2017 distinct integers, as you are repeating their usage on each subsequent row.

We need 2017^2 distinct integers. Each grid number should not have been used before.

Brian Dearing - 3 years, 7 months ago

Log in to reply

yep, I misread the question!

Antoine G - 3 years, 7 months ago

it is said that each 2017*2017 number will be distinct so how you use same numbers in another rows?

hasan kibria - 3 years, 7 months ago

Log in to reply

I corrected that more than a week ago. Please only read the first part of the answer only up to the text in boldface. The part after the boldface does not make sense as many have already pointed out.

Antoine G - 3 years, 7 months ago
Paul Sherman
Oct 19, 2017

Let the element in row i i , column j j be p i + j q i j p_{i+j}q_{i-j} where i + j i+j and i j i-j are computed mod 2017 and p 0 , p 1 , , p 2016 , q 0 , q 1 , , q 2016 p_0, p_1, \dots, p_{2016}, q_0, q_1, \dots, q_{2016} are distinct primes.

Every row or column product is equal to p 0 p 1 p 2016 q 0 q 1 q 2016 p_0p_1\dots p_{2016} q_0q_1\dots q_{2016} and every element is the product of a unique pair of primes and therefore distinct from all other elements.

A very classy solution, not relying on assuming the audience knows magic square algorithms off the top of their head. Thank you!

Michael Borrello - 3 years, 7 months ago
Tomáš Žilínek
Oct 21, 2017

One word: SUDOKU

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...