9
$\begingroup$

My previous puzzle asked for the maximum number of 4-point circles attainable from a configuration of $n=10$ points drawn on a plane. I am now interested in generalizations of this puzzle to arbitrary $n$.

I wrote a hill-climbing program that searches for configurations with integer coordinates. Here are the best solutions it has found so far:

$n=8$, 12 circles: (2,16) (10,20) (7,26) (12,6) (7,16) (12,11) (22,11) (16,14) enter image description here

$n=9$, 14 circles: (9,17) (8,18) (5,17) (6,16) (7,19) (7,15) (6,18) (7,17) (8,16) enter image description here

$n=11$, 30 circles: (5,27) (41,29) (29,37) (44,40) (35,33) (19,35) (35,7) (23,28) (35,37) (30,32) (17,19) enter image description here

$n=12$, 43 circles: (27,7) (33,5) (37,17) (27,47) (21,5) (32,7) (12,17) (27,22) (42,17) (27,2) (17,17) (22,7) enter image description here

Here are the questions I want answered:

  1. Can you improve any of these solutions? You can use either integer or non-integer coordinates.
  2. Can we construct any upper/lower bounds on the maximum number of circles possible for an arbitrary $n$?
  3. The solutions for $n$=8, 10 and 12 use two concentric polygons. Can we conjecture that for even $n \geq 8$ the best solution will use two concentric $(n/2)$-polygons?
  4. For $n=13$ my best solution uses 43 circles, which is exactly like the $n=12$ case. Surely that extra point must be useful for a few more circles?
$\endgroup$
7
  • 2
    $\begingroup$ The sequence for this problem has been finally published. Even Neil Sloane liked it! oeis.org/A337747 $\endgroup$ Oct 5, 2020 at 6:12
  • $\begingroup$ How do you verify that there're at most 14 circles for n=9 and 22 circles for n=10? $\endgroup$
    – Zhaohui Du
    Nov 14, 2022 at 7:32
  • $\begingroup$ A typical orchard planting problem requires that there're exact 3 trees in each row. So here it is required that each circle contains exact 4 points or circle with more than 4 points are almost counted? $\endgroup$
    – Zhaohui Du
    Nov 16, 2022 at 14:26
  • $\begingroup$ @ZhaohuiDu I used my hill climbing method to find the solutions, but I haven't verified that they are optimal. I suspect they are for n<=10. 3 points defined a circle, so that would be too easy, so here we require 4 points to be on a circle. $\endgroup$ Nov 17, 2022 at 5:36
  • 1
    $\begingroup$ You could have a try to use software Singular to verify it. I have verified that your result for n<=10 are optimal. github.com/emathgroup/selectedTopics/blob/master/content/… including all optimal result for n=9. $\endgroup$
    – Zhaohui Du
    Nov 17, 2022 at 23:33

5 Answers 5

6
$\begingroup$

A simple upper bound:

Since three points in the plane determine a circle any two distinct circles cannot have a triplet in common. We thus get an upper bound by counting all triplets and dividing by the number of triplets in a quadruplet $\left\lfloor\frac{\begin{pmatrix} n \\ 3 \end{pmatrix}}{\begin{pmatrix} 4 \\ 3 \end{pmatrix}}\right\rfloor=\left\lfloor\frac{\begin{pmatrix} n \\ 3 \end{pmatrix}}{4}\right\rfloor=\left\lfloor\frac{n(n-1)(n-2)}{24}\right\rfloor$

This evaluates to $n=7 \rightarrow 8;n=8 \rightarrow 14;n=9 \rightarrow 21;n=11 \rightarrow 41;n=12 \rightarrow 55$

A simple lower bound:

Construction: n even: 2 concentric parallel regular n/2-gons. This creates lots of trapezia with two points in either n/2-gon each permitting a circle. For n odd we can add the center point and use the same construction for n-1. IF (n-1)/2 is odd we can place the parallel sides of the (n-1)/2-gons opposite to each other and adjust the sizes of the two (n-1)/2-gons to create (n-1)/2 more circles all passing through the center, 2 points of the smaller (n-1)/2-gon and one point of the larger one. We can make a similar construction for (n-1)/2 even by rotating one (n-1)/2-gon so its corners align with the centers of the sides of the other. Also, note that if four points happen to be collinear we can still count them because we can use inversion in a circle centered at a point in general position to transform all such straight lines into proper circles.

Counting circles yields $2 + \frac {(n-1)[(n-1)(n-5)+16]} {32}$ for $n\equiv 1 \mod 4;n\ge9\ $,$\ 2 + \frac {(n-1)[(n-3)^2+16]} {32}$ for $n\equiv 3 \mod 4;n\ge11\ $,$\ 2 + \frac {n[(n-2)^2+4]} {32}$ for $n\equiv 0 \mod 4;n\ge8$ and $2 + \frac {n(n-2)^2} {32}$ for $n\equiv 2 \mod 4;n\ge10$

This evaluates to $n=8 \rightarrow 12;n=9 \rightarrow 14;n=11 \rightarrow 27;n=12 \rightarrow 41$

The lower bound constuction for $n=13$ beats OP by a single cirlce:

enter image description here The full configuration (bottom right panel) is obtained as 3 rotated overlays of the two templates (top right and bottom left panels, 6 circles each) plus the circumcircles of the two hexagons and six circles through the center (top left panel) for a total of 44.

Lower bound at $n=14$:

enter image description here The full configuration (right panel) is obtained as 7 rotated overlays of the template (left panel, 9 circles each) plus the circumcircles of the two heptagons for a total of 65.

$\endgroup$
7
  • $\begingroup$ This is excellent work Paul! Are you sure your lower bound is correct. For $n=14$ it gives me 65, but I can only find 57 so far. $\endgroup$ Sep 8, 2020 at 6:29
  • $\begingroup$ @DmitryKamenetsky Not 100% sure I did the counting right in every single case but $N=14$ seems correct, see updated answer. $\endgroup$ Sep 8, 2020 at 9:30
  • $\begingroup$ @PaulPanzer "2 concentric parallel regular n/2-gons": this does not work for multiples of 4. (unless you count 4 points on a row as a circle of infinite size). Some shifting as in the picture for 8 is needed, and it is not clear if this is possible for 12+. Or am I missing something? $\endgroup$
    – Retudin
    Sep 8, 2020 at 10:08
  • $\begingroup$ @Retudin That's what the "inversion in a circle centered at a point in general position" is for. It basically allows us to treat straight lines as circles. $\endgroup$ Sep 8, 2020 at 10:27
  • $\begingroup$ Ah yes your n=14 is correct. My program struggles to place heptagons on integer coordinates. $\endgroup$ Sep 9, 2020 at 22:17
3
$\begingroup$

14 trees with 73 circles (remove B or I to form a solution for 13 trees with 53 circles)

1:A=(-1.2208577248401677090604559983157963834, -3.1468480523080114886881271169977579250)
2:B=(-1.9478233124221029597568335446233091471, -1.9030657422906829627855358303024612249)
3:C=(-2.7527647907411112446780188831961624579, -3.5363463784316339145936381145450808675)
4:D=(-0.82783248947524419914841475107311902588, -0.80881034795529151745796572847987162035)
5:E=(0.73831734921240420520581932243142318234, 1.9030657422906829627855358303024612258)
6:F=(1,0)
7:G=(-1.8691742383633934665857228826763170467, 0)
8:H=(-1.5323609202837326010799277620171050618, -1.6348501262607572224466639246140796226)
9:I=(-1.9854399388298223415753940842379802469, -2.8132724283050665407238088353110992720)
10:J=(-2.2258288971159533487712352984471172569, -1.4274195298222514843054347812245927651)
11:K=(1.3430703308172535824813264335273661652, -2.4949510095897986824206185955346039503)
12:L=(-0.52723171215234560757205083333012202590, 0.97941058062225676502940186295657279032)
13:M=(0,0)
14:N=infinty

4 consecutive letters forms a circle, such as circle ABEG,ABHI, etc

ABEGABHIABJNABKMACDGACEFACHJACKNACLMADHKADIJADLNAEHLAEIKAEMNAFHMAFILAFJKAGHNAGIMAGJLBCDFBCHKBCIJBCLNBDHLBDIKBDMNBEHMBEILBEJKBFHNBFIMBFJLBGINBGJMBGKLCDHMCDILCDJKCEHNCEIMCEJLCFINCFJMCFKLCGHICGJNCGKMDEFGDEINDEJMDEKLDFHIDFJNDFKMDGHJDGKNDGLMEFHJEFKNEFLMEGHKEGIJEGLNFGHLFGIKFGMNHILNHJKNHJLMIJKMKLMN

c14

And another one with different parameters after circle inverse transformation where all black circles are same pattern as that in the bicenter regular polygons while red circles are extra circles. enter image description here

https://github.com/emathgroup/selectedTopics/blob/master/content/attached/files/c14.html is the geogebra version of it and you could change parameters (o,d and point NN) freedomly.

Similarly 15 trees could have 90 circles and 16 trees 120 circles: https://github.com/emathgroup/selectedTopics/blob/master/content/attached/files/c16.html

And it seems: if $n \equiv 0\pmod 4$, $\text{A337747}(n)=\frac{n((n-2)^2+ 4)}{32}+2×\text{A008610}(\frac{n}2-3)$ if $n \equiv 2\pmod 4$, $\text{A337747}(n)=\frac{n(n-2)^2}{32}+2×\text{A008610}(\frac{n}2-3)$

$\endgroup$
1
  • $\begingroup$ Excellent work! $\endgroup$ Dec 12, 2022 at 5:10
1
$\begingroup$

I rewrote my solver so it is smarter and can handle non-integer coordinates. I have managed to improve $n=12$:

I can get 45 circles with (1.551724138, 2.379310345) (3, 3) (-1, -1) (0, 1) (0.729729730, 1.378378378) (1.153846154, 1.769230769) (0.931034483, 2.172413793) (0.333333333, 1.666666666) (2.2, 1.4) (0.529411765, 0.882352941) (1.153846154, 0.230769231) (1.615384615, 1.923076923). I am not sure if this solution is possible with integer coordinates.

enter image description here

I also improved $n=13$:

I can get 47 circles. Surprisingly there is no obvious symmetry in this solution: (1.153846154,0.769230769) (3,4) (2.6,3.2) (2,1) (4.2,1.6) (1.551724138,1.379310345) (1,0) (3,2) (1,2) (3,1) (1.975609756,0.780487805) (2.846153846,1.230769231) (0.529411765,1.882352941)

enter image description here

I made a small improvement to $n=15$:

I can get 73 circles: (1.411764706, 1.352941176) (0.6, 2.2) (2.04, 0.72) (2.12, 0.84) (3.6, 0.2) (5, 1) (1.846153846, 0.769230769) (0.705882353, 1.823529412) (1.294117647, 1.176470588) (3.2, -0.4) (2, 1) (3, -2) (0.588235294, 1.647058824) (1.216216216, 1.297297297) (0.2, 1.6)

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Nice work! Interestingly, the cross ratios of any four of these points lying on a circle are still rational with small denominator. For your 13 point example (count ⨉ cross ratio): 4 ⨉ 1/13;13 ⨉ 1/4;10 ⨉ 5/13;3 ⨉ 4/13;4 ⨉ 3/16;1 ⨉ 4/9;1 ⨉ 5/32;1 ⨉ 1/9;3 ⨉ 3/8;2 ⨉ 1/40;2 ⨉ 1/16;2 ⨉ 1/25;2 ⨉ 2/5;2 ⨉ 1/3;1 ⨉ 1/2;2 ⨉ 1/5;2 ⨉ 1/6; The counts add to 55 because there are two circles with 5 points on them. This may vaguely explain why integers worked so well in the first place. For A,B,C,D to lie on a cirlce the cross ratios need to sum to one: (A,B;C,D) + (A,C:B,D) = 1. Seems easier for rationals. $\endgroup$ Sep 16, 2020 at 3:29
  • 1
    $\begingroup$ I wonder if one could directly base the search on cross ratios instead of coordinates? I also wonder whether Pythagorean triples have a role to play here since they help keeping distances rational which presumably makes it easier to get rational cross ratios. $\endgroup$ Sep 16, 2020 at 3:35
  • $\begingroup$ Also of note: Your new 12 point solution has superior structure compared to the two hexagon construction, because the two hexagons waste quite a few potential cirlces of four by collapsing them onto circles of six. Your solution only has circles of four. $\endgroup$ Sep 16, 2020 at 3:44
  • $\begingroup$ Interesting idea to search over cross ratios. I need to think about it. If I give you a set of cross ratios, are you able to reconstruct a solution? $\endgroup$ Sep 16, 2020 at 9:28
  • $\begingroup$ Not sure, for $n$ large enough just by counting degrees of freedom it should be possible in principle. I checked a tiny bit deeper: the cross ratios are all rational not because all distances are, but because lengths like $\sqrt 5$ are combined in such a way that the result is rational. $\endgroup$ Sep 16, 2020 at 16:48
1
$\begingroup$

For n=9, there're four groups of different solutions with 14 circles: One candidate is infinity point + (0,0), (1,0), (0.5, 1.3228756555322952952508078768196302129), (-0.25,0.66143782776614764762540393840981510643) (2.5,1.3228756555322952952508078768196302129), (-1,0), (-1.5,1.3228756555322952952508078768196302129), (-0.5,-1.3228756555322952952508078768196302129) where 1.3228756555322952952508078768196302129 is $\frac{\sqrt{7}}2$ enter image description here

All available solutions could be got from equations:

sd8/f484.7.out  
      _[1]=4d2-7  
      _[2]=k+1/2  
      _[3]=c-1/2  
      _[4]=b+d  
      _[5]=a-3/2  
sd8/f4041.7.out  
      _[1]=4d-1  
      _[2]=k+1/2  
      _[3]=c-1/2  
      _[4]=b+d  
      _[5]=a-3/4  
or  
      _[1]=4d+1  
      _[2]=k+1/2  
      _[3]=c-1/2  
      _[4]=b+d  
      _[5]=a-3/4  
sd8/f13492.7.out
      _[1]=16d2-7
      _[2]=k+1/2
      _[3]=c-1/4
      _[4]=b+d
      _[5]=a-1/4
sd8/f12577.7.out  
      _[1]=c4k2+2c2d2k2+d4k2+c4k+2c2d2k+d4k-2c3k2-2cd2k2-c2k3-d2k3+c4+2c2d2+d4-2c3k-2cd2k-2c2k2-2d2k2+2ck3-2c3-2cd2-c2k-d2k+4ck2+c2+d2+2ck  
      _[2]=-2c3dk4-2cd3k4-c2dk5+4bd2k5-d3k5+bk7-4c3dk3-4cd3k3+8bd2k4-4d3k4+2cdk5+2bk6-6c3dk2-6cd3k2+12bd2k3-8d3k3+6cdk4+bk5-dk5-4c3dk-4cd3k+3c2dk2+8bd2k2-9d3k2+10cdk3-dk4-2c3d-2cd3+2c2dk+4bd2k-6d3k+8cdk2+2c2d-2d3+4cdk  
      _[3]=2c3dk3+2cd3k3+c2dk4-4bd2k4+d3k4-bk6+4c3dk2+4cd3k2-8bd2k3+4d3k3-2cdk4-2bk5+4c3dk+4cd3k-c2dk2-8bd2k2+7d3k2-6cdk3+dk4+2c3d+2cd3-2c2dk-4bd2k+6d3k-8cdk2+bk3+dk3-c2d+3d3+2bck-4cdk-2bk2-dk2-2cd-2bk+2d  
      _[4]=c4dk+2c2d3k+d5k+2bc3k2+2bcd2k2-bc2k3-bd2k3+bc4+2bc2d2+bd4-4c3dk-4cd3k-4bc2k2-c2dk2-d3k2+bk4-2bc3-2bcd2-bc2k+4c2dk-bd2k+2bck2+2cdk2+bk3+bc2+bd2+2bck-bk2-dk2-bk+d  
      _[5]=c3k2+cd2k2+c2k3-2bdk3+d2k3+ak4+c3k+cd2k-2bdk2+2d2k2+ak3-2ck3-k4+c3+cd2-2bdk+2d2k-3ck2-k3-c2+d2-2ck  
      _[6]=c2dk+d3k+2bck2-bk3+bc2+bd2-2cdk-2bk2-bc+ad-bk+dk  
      _[7]=ack-c2k+bdk-d2k-ak2-c2-d2-ak+ck+k2+c+k  
      _[8]=c3k+cd2k+c2k2-2bdk2+d2k2+ak3+ac2+ad2-c2k+d2k-2ck2-k3-ac-bd-ak-ck+k  
      _[9]=a2k+b2k-c2-d2-2ak+2c+k  
      _[10]=a2c+b2c-ac2+c3-ad2+cd2+c2k-2bdk+d2k+ak2-a2-b2+ac-2c2+bd-ak-2ck-k2+c+k+1  

(I have thought there should be no real roots of the last equation, but in fact we could find infinity number of real roots).

For any solution of the above equations, We need to find a real projective transformation to transform complex point (a+bi, c+di) to infinity points (1:i:0),(1:-i:0).

The projective transformation will transform 8 points (0,0), (1,0),(0,1),((1+k)/k,1),(1,k+1), (1:0:0),(1:k:0),(0:1:0) into a result (Add an extra infinity point) For example, if k=-1/2;a=1,b=1,c=3/10,d=-1/10; The 8 points could be projected to (0,0),(1,0),(1,2),(9/5,12/5),(0,3),(-3,0),(3/2,3/2),(3/5,6/5)

I have verified that for n=9, there're at most 14 circles and for n=10, there're at most 22 circles too.

$\endgroup$
1
  • $\begingroup$ For n=11, there're at most 30 circles. One group of the solution for 30 circles are find real number a and t so that real number $b^2=\frac{((-4*a^3 + 20*a^2 - 32*a + 16)*t^2 + (2*a^3 - 10*a^2 + 16*a - 8)*t + (a^2 - 2*a + 1))}{((4*a - 4)*t^2 + (-2*a + 2)*t - 1)}$ $c=t,d=\frac{(2*b*c^2 - 2*b*c)}{-((2*a - 4)*c + 1)}$ Find the projective transformation to tranform (a+bi,c+di) to infinity point (1:i:0) and (a-bi,c-di) to infinity point (1:-i:0). $\endgroup$
    – Zhaohui Du
    Nov 22, 2022 at 8:26
1
$\begingroup$

For n=11, there're at most 30 circles. One group of the solution for 30 circles are find real number a and t so that real number $b^2=\frac{((-4*a^3 + 20*a^2 - 32*a + 16)*t^2 + (2*a^3 - 10*a^2 + 16*a - 8)*t + (a^2 - 2*a + 1))}{((4*a - 4)*t^2 + (-2*a + 2)*t - 1)}$ $c=t,d=\frac{(2*b*c^2 - 2*b*c)}{-((2*a - 4)*c + 1)}$ Find the projective transformation to tranform (a+bi,c+di) to infinity point (1:i:0) and (a-bi,c-di) to infinity point (1:-i:0). Apply the transformation above to 10 points

"list n1=1,0,0;\n"//A, 
"list n2=1,0,1;\n"//B
"list n3=(1-4t),2t(1-2t),(1-2t);\n"//C
"list n4=0,1,1;\n"//D
"list n5=0,0,1;\n"//E
"list n6=2,2t,1;\n"//F
"list n7=0,1,0;\n"//G
"list n8=2,2t-1,0;\n"//H
"list n9=2,2t-1,1;\n"//I
"list n10=1,t,1;\n";//J

and include infinity points we could get 11 points with 30 circles. (12 of them are straight lines) such as a=1/3, t=0.22,b=0.11908559882815065066807104006502303474,c=0.22, d=0.1532631656918298874098074285636846457 The matrix for the projective transformation is [-1 1.2739641311069882498453927025355596784 0] [0 -0.34620989492339901594966107566213561308 0] [-1.1938775510204081632653061224489795919 0.92764378478664192949907235621521335802 0.19387755102040816326530612244897959185] enter image description here

45 circles are also best result for 12 trees CGHLDEFLCFJLCEKLFHILEGILDGJLDHKLIJKLACILBDILBEJLBFKLAHJLAGKLABCDABEHABFGACEGACFHACJKADEKADFJADGHAEFIAGIJAHIKBCEFBCGJBCHKBDEGBDFHBDJKBEIKBFIJBGHICDEHCDFGCEIJCFIKDGIKDHIJEFGHEGJKFHJK

si[1]=bc-ad-bt-dt+b
si[2]=ac+c2+bd+d2-at-ct+a+t-1
si[3]=a2+b2-c2-d2+2at+2ct-2a-2t+1
si[4]=2c2d+2d3-4adt-4cdt-bt2-dt2+4ad+3bt+5dt-2b-2d
si[5]=2c3+2cd2-2c2t+4bdt+2d2t-at2-ct2-2c2-4bd-2d2+3at+5ct+t2-2a-2c-3t+2
si[6]=4b2dt+4bd2t-abt2+cdt2-bt3-dt3-4b2d+3abt+4adt+cdt+5bt2+2dt2-2ab-2ad-8bt-3dt+4b
si[7]=4abdt+4ad2t+b2t2+4bdt2+3d2t2-4abd-3b2t-8bdt-d2t+2b2+2bd
ring r1=0,(a,b,c,d,t),dp;
list n1=1,1,1;
list n2=-1/2*t + 1/2,1/2*t,1;
list n3=0,1,0;
list n4=-t,t,1;
list n5=-t + 1,t - 1,1;
list n6=0,0,1;
list n7=t,-t + 1,0;
list n8=1,0,0;
list n9=1,0,1;
list n10=0,1,1;
list n11=-t + 1,t,1;

enter image description here and Geogebra dynamic graph for it at https://github.com/emathgroup/selectedTopics/blob/master/content/attached/files/c12.ggb

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.