Is it possible to fill a 2 0 1 7 × 2 0 1 7 square grid with 2 0 1 7 2 distinct positive integers such that the product of the numbers in each row and each column is the same?
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.
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.
Log in to reply
No reason. The question asked whether it was possible. I showed it was.
This was the solution I had in mind. Any other algorithm ideas not based on magic squares?
Log in to reply
I think this works. Put x i , j = A u B v 1 ≤ I , j ≤ N where 1 ≤ u , v ≤ N are the uniquely chosen integers such that i − j ≡ u i + j ≡ v ( m o d N ) and A , B are coprime positive integers. The common row/column product is then ( A B ) 2 1 N ( N + 1 ) . This is because the elements of each row/column contain the factors A j , B k for 1 ≤ j , k ≤ N multiplied together in A B -pairs in some order.
This works for N odd, but that is OK for N = 2 0 1 7 .
Log in to reply
The u 's and 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 's, then they have different v 's.) It's well-known that a pair of orthogonal Latin squares exist for all N = 2 , 6 , so this solution works for those N 's; in particular, N = 2 0 1 7 .
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.
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 and α → 1 , b and β → 2 , etc...). Pick two coprime numbers A and B. Put the number A a B α (and so forth) in the square a α , etc... Graeco-Latin squares are known to exist for any number ≥ 3 except 6, but I honestly don't know how exlpicit the proof is.
2nd cheap variation: take any solutions (i.e. 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 2 0 1 7 and b 1 , b 2 , … , b 2 0 1 7 . All those numbers should be coprime to each other. instead of sending the Graeco latin pair ( x , y ) to A x B y , send them to a x a y . Actually "coprime" is a bit overkill, some weaker hypothesis would do...
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 be the n t h prime number. Here is how my solution would look for a three by three square -
p 1 p 4 p 2 p 5 p 3 p 6 p 2 p 6 p 3 p 4 p 1 p 5 p 3 p 5 p 1 p 6 p 2 p 4
Each row and each column contain the first six prime numbers and so they all have the same magic product 2 × 3 × 5 × 7 × 1 1 × 1 3 . 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 4 0 3 4 t h to the 2 0 1 8 t h 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 4 0 3 4 p i
Log in to reply
Each component ( p 1 , p 2 , p 3 and 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.
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.
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.
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.
The question asks if the "products" of rows and columns, not the sums....
Log in to reply
By taking powers, sums of the exponents become products of the powers.
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 and α → 1 , b and β → 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 put the number A x B y . Graeco-Latin squares are known to exist for any number ≥ 3 except 6.
Note: you can relax the hypothesis on the coprimality of A and B. In fact, if A = p a q b and B = p c q d all you need is that the matrix ( a c b d ) 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 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 2 0 1 6 , a 2 0 1 7
2nd row : a 2 0 1 7 , a 1 , a 2 , … , a 2 0 1 5 , a 2 0 1 6
3rd row : a 2 0 1 6 , a 2 0 1 7 , a 1 , … , a 2 0 1 4 , a 2 0 1 5
etc...
The product of each row and each column is ∏ i = 1 2 0 1 7 a i . Taking a i = i one gets a product of 2 0 1 7 ! .
Shouldn't all the numbers be distinct? Not sure if this answer applies in that case.
You do not have 2 0 1 7 2 distinct numbers. You have 2 0 1 7 distinct numbers, each repeated 2 0 1 7 times.
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
Log in to reply
No you couldn't. The proposed pattern uses primes p 1 , p 2 , . . . , p 2 0 1 7 , with the prime in the ( m , n ) position being p m + n − 1 where the index is calculated modulo 2 0 1 7 . 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.
correct, I misread the question!
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?
Log in to reply
We are no saying that you have to use the numbers from 1 to 2 0 1 7 2 . You just have to use 2 0 1 7 2 distinct positive integers
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.
it is said that each 2017*2017 number will be distinct so how you use same numbers in another rows?
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.
Let the element in row i , column j be p i + j q i − j where i + j and i − j are computed mod 2017 and p 0 , p 1 , … , p 2 0 1 6 , q 0 , q 1 , … , q 2 0 1 6 are distinct primes.
Every row or column product is equal to p 0 p 1 … p 2 0 1 6 q 0 q 1 … q 2 0 1 6 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!
Problem Loading...
Note Loading...
Set Loading...
Let the number in row i , column j be equal to p a ( i , j ) , where p is prime and a ( i , j ) are the numbers in a 2 0 1 7 × 2 0 1 7 magic square of ordinary type. There are plenty of algorithms for finding a magic square using the numbers 1 , 2 , 3 , . . . , 2 0 1 7 2 , so we are done.