6

The classic Orchard planting problem asks for the maximum number of 3-point straight lines attainable from a configuration of $n$ points drawn on a plane.

Here we are interested in a variant of this problem. What is the maximum number of 4-point circles attainable from a configuration of 10 points drawn on a plane? Each attained circle must pass through at least 4 points.

Dmitry Kamenetsky
  • 35,897
  • 5
  • 66
  • 276
  • 3
    For a lower bound, you can take a solution to the 9-point linear orchard planting problem, add the point at infinity, and apply a Möbius transformation on the whole thing to turn all the lines into circles. So that gives you 10 by itself, and it seems that you can wiggle some points around in the original solution to make more circles (which remain circles when Möbius-transformed). – Deusovi Aug 31 '20 at 05:41
  • Wow I didn't even think of that. Brilliant! – Dmitry Kamenetsky Aug 31 '20 at 05:45
  • The Wolfram's page you linked contains a table which says that for n=10 points and required k=4 points in a line one can achieve up to 5 lines. So at least 5 circles are possible. – CiaPan Aug 31 '20 at 08:06
  • Since mapping any point into infinity point could transform all circles passing through it into lines. So we could get that number of circles passing through this point to be no more than the result of 9-point linear orchard plating problem (that's 10). So repeat it for all points, we could get the total numbers of circle could be no more than 10*10/4=25 (since each circle is counted 4 times). – Zhaohui Du Nov 07 '22 at 01:35
  • Maybe it also means that we could always start from some optimal (n-1)-points linear orchard planting problem, and try to find how much more circles could be found in it. – Zhaohui Du Nov 07 '22 at 01:37
  • @ZhaohuiDu some very interesting comments. Also have a look at these: https://puzzling.stackexchange.com/questions/101945/general-orchard-planting-problem-for-circles https://oeis.org/A337747 – Dmitry Kamenetsky Nov 08 '22 at 02:16

3 Answers3

8

I can do

$22$: enter image description here

Less aesthetically pleasing but more revealing version

above version was obtained from this by inversion in a circle enter image description here

or

enter image description here

The construction is as follows: two concentric regular pentagons: This gives $2$ circumscribed circles and $5\times 2 \times 2$ symmetric trapezoids each admitting a circumcircle by symmetry.

Here is a less busy picture---the full is obtained bv overlaying successive rotations by $72°$ and by adding the two circumcircles of the two pentagons. enter image description here

Paul Panzer
  • 10,341
  • 18
  • 48
  • 2
    That is amazing. +1 – Jaap Scherphuis Aug 31 '20 at 19:23
  • 2
    I find it interesting that the sizes of the pentagons don't seem to matter so long as they're concentric. Any two parallel edges have four points that form an isosceles trapezium, which is always inscribable within a circle. Very cool indeed. – Ian MacDonald Aug 31 '20 at 20:38
  • This is very cool! What would happen if we used two concentric quadrilaterals and two extra points on the outside? – Dmitry Kamenetsky Sep 01 '20 at 01:13
  • I think this nice pattern can be extended to larger $n$. – Dmitry Kamenetsky Sep 01 '20 at 01:29
  • @DmitryKamenetsky My gut feeling would be that even-laterals are generally not as efficient because they are used up after a half turn while odd-laterals give distinct trapezoids for every $2\pi/n$ turn. – Paul Panzer Sep 01 '20 at 04:00
  • 1
    @DmitryKamenetsky Yep, if I'm not mistaken multiples of $5$ should do nicely: $15\rightarrow 63,20\rightarrow 124\ldots$ – Paul Panzer Sep 01 '20 at 04:11
  • 1
    @DmitryKamenetsky Wait, probably you can squeeze out extra circles by chosing the pentagon radii correctly! I'd guess at least another $5$ for $15$ and another $10$ for $20$. – Paul Panzer Sep 01 '20 at 04:26
  • 1
    @PaulPanzer sounds like this would make a great integer sequence. I'll try to write a program that finds these point placements. – Dmitry Kamenetsky Sep 01 '20 at 04:27
  • I wrote a program that searches for solutions with integer coordinates. The best I found was a solution that is similar to yours. So it may be optimal. – Dmitry Kamenetsky Sep 04 '20 at 07:09
  • @DmitryKamenetsky Interesting that the additional integer constraint doesn't seem to kill soslutions. Did you also try other n? – Paul Panzer Sep 04 '20 at 07:19
  • Yes. I got 14 for n=9, 12 for n=8 and 6 for n=7. I didn't try n>10 yet. Does this match your results? – Dmitry Kamenetsky Sep 04 '20 at 07:31
  • Note that it is impossible to make a regular pentagon with integer coordinates. But I found a solution with two non-regular pentagons. – Dmitry Kamenetsky Sep 04 '20 at 07:33
  • @DmitryKamenetsky I didn't really try any other numbers. Perhaps the non-regulat pentagons are in fact mappable (via inversion in a circle or similar) to regular ones (like the ones in my first figure). You could check whether they are inscribed in a circle and whether the cross ratios of any four points equal !. – Paul Panzer Sep 04 '20 at 07:42
  • I ran my code for larger n. I got 30 circles for n=11 and 43 circles for n=12. The fascinating thing is that for n=12 the solution is two concentric hexagons. For n=8 the best solution is two concentric quadrilaterals. So perhaps for even n, the best solution is to use two concentric (n/2)-polygons. – Dmitry Kamenetsky Sep 07 '20 at 01:20
  • 1
    @DmitryKamenetsky Wow, that's indeed fascinating. I'd be interested in seeing these solutions. Would you mind making another question? Maybe you could ask for bounds for any n or something like that. Or I can do that if you feel it's more appropriate. – Paul Panzer Sep 07 '20 at 01:58
  • @PaulPanzer I am happy to ask a general question, but I feel it will be better suited for Maths StackExchange. What do you think? I am also happy for you to ask any question related to this problem. – Dmitry Kamenetsky Sep 07 '20 at 05:11
  • @DmitryKamenetsky Go ahead! I'm fine with anything as long as you sneak in a picture or two of your simulation results :-) – Paul Panzer Sep 07 '20 at 08:44
  • @PaulPanzer done! Check it out: https://puzzling.stackexchange.com/questions/101945/general-orchard-planting-problem-for-circles – Dmitry Kamenetsky Sep 08 '20 at 01:22
5

The following answer follows the excellent idea by Deusovi in a comment to the question.

Start with a solution to the original 9-tree orchard problem, with 10 lines of 3 trees.

Then add the point at infinity to get 10 points, and 10 lines with 4 points on them, and use a Möbius transformation to change them all to circles with 4 points on them.
In particular, I used points at the following coordinates:
$$\begin{array}{|c|c|c|} \hline Point & Original & Transformed \\ \hline A & \infty & (0,0) \\ \hline B & (1,2) & (1/5,-2/5) \\ \hline C & (2,2) & (1/4, -1/4) \\ \hline D & (3,2) & (3/13,-2/13) \\ \hline E & (0,1) & (0,-1) \\ \hline F & (2,1) & (2/5,-1/5) \\ \hline G & (4,1) & (4/17,-1/17) \\ \hline H & (0,3) & (0,-1/3) \\ \hline I & (2,3) & (2/13,-3/13) \\ \hline J & (4,3) & (4/25,-3/25) \\ \hline \end{array}$$
The last column is the new coordinate after the $z \to 1/z$ transformation of the complex plane, which in cartesian coordinates is the map $(x,y) \to (x/s,-y/s)$ where $s=x^2+y^2$.

The original ten lines then become the ten circles ABCD, AEFG, AHIJ, AHBF, AHCG, AIBE, AICF, AIDG, AJCE, AJDF. I chose the original points such that no line goes through the origin, ensuring that after the transform they are circles rather than straight lines (the origin maps to the point at infinity, and would be contained on any straight line).

The original arrangement also has the circles BDEG, DBHJ, BDIF, EFHI, FGIJ, EGHJ, and they remain circles after the transformation, for a total of 16 circles.

enter image description here

Jaap Scherphuis
  • 53,019
  • 7
  • 120
  • 208
1

I found

Two more solutions that produce 22 circles, but have a very different structure to the one found earlier.

(2.8,2.4) (3,1) (4,4) (3,2) (1.5,1.5) (3.411764706,1.647058824) (2.333333333,2.333333333) (2,0) (1.692307692,2.461538462) (2.461538462,1.692307692) enter image description here

(3.076923077,2.384615385) (2.068965517,2.172413793) (0.8,1.4) (0,7) (2.702702703,3.216216216) (2,1) (1.176470588,2.294117647) (1.333333333,3) (2,3) (3.529411765,1.117647059) enter image description here

Dmitry Kamenetsky
  • 35,897
  • 5
  • 66
  • 276
  • 1
    They are indeed different from mine, but I'm not sure they are different from each other. Cross ratios are the same for both: 14 ⨉ 1/2;8 ⨉ 1/5 (my solution has nonrational Cross ratios which come in two groups of 10 and two groups of 5) – Paul Panzer Sep 16 '20 at 05:05