Alice and Bob fall in love

In this interesting Riddler problem, we’re dealing with a possibly unbounded sequence of… children? Here it goes:

As 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’ 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.)

Anyhow, since having a new child is a lot of work, Alice and Bob don’t 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.

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

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 — can we predict it with a formula? Does the size of their brood over time show asymptotic behavior? If so, what are its bounds?

Here is an explanation of my derivation:
[Show Solution]

If you’re just interested in the answers to the questions, here they are:
[Show Solution]

9 thoughts on “Alice and Bob fall in love”

  1. One thought: the problem solution structurally looks quite similar to what comes up in the derivation of Newton’s Identities, in particular

    $\frac{p'(t)}{p(t)} = f_k(t) = \frac{1}{t-t_1} + \frac{1}{t-t_2} + \cdots + \frac{1}{t-t_{k-1}} =\sum_{i=1}^{k-1} \big(\frac{1}{t} + \frac{t_i}{t^2} + \frac{t_i^2}{t^3} + \cdots\big) = \frac{s_0}{t} + \frac{s_1}{t^2} + \frac{s_2}{t^3}+ \cdots$

    where we have the power sum
    $s_r := t_1^r + t_2^r + … + t_{k-1}^r$

    (though in this case we are looking for the maximal $t$ that sets the above equal to one)

    1. Nice observation — I thought about it a bit more and realized we could also express $t_k$ in the following compact form:
      \[
      t_k = \underset{t \gt t_{k-1}}{\text{arg max}}\,\, e^{-t}\prod_{i=1}^{k-1}(t-t_i)
      \]It doesn’t buy us much, but it’s pretty! I updated my blog post to include this note.

  2. Hi Laurent,
    Very nice post, of course my results agree with yours.
    I interpreted the question about “a formula” as a question “can I find an explicit expression” which you can for t1, t2 (linear equation), t3 (quadratic equation), t4 (cubic), and t5 (quartic), but there is no general formula for the roots of a quintic, so there is no “formula” for t6 (though there is an implicit relation or polynomial with instructions for root finding).
    Regarding the asymptotic behavior, I think it’s not hard to show that
    t_n – t_{n-1} = ln(n) + EulerGamma + O(1/ln(n))
    and so far I think I calculated the O(1/ln(n)) term to be 1/( 4 ln(n)) + O(1/ln^2(n)).

    The “proof” is that for large n, the spacing becomes nearly uniform. If it were precisely uniform, we would have (writing the spacing as Delta)
    1 = 1/Delta + 1/(2 Delta) + … + 1/(n Delta) = (1/Delta) (ln(n)+EulerGamma+small)
    resulting in Delta = ln(n) + EulerGamma.
    Of course the spacing is not exactly uniform. Really we should write
    1/(2 Delta) as 1/(Delta_n + Delta_{n-1}) and so forth.
    But Delta_{n-1} is approximately EulerGamma + ln(n-1) = Delta – O(1/n). The sum of the 1/n corrections proves to be subleading by a 1/ln(n) factor….

    1. Guy, Laurent,

      Thanks for your solutions/posts.

      I used Guy’s insight to derive upper and lower bounds. The lower one turns out to be tight and close to Laurent’s line fit. (Laurent, this is with the -0.315N from your figure. Your text uses -3.15N. Is that a type?)

      The upper bound diverges a bit but has a nice form.

      See https://colab.research.google.com/drive/1fKSNWX3cZvbkx1XnWJDwXu3eDpgr_B4y#scrollTo=3iAgOeceH9BR or follow links from https://sites.google.com/view/msbits

      I give a shout out to Guy’s comment and Laurent’s blog there. Please let me know if you would like me to provide alternate references.

  3. Does the time between kids increase as they have more and more kids?

    Proof by contradiction that the length of time between births increases without bound.
    Let x_n be the length of time between the n-1 th and n th birthdays.
    Assume there is a maximum length of time (y) between any two births.

    The n+1 th birth will happen when:
    1/x_n + 1/(x_n + x_n-1) + … + 1/(x_n + x_n-1 + … + x_2 + x_1) = 1

    x_n <y
    x_n + x_n-1 < 2y

    x_n + x_n-1 + … + x_2 + x_1 < n y

    1/y + 1/(2y) + 1/(3y) + … + 1/((n-1)y) + 1/(n y) < 1

    1 + 1/2 + 1/3 + … + 1/(n-1) + 1/n < y

    However, the sum on left hand side is the harmonic series which is known to diverge.
    Therefore, the assumption is false and y (length of time between births) is unbounded with n.

    Link to list of the first 10,000 birthdays:
    https://docs.google.com/spreadsheets/d/1s5RtpjMd_RvCYDiw3TwQjlJUTOFX9CdSb46QBrPr_hw/edit?usp=sharing

  4. I found a little different way to show asymptotic behavior. As you have stated
    $$
    \sum_{i=1}^{k-1}\frac{1}{t_{k}-t_{i}} = 1
    $$
    Rewrite this as
    $$
    \sum_{i=1}^{k-1}\frac{1}{1-\frac{t_{i}}{t_{k}}} = t_{k}
    $$
    For large $k$, if we posit a solution of the form
    $$
    t_{k} \simeq k H_{k-1}
    $$
    with $H_{k}$ being the Harmonic numbers, and noting that for large $k-i$,
    $$
    \frac{t_{i}}{t_{k}} \rightarrow 0
    $$
    and for small $k-i$
    $$
    \frac{t_{i}}{t_{k}} \rightarrow \frac{k}{k-i}
    $$
    you get the identity
    $$
    k H_{k-1} \simeq k \sum_{i=1}^{k-1} \frac{1}{k-i} = k H_{k-1}
    $$

Leave a Reply

Your email address will not be published. Required fields are marked *