Return to Answer

• 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}}.$ 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.

• 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}}.$ 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.

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

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.

UPDATED AGAIN Here are some lower bounds and the results of $10^6$ random trials. The $1$-dimensional case is quite informative and is discussed at the end.

One way to get an exponential 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 such bounds which are increasingly good. However an exponential model is not the right one to use.

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

$$[1, 1000000], [2, 812791], [3, 580116], [4, 376623], [5, 228824], [6, 131445],$$$$ [7, 72077], [8, 38186], [9, 19805], [10, 10009], [11, 4852], [12, 2299],$$$$ [13, 1070], [14, 540], [15, 259], [16, 113], [17, 47], [18, 18], [19, 4]$$

As suggested by Emil, the correct model is possibly of the form $f(n) c^n$ for some $f(n)$ with sub-exponential growth. This is supported by the following:

Consider the similar problem in $1$-dimension:

The interval $[0,1]$ is divided into $n+1$ subintervals by $n$ random points. What is the probability that the longest subinterval has length at least $\frac12?$

It turns out that the exact answer is $\frac{n+1}{2^n}.$ It is easiest to prove the more general form: Given that the largest currently surviving interval has length $\frac12+x,$ the probability of surviving the next $n$ random points is $$\frac{n(2x-1)+1}{2^n}.$$

Given this exact result, we don't need an upper bound. But getting one helped me understand Christian's method: I claim that an upper bound, valid for all $n$ is $$N\left(\frac12+\frac1N\right)^n.$$ Fix an integer $N>2$ and consider the $N$ intervals $I_t=[\frac{t}{2N},\frac{t}{2N}+\frac{N-1}{2N}]$ with $1 \leq t \leq N.$ A subinterval $[s,s+\frac12]$ contains one of these (move each endpoint inward to the nearest $\frac{a}{2n}.$) If some interval of length $\frac12$ stays undivided, so does at least one of the $I_t.$ The chance that any particular one stays undivided by $n$ random points is $(\frac12+\frac1N)^n.$ So the chance that at least one does is less than $N\left(\frac12+\frac1N\right)^n.$ This is an upper bound on what we seek.

Here are some lower bounds including a wild speculation that the correct value for largish $n$ might be roughly $0.35^n.$

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 the $n$ lines cut the tilted square is $1/(6^n).$

This can be improved to $4/(6^n)=2/(3\cdot 6^{n-1})$ as follows. 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.$

If I did a randomized experiment correctly then a lower bound of about $0.34^n$ results from looking at the chance that that all $n$ lines miss the circle of radius $1/\sqrt{2\pi}$ centered at $(1/2,1/2).$

LATER Here is a somewhat less good lower bound, included since I previously neglected to divide by $3$ and thought it was an improvement. I also forgot to multiply by $2.$

If I calculated correctly, 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).$

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

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}}.$ 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.