Skip to main content
5 of 7
added 1479 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

UPDATED Here are some lower bounds and the results of $10000$ random trials.

One way to get a lower bound is to choose an area $1/2$ subset and find the chance that it remains intact after $n$ lines. A tilted square, the intact isosceles right triangle after the first line (if there is one), an optimal octagon and centered circle (in that order) give bounds which are increasingly good. However they may all be far from optimal

  • The chance that a single line avoids the tilted square with corners $(1/2,0),(1,1/2),(1/2,1),(0,1/2)$ (of area $1/2$) is $1/6:$ With probability $1$, the point first chosen is not a corner of the original square or the tilted one. wlog it is on the left half of the bottom. Then the second point needs to be on the lower half of the right side. The chance of this is 1/6. So the chance that none of $n$ lines cut the tilted square is $$\frac1{6^{n}}.$$

  • This can be improved to $$\frac4{6^n}=\frac2{3\cdot 6^{n-1}}$$ by considering instead isosceles right triangles. The chance that the first line crosses two adjacent sides is $2/3.$ If this does happen then one of the diagonals misses this line and splits the square into two isosceles right triangles with area $1/2.$ One is cut and the other intact. For every subsequent choice the first point is outside the intact half with probability $1/2$ and the second with probability $1/3.$

  • Here is a certain octagon along with the circle with center $(\frac12,\frac12)$ and radius $\frac1{\sqrt{2\pi}}.$ enter image description here I find that the octagon above is the best of its kind. I get that the probability it stays intact is about $$(\frac{2(0.4797667)}3)^n=0.31984^n.$$ The lower left corner is at about $(0.32606,0.11670).$

  • For the octagon, and also the circle, the exact probability of a line missing it can, in principle, be found using several integrals. They are not that nice so I evaluated them numerically. The probability of a line missing the circle is about $.34470989$ hence $$0.34470989^n.$$

Perhaps some shape of the form $t$circle+$(1-t)$octagon beats the circle. However another octagon might do even better for that process.


It is not all that hard to randomly generate lines. One need only keep track of the vertices of the one maximum area region. Then a new line either misses it or intersects two of the sides creating two new vertices and two regions.

In $10,000$ random trials it happened $4$ times that only the $17$th line left all regions with size less than $\frac12.$ Of course the first line is always OK. $1896$ times the second line was fatal, the other $8104$ it wasn't. The counts were

$$[1, 10000], [2, 8104], [3, 5696], [4, 3632], [5, 2172], [5, 1239], [7, 672], [8, 356], [9, 190], [10, 99], [11, 53], [12, 25], [13, 12], [13, 8], [15, 5], [16, 4]$$

In trying for an exponential fit it seems wise to use $m$, the number of lines after the first one. the best exponential fit to the observed probability of surviving $m+1$ lines at least is

$$1.6885 \left( 0.56313^m\right).$$ Here is a plot of that function along with the observed probabilities.

enter image description here

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104