mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   November 2019 (https://www.mersenneforum.org/showthread.php?t=24922)

Xyzzy 2019-11-07 13:13

November 2019
 
[url]http://www.research.ibm.com/haifa/ponderthis/challenges/November2019.html[/url]

Dieter 2019-11-10 09:09

„However, we're looking for solutions that lead to values of the determinant other than those that can be achieved with Latin squares.“
How should I know if a value, achieved with a Non-Latin-square, can eventually be achieved with a Latin square, too? I cannot check all Latin squares.
I hope that we shall consider Non Latin squares without checking this.
Until now my best matrix has a determinant = 921979020.

a1call 2019-11-10 09:31

Well you have done better than I have. The best I have is
921002400 Which I assume you must have run across as well since the large determinants seem to be getting more scarce as they get larger. I think your concern is valid and it is probably prohibitively impractical to prove that it is impossible to have a given large value unachievable by Latin Squires. It even might be the case that such a constraint is impossible for large values.

Number of normalized 9x9 Latin squares:
377597570964258816
[url]http://mathworld.wolfram.com/LatinSquare.html[/url]

And I could not find the known record value by googling which is the value to bit for double astrics.

Dieter 2019-11-10 09:58

[QUOTE=a1call;530181]Well you have done better than I have. The best I have is
921002400 Which I assume you must have run across as well since the large determinants seem to be getting more scarce as they get larger. I think your concern is valid and it is probably prohibitively impractical to prove that it is impossible to have a given large value unachievable by Latin Squires. It even might be the case that such a constraint is impossible for large values.

Number of normalized 9x9 Latin squares:
377597570964258816
[url]http://mathworld.wolfram.com/LatinSquare.html[/url]

And I could not find the known record value by googling which is the value to bit for double astrics.[/QUOTE]

I have googled 929587995

Dieter 2019-11-10 10:00

9 4 3 8 1 5 2 6 7
3 9 8 5 4 6 1 7 2
4 1 9 3 2 8 7 5 6
1 2 4 9 7 3 6 8 5
8 3 5 6 9 7 4 2 1
2 7 1 4 6 9 5 3 8
5 8 6 7 3 2 9 1 4
7 6 2 1 5 4 8 9 3
6 5 7 2 8 1 3 4 9

found in the net

a1call 2019-11-10 10:59

Acknowledged with thanks and kudos on you search capabilities.:smile:

uau 2019-11-10 16:51

I think this is a clearer version:
[CODE]
1 2 4 8 6 7 5 3 9
9 1 2 4 8 6 7 5 3
3 9 1 2 4 8 6 7 5
5 3 9 1 2 4 8 6 7
7 5 3 9 1 2 4 8 6
6 7 5 3 9 1 2 4 8
8 6 7 5 3 9 1 2 4
4 8 6 7 5 3 9 1 2
2 4 8 6 7 5 3 9 1
[/CODE]That is, just 9 rotated copies of the same row (or column).

Dr Sardonicus 2019-11-11 15:58

There is a conjecture that for an nxn Latin square with entries the integers 1 to n, viewed an an nxn matrix, the maximum |determinant| occurs with a "circulant" matrix -- each succeeding row is formed by rotating one space to the left (the previous post rotates to the right, but it doesn't matter).

I did a totally mindless search of all 362880 permutations of the numbers 1 to 9, and found the maximum |determinant| of circulant 9x9 Latin squares with entries 1 to 9 was 929587995. This occurred for 108 squares.

Restricting attention to matrices whose [1,1] entry is 1 gives the following 12 first rows of circulant Latin squares having |determinant| 929587995:

[code][[1, 9, 8, 6, 2, 4, 3, 5, 7], [1, 9, 3, 5, 7, 6, 8, 4, 2], [1, 6, 9, 8, 3, 4, 5, 2, 7], [1, 4, 9, 3, 8, 5, 6, 7, 2], [1, 4, 6, 5, 9, 2, 8, 7, 3], [1, 5, 4, 6, 9, 7, 3, 2, 8], [1, 8, 2, 3, 7, 9, 6, 4, 5], [1, 3, 7, 8, 2, 9, 5, 6, 4], [1, 2, 7, 6, 5, 8, 3, 9, 4], [1, 7, 2, 5, 4, 3, 8, 9, 6], [1, 2, 4, 8, 6, 7, 5, 3, 9], [1, 7, 5, 3, 4, 2, 6, 8, 9]][/code]

So I guess 929587995 is the number to beat.

SmartMersenne 2019-11-11 23:32

I have 921437430

LaurV 2019-11-12 02:33

One could get better that that (caution! do not spoil it please!)

There is nowhere written that the numbers must be unique in rows and columns, like a sudoku grid. In theory, you can have a row full of twos (but of course, you can not have two rows which contain each the same digit, or linear combination, as in that case the determinant will be zero). They clearly formulated the problem saying that you must use each digit 9 times. If you like to put them in the same row or column, nobody stops you. Yo don't need to use one permutation in each row and column, etc.

I bet a lot of people will be put off by the formulation and will try to play with sudoku-style grids, but that is not required. The part related to Latin squares is strategically inserted (marketing :razz:).

Hint: pari is very good in solving determinants for you, if you do not want to dirty your hands with coding, but moving the stuff around in the matrix is quite slow in pari. We try an extremely simple "genetic" approach: where we fill the matrix initially, with 1 yo 9 in order in each row, then exchange two random elements in the matrix and keep the matrix with the largest determinant. Then repeat: switch, get determinant, switch, get determinant, till you get very very very old. It is quite easy to reach 9 digits, but very hard from there up...

yae9911 2019-11-12 04:09

The "marketing" is related to OEIS. A301371(9)=? A301371(8) beats the corresponding Latin square record.

@Dr. Sardonicus: Try to find the second largest determinant that can be achieved by circulant matrices. Since circulant matrices are indeed good candidates for large determinants, this gives an idea about the density of candidate values to be avoided. And OEIS A309259 provides a criterion for "other than those that can be achieved with Latin squares" (only necessary, not sufficient).
@Dieter and @a1call: You are too pessimistic w.r.t. "knowing which value can be achieved ...". The challenge team definitely has a (not too long) list.


All times are UTC. The time now is 13:41.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.