{"id":2563,"date":"2018-12-01T13:25:48","date_gmt":"2018-12-01T19:25:48","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2563"},"modified":"2019-10-02T17:41:49","modified_gmt":"2019-10-02T22:41:49","slug":"alice-and-bob-fall-in-love","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/alice-and-bob-fall-in-love\/","title":{"rendered":"Alice and Bob fall in love"},"content":{"rendered":"

In this interesting Riddler problem<\/a>, we’re dealing with a possibly unbounded sequence of… children? Here it goes:<\/p>\n

\nAs you may know, having one child, let alone many, is a lot of work. But Alice and Bob realized children require less of their parents\u2019 time as they grow older. They figured out that the work involved in having a child equals one divided by the age of the child in years. (Yes, that means the work is infinite for a child right after they are born. That may be true.)<\/p>\n

Anyhow, since having a new child is a lot of work, Alice and Bob don\u2019t want to have another child until the total work required by all their other children is 1 or less. Suppose they have their first child at time T=0. When T=1, their only child is turns 1, so the work involved is 1, and so they have their second child. After roughly another 1.61 years, their children are roughly 1.61 and 2.61, the work required has dropped back down to 1, and so they have their third child. And so on.<\/p>\n

(Feel free to ignore twins, deaths, the real-world inability to decide exactly when you have a child, and so on.)<\/p>\n

Five questions: Does it make sense for Alice and Bob to have an infinite number of children? Does the time between kids increase as they have more and more kids? What can we say about when they have their Nth child \u2014 can we predict it with a formula? Does the size of their brood over time show asymptotic behavior? If so, what are its bounds?\n<\/p><\/blockquote>\n

Here is an explanation of my derivation:
\n[Show Solution]<\/a><\/p>\n

\n

Let’s call $t_k$ the time at which Alice and Bob have their $k^\\text{th}$ child. The first child is born at time zero, so $t_1 = 0$. Since the work due to a child is one divided by their age, the work due to child $k$ at time $t$ is given by:
\n\\[
\n\\text{work at time }t = \\begin{cases}
\n\\frac{1}{t-t_k} & \\text{if }t > t_k \\\\
\n0 & \\text{otherwise}
\n\\end{cases}
\n\\]We also know that each new child is born once the total work due to all previous children equals $1$. Therefore, we have the following equations:
\n\\begin{align}
\nt_2\\text{ satsifies:} && \\frac{1}{t_2-t_1} &= 1 \\\\
\nt_3\\text{ satisfies:} && \\frac{1}{t_3-t_2} + \\frac{1}{t_3-t_1} &= 1 \\\\
\nt_4\\text{ satisfies:} && \\frac{1}{t_4-t_3} + \\frac{1}{t_4-t_2} + \\frac{1}{t_4-t_1} &= 1 \\\\
\n\\cdots\\qquad \\\\
\nt_k\\text{ satisfies:} && \\sum_{i=1}^{k-1} \\frac{1}{t_k-t_i} &= 1
\n\\end{align}and so on. We also know that $t_1 \\lt t_2 \\lt t_3 \\lt \\ldots$ since the children are born sequentially. The nice thing about these equation is that they can be solved sequentially. We know that $t_1=0$. Substituting this into the first equation yields $t_2=1$. Substituting these values into the second equation yields:
\n\\[
\n\\frac{1}{t_3-1}+\\frac{1}{t_3} = 1
\n\\]Rearranging yields $t_3^2-3t_3+1=0$. This equation has two solutions, but we take the one that satisfies $t_3 \\gt t_2$, and we obtain $t_3=\\tfrac{3+\\sqrt{5}}{2} \\approx 2.618$. We can continue in this fashion, solving each subsequent equation by substituting the previous values… but things get complicated in a hurry. The next equation becomes:
\n\\[
\nt_4^3-\\left(\\tfrac{11+\\sqrt{5}}{2}\\right)t_4^2+\\left(\\tfrac{13+3\\sqrt{5}}{2}\\right)t_4-\\left(\\tfrac{3+\\sqrt{5}}{2}\\right)=0
\n\\]Once again, we find that there is a unique solution that satisfies $t_4 \\gt t_3$. This solution is approximately $t_4\\approx 4.5993$. There doesn’t appear to be any automatic way to continue this process. Every time we try to compute the next $t_k$, we have to find the root of an even more complicated polynomial!<\/p>\n

We’ll take a numerical approach, but let me first address one issue: how can we be sure that these ever-more-complicated polynomials always have a root that satisfies our constraints? For example, what if the polynomial for $t_4$ had no roots larger than $t_3$? What if it had many such roots? Thankfully, there is a simple way we can guarantee that there is always exactly one admissible root to each polynomial by leveraging the intermediate value theorem<\/a>. Specifically, the function
\n\\[
\nf_k(t) = \\frac{1}{t-t_1} + \\frac{1}{t-t_2} + \\cdots + \\frac{1}{t-t_{k-1}}
\n\\]with $t \\gt t_{k-1} \\gt \\ldots \\gt t_1$ is a continuous and strictly decreasing function. Moreover, $\\lim_{t\\to {t_{k-1}}^+}f_k(t) = +\\infty$ and $\\lim_{t\\to\\infty} f_k(t) = 0$. Therefore, by the intermediate value theorem, there must be some point $t_k \\in (t_{k-1},\\infty)$ such that $f_k(t_k)=1$. The strict monoticity of $f_k$ ($f_k$ is strictly decreasing) implies that this $t_k$ must be unique.<\/p>\n

The root may be unique, but how can we find it efficiently? Here, we can leverage a further property of $f_k$; namely convexity<\/a>. The fact that $f_k$ is convex (and smooth) means that we can leverage some efficient methods from convex analysis that make use of derivative information. There are many ways to get the answer from here… What I ended up doing was to use the L-BFGS algorithm<\/a> on the objective $(f_k(t)-1)^2$. My implementation in Julia<\/a> using the Optim.jl<\/a> package took about 40 seconds to evaluate birth dates of the first 1,000 children.<\/p>\n

Note:<\/strong> there are many ways to formulate this as an optimization problem. One way is to note that solving $f_k(t)=1$ is equivalent to extremizing the antiderivative of $f_k(t)-1$. In other words, we could solve:
\n\\[
\nt_k = \\underset{t \\gt t_{k-1}}{\\text{arg min}} \\left( t-\\sum_{i=1}^{k-1}\\log(t-t_i) \\right)
\n= \\underset{t \\gt t_{k-1}}{\\text{arg max}}\\,\\, e^{-t}\\prod_{i=1}^{k-1}(t-t_i)
\n\\]Incidentally, this last expression for $t_k$ makes it clear that there should be a unique $t_k$. When $t\\gt t_{k-1}$, the product is a polynomial that is strictly increasing, and it’s multiplied by $e^{-t}$, which will drive it to zero eventually. There must therefore be a unique maximizer. I tried implementing both of these approaches and both turned out to be slower than directly minimizing $(f_k(t)-1)^2$.\n<\/div>\n

If you’re just interested in the answers to the questions, here they are:
\n[Show Solution]<\/a><\/p>\n

\n