Allgemeines Obstgartenpflanzproblem für Kreise

Question

In meinem vorherigen Puzzle wurde nach der maximalen Anzahl von 4-Punkt-Kreisen gefragt, die mit einer Konfiguration von erreichbar sind$n=10$Punkte in einer Ebene gezeichnet. Ich interessiere mich jetzt für Verallgemeinerungen dieses Puzzles auf willkürlich$n$.

Ich habe ein Bergsteigerprogramm geschrieben, das nach Konfigurationen mit ganzzahligen Koordinaten sucht. Hier sind die besten Lösungen, die es bisher gefunden hat:

$n=8$12 Kreise: (2,16) (10,20) (7,26) (12,6) (7,16) (12,11) (22,11) (16,14)

$n=9$14 Kreise: (9,17) (8,18) (5,17) (6,16) (7,19) (7,15) (6,18) (7,17) (8,16)

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

$n=12$43 Kreise: (27,7) (33,5) (37,17) (27,47) (21,5) (32,7) (12,17) (27,22) (42,17) ( 27,2) (17,17) (22,7)

Hier sind die Fragen, die ich beantwortet haben möchte:

1. Können Sie eine dieser Lösungen verbessern? Sie können entweder ganzzahlige oder nicht ganzzahlige Koordinaten verwenden.
2. Können wir Ober- / Untergrenzen für die maximal mögliche Anzahl von Kreisen für eine beliebige Anzahl konstruieren? $n$?
3. Die Lösungen für $n$= 8, 10 und 12 verwenden zwei konzentrische Polygone. Können wir das überhaupt vermuten?$n \geq 8$ Die beste Lösung verwendet zwei konzentrische $(n/2)$-Polygone?
4. Zum $n=13$ Meine beste Lösung verwendet 43 Kreise, genau wie die $n=12$Fall. Sicherlich muss dieser zusätzliche Punkt für ein paar weitere Kreise nützlich sein?

Answer 1

Eine einfache Obergrenze:

Da drei Punkte in der Ebene einen Kreis bestimmen, können zwei unterschiedliche Kreise kein Triplett gemeinsam haben. Wir erhalten also eine Obergrenze, indem wir alle Tripletts zählen und durch die Anzahl der Tripletts in einem Quadruplett dividieren$\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$

Dies ergibt zu $n=7 \rightarrow 8;n=8 \rightarrow 14;n=9 \rightarrow 21;n=11 \rightarrow 41;n=12 \rightarrow 55$

Eine einfache Untergrenze:

Konstruktion: n gerade: 2 konzentrische parallele reguläre n / 2-Gons. Dies erzeugt viel Trapez mit zwei Punkten in entweder n / 2-Gon, die jeweils einen Kreis zulassen. Für n ungerade können wir den Mittelpunkt hinzufügen und dieselbe Konstruktion für n-1 verwenden. WENN (n-1) / 2 ungerade ist, können wir die parallelen Seiten der (n-1) / 2-Gons einander gegenüberstellen und die Größe der beiden (n-1) / 2-Gons anpassen, um ( n-1) / 2 weitere Kreise, die alle durch die Mitte verlaufen, 2 Punkte des kleineren (n-1) / 2-Gon und ein Punkt des größeren. Wir können eine ähnliche Konstruktion für (n-1) / 2 herstellen, indem wir einen (n-1) / 2-Gon so drehen, dass seine Ecken mit den Mittelpunkten der Seiten des anderen ausgerichtet sind. Beachten Sie auch, dass wenn vier Punkte kollinear sind, wir sie trotzdem zählen können, da wir die Inversion in einem Kreis verwenden können, der an einem Punkt in der allgemeinen Position zentriert ist, um alle diese geraden Linien in richtige Kreise umzuwandeln.

Kreise zählen ergibt $2 + \frac {(n-1)[(n-1)(n-5)+16]} {32}$ zum $n\equiv 1 \mod 4;n\ge9\ $,$\ 2 + \frac {(n-1)[(n-3)^2+16]} {32}$ zum $n\equiv 3 \mod 4;n\ge11\ $,$\ 2 + \frac {n[(n-2)^2+4]} {32}$ zum $n\equiv 0 \mod 4;n\ge8$ und $2 + \frac {n(n-2)^2} {32}$ zum $n\equiv 2 \mod 4;n\ge10$

Dies ergibt zu $n=8 \rightarrow 12;n=9 \rightarrow 14;n=11 \rightarrow 27;n=12 \rightarrow 41$

Die untere Grenzkonstruktion für $n=13$ schlägt OP mit einem einzigen Cirlce:

Die vollständige Konfiguration (untere rechte Tafel) wird als 3 gedrehte Überlagerungen der beiden Schablonen (obere rechte und untere linke Tafel, jeweils 6 Kreise) plus die Kreise der beiden Sechsecke und sechs Kreise durch die Mitte (obere linke Tafel) für a erhalten insgesamt 44.

Untergrenze bei $n=14$::

Die vollständige Konfiguration (rechtes Feld) wird als 7 gedrehte Überlagerungen der Schablone (linkes Feld, jeweils 9 Kreise) plus die Kreise der beiden Heptagone für insgesamt 65 erhalten.

Answer 2

Ich habe meinen Solver neu geschrieben, damit er intelligenter ist und nicht ganzzahlige Koordinaten verarbeiten kann. Ich habe es geschafft, mich zu verbessern$n=12$::

Ich kann 45 Kreise mit (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,666666) erhalten 1,4) (0,529411765, 0,882352941) (1,153846154, 0,230769231) (1,615384615, 1,923076923). Ich bin nicht sicher, ob diese Lösung mit ganzzahligen Koordinaten möglich ist.

Ich habe mich auch verbessert $n=13$::

Ich kann 47 Kreise bekommen. Überraschenderweise gibt es in dieser Lösung keine offensichtliche Symmetrie: (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)

Ich habe eine kleine Verbesserung gemacht $n=15$::

Ich kann 73 Kreise erhalten: (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.1764788) ) (3,2, -0,4) (2, 1) (3, -2) (0,588235294, 1,647058824) (1,216216216, 1,297297297) (0,2, 1,6)