mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-11-07, 13:13   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2×3×5×257 Posts
Default November 2019

http://www.research.ibm.com/haifa/po...ember2019.html
Xyzzy is offline   Reply With Quote
Old 2019-11-10, 09:09   #2
Dieter
 
Oct 2017

89 Posts
Default

„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.
Dieter is offline   Reply With Quote
Old 2019-11-10, 09:31   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

76A16 Posts
Default

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
http://mathworld.wolfram.com/LatinSquare.html

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

Last fiddled with by a1call on 2019-11-10 at 09:38
a1call is offline   Reply With Quote
Old 2019-11-10, 09:58   #4
Dieter
 
Oct 2017

89 Posts
Default

Quote:
Originally Posted by a1call View Post
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
http://mathworld.wolfram.com/LatinSquare.html

And I could not find the known record value by googling which is the value to bit for double astrics.
I have googled 929587995
Dieter is offline   Reply With Quote
Old 2019-11-10, 10:00   #5
Dieter
 
Oct 2017

89 Posts
Default

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
Dieter is offline   Reply With Quote
Old 2019-11-10, 10:59   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

111011010102 Posts
Default

Acknowledged with thanks and kudos on you search capabilities.
a1call is offline   Reply With Quote
Old 2019-11-10, 16:51   #7
uau
 
Jan 2017

7410 Posts
Default

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
That is, just 9 rotated copies of the same row (or column).
uau is offline   Reply With Quote
Old 2019-11-11, 15:58   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·5·233 Posts
Default

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]]
So I guess 929587995 is the number to beat.

Last fiddled with by Dr Sardonicus on 2019-11-11 at 16:01 Reason: Add code tags
Dr Sardonicus is offline   Reply With Quote
Old 2019-11-11, 23:32   #9
SmartMersenne
 
Sep 2017

7·11 Posts
Default

I have 921437430
SmartMersenne is offline   Reply With Quote
Old 2019-11-12, 02:33   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

19×461 Posts
Default

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 ).

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...

Last fiddled with by LaurV on 2019-11-12 at 02:41
LaurV is offline   Reply With Quote
Old 2019-11-12, 04:09   #11
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

31 Posts
Default

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.
yae9911 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
November 2018 Batalov Puzzles 5 2018-12-03 13:31
November 2017 Batalov Puzzles 3 2017-12-08 14:55
November 2016 Xyzzy Puzzles 1 2016-12-06 16:41
November 2015 R. Gerbicz Puzzles 3 2015-12-01 17:48
November 2014 Xyzzy Puzzles 1 2014-12-02 17:40

All times are UTC. The time now is 16:34.

Wed Sep 30 16:34:26 UTC 2020 up 20 days, 13:45, 0 users, load averages: 1.60, 1.81, 1.81

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.