A277433 Minimal No-3-in-line

[Ed Pegg]

https://oeis.org/A277433  

14x14 <= 12 
{{0, 0}, {0, 13}, {3, 6}, {3, 7}, {6, 3}, {6, 10}, {7, 3}, {7,10}, {10, 6}, {10, 7}, {13, 0}, {13, 13}}
◆◇◇◇◇◇◇◇◇◇◇◇◇◆
◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◆◆◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◆◇◇◇◇◇◇◆◇◇◇
◇◇◇◆◇◇◇◇◇◇◆◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◆◆◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◆◇◇◇◇◇◇◇◇◇◇◇◇◆

19x19<=16  

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◆◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇◇◇
◇◇◇◇◇◇◆◇◇◇◇◇◆◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◆◇◇◇◇◇◇◇◆◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◆◇◇◇◇◇◆◇◇◇◇◇◇
◇◇◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◆◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

24x24 <= 20

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◆◇◇◇◇◆◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◆◇◇◆◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◆◇◇◆◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◆◇◇◇◇◆◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

[Ed Pegg]

Someone asked earlier if a comment could be added to a sequence. 
https://oeis.org/A005408  The odd numbers.  
Falstaff: "They say there is divinity in odd numbers, either in nativity, chance, or death." Shakespeare, The Merry Wives of Windsor (Act 5, Scene 1).

https://oeis.org/A277433  Martin Gardner's minimal no-3-in-a-line problem, all slopes version.

1, 4, 4, 4, 6, 6, 8, 8, 8, 8, 10, 10, 12, 12, 14, 15, 16, 16, 16, 18, 20, 20, 20, 20, 22, 24, 24, 24, 24, 28   

These are at least upper bounds.  I'll pay $20 to anyone that can improve any of the solutions under size 30. 

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/18b339aa-dfd6-4f07-9946-b8b94869b4ban%40googlegroups.com.

[Ed Pegg]

I've put a write-up and interactive code at 
https://community.wolfram.com/groups/-/m/t/3740214  
along with 101 solutions I've compiled.

[Neil Sloane]

Hi Ed!

>  I've put a write-up and interactive code at 

https://community.wolfram.com/groups/-/m/t/3740214  
along with 101 solutions I've compiled.

Please don't forget to add a link to your write-up to the entry A277433 (assuming that is the best place for it)!

Best regards

Neil 

Neil J. A. Sloane, Chairman, OEIS Foundation.

Also Visiting Scientist, Math. Dept., Rutgers University, 

Email: njas...@gmail.com

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAGog0%2Bbm97%3D63DvA%2Baf%3DmAyCCnuAN1PtMfQBqo-q7jSaCH71fQ%40mail.gmail.com.

[Ed Pegg]

Thanks, Neil.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAAOnSgSqdV_OtCE1LcT_P7c-k_RH36mwJtHBKJG8UG%2BZs46nyw%40mail.gmail.com.

[Ed Pegg]

I believe there's a not-too-bad proof of a(12)=10, because it's difficult to get coverage of 144 points with 9 points.  If the number of orthogonal lines isn't maximized, coverage seems impossible. Enumerating all the alternating orthogonal chains isn't too bad up to 8-chains. Unfortunately, this method only seems useful for a(12).

orth4[n_]  := Binomial[n, 2]^2
orth6[n_]  := 6 Binomial[n, 3]^2
orth8[n_]  := 72 Binomial[n, 4]^2
orth10[n_] := 1440 Binomial[n, 5]^2
orth[2 k_][n_] := (k! (k - 1)!/2) Binomial[n, k]^2   

orth6[12]  =     290,400
orth8[12]  =     17,641,800
orth10[12] =    903,260,160

[Ed Pegg]

A curiosity ... 15x15 can be covered with 13 points so that adding another point will produce 3-in-a-line ... but it has two 3-in-a-line.    

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◆◇◆◇◇◇◇◇◇◇
◇◇◇◇◇◇◆◇◇◆◇◇◇◇◇
◇◇◇◇◆◇◇◇◆◇◇◇◇◇◇
◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇
◇◇◆◇◆◇◇◆◇◇◇◇◇◇◇
◇◇◇◇◇◇◆◇◆◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

[Ed Pegg]

Dmitry Kamenetsky supplied improvements for a(16), a(17) and a(21).

[Ed Pegg]

I just learned of https://arxiv.org/pdf/2203.13170  

Geometric Dominating Sets
Oswin Aichholzer, David Eppstein, Eva-Maria Hainzl  

  n 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
In  12 12 14 14 15 16 16 16 16 18 20 20 22 24 24 24 24 25  

I wasn't too far off.  I need to make another update. 
n = 20: 18 -> 16
n = 21: 19 -> 16
n = 22: 20 -> 18
n = 30: 28 -> 25

[Ed Pegg]

I thought this would be easy. Easy! I've put in another hack at it.  
https://oeis.org/A277433  
https://arxiv.org/abs/2203.13170  
https://community.wolfram.com/groups/-/m/t/3740214