Dividing Mr. Once-ler's Estate [solution - kinda]

Solution for the week of 5/04

Our puzzle last week had us figuring out how to protect our inherited Truffula forest.

You and your three siblings are at the reading of the will for your late father—a wealthy outdoorsman—that owned a forest of very rare and valuable trees known as Truffula trees. The Truffula forest has a single clear center, and from that center outward, the density of trees drops by 50% for every kilometer you travel outward.

In his will, your father decides to split the forest evenly between you and your three siblings by creating 4 equal quadrants emanating from the center of the forest

Each sibling has very different intentions for their forest so you all agree to the creation of a fence that will section off each sibling’s quadrant. For your quadrant, you also want to make to keep the Truffula trees protected so you decide to create a fence around the outside of your quadrant (something like a circumference). To minimize fencing costs, you plan to stretch the fence snugly around just the trees at the forest’s outer edge, keeping all other trees safely within the boundary (see the red line). To actually build this fence, you'll need special posts every time the fence changes direction around these outermost trees. You also find that your section of the forest has 1000 trees.

The question for this week is, on average, how many fence posts will you need?

Thanks to solvers

Izumihara Ryoma

and Vamshi for your submissions. Some readers may have recognized this problem as a relatively well known problem in algorithms—computing the convex hull over a set of point. A convex hull refers to the convex polygon drawn over a set of points such that it covers all of them with minimum area.

Those that attempted this problem may also have found it rather messy mathematically. That’s because I made a mistake. I meant for the problem to be a bit easier but in translating the intended problem into a “story” format, I accidentally introduced a gnarly complexity. The problem was originally supposed to have the x-coordinate and y-coordinate be independent so we could make some simpler arguments about how the set of Pareto dominant points converges on the number of points in the outer hull as the number of trees gets large. But the tree description I provided with it’s radial symmetry most certainly doest not have x-y independence. Honestly, a similar argument might be workable but it’s much less obvious to me.

Being that this mistake caught me a bit off guard, I didn’t have as much time to work on a solution as I would have liked. I came up with the solution below but the answer it yields is different to what my simulations suggest, indicating the solution is probably wrong. In fact, solver

Izumihara Ryoma

’s solution get’s closer to the simulated values I found and he’s a sharp fellow so his solution is much more likely the correct one. I present my solution as well just in case it spurs any thoughts or if anyone can spot an error (which likely exists).

The Best Answer We Have…

Check out Izumihara’s solution here.

My [Probably Wrong] Solution…

How do we construct the convex hull? For the most part, we just need one reasonably simple observation. A line is part of the convex hull if all the points we are trying to cover lie on one side of the line. In the case we’re consider where all the points are in the upper right quadrant, this simplifies to all the points being “less” than a line on the outer hull. Let’s say point A and B make up this line. They have coordinates r_A, θ_A, r_B, and θ_B . The line they form is given by

\(r(\theta) =\frac{r_A\sin(\theta_B-\theta)+r_B\sin(\theta-\theta_A)} {\sin(\theta_B-\theta_A)}\)

Also, before we progress much further, we should describe the distribution of trees in the quadrant

\(f_{R,\Theta}(r,\theta)= \frac{2 \ln 2}{\pi} \cdot 2^{-r} \qquad r \in [0,\infty),\; \theta \in \left[0,\tfrac{\pi}{2}\right]\)

There are n-2 points that remain that need to be less than the line r(θ). The probability of any one of these points being greater than the line is

\(p_{AB} \;=\; \frac{2\ln 2}{\pi} \int_{\theta_A}^{\theta_B} \! \int_{r(\theta)}^{\infty} 2^{-r}\,dr\,d\theta \;=\; \frac{2}{\pi} \int_{\theta_A}^{\theta_B} 2^{-r(\theta)}\,d\theta \)

As such, the probability of all of the points be less than line AB is

\(p_{n|AB} = (1-p_{AB})^{(n-2)}\)

Now recall that

\(p_{n|AB} = \Pr[\text{all points $<\overline{AB}$} | A,B]\)

is a conditional probability. So we’ll need to compute the marginal with respect to A and B.

\(p_{n} \;=\; \int \int \int \int p_{n|AB} \;f_{R,\Theta}(r_A,\theta_A)\,f_{R,\Theta}(r_B,\theta_B)\; dr_A dr_B d\theta_A\,d\theta_B\)

We also need to consider that fact that there are (n choose 2) possible choices for A and B. Putting this together we get

\(E[H_n] = \binom{n}{2} p_n\)

Where H_n is the number of vertices in the outer hull. That leaves us with this monstrosity.

\(\begin{align*} E[M_n] \;=\; &\frac{n(n-1)}{2} \left(\frac{2\ln2}{\pi}\right)^{\!2} \\ &\int_{0}^{\pi/2} \int_{0}^{\theta_{B}} \int_{0}^{\infty} \int_{0}^{\infty} \bigl[1-p_{A,B}\bigr]^{\,n-2} \;2^{-r_{A}}\,2^{-r_{B}}\; dr_{A}\,dr_{B}\,d\theta_{A}\,d\theta_{B} \end{align*} \)

Now there are some simplifications we can make to this expression but I don’t this even yields the correct answer so I won’t bother here. The computational evaluation of this integral gives 4.8031 fence posts. This is a bit high compared to Izumihara’s 3.02 solution and my own simulation results which yielded 2.82 (turns out even simulating this problem isn’t super straightforward 😕)

In any case, I’ve run out of time for this writeup. Apologies to my readers for the mistake. I’m a little embarrassed about this snafu and will try to be more careful moving forward. I hope to see you for the next puzzle!