The Critical Line – Volume 26

Here’s an enjoyable problem I came across recently, that I have paraphrased and adapted slightly. I’m unsure of the original author. You have 1000 chocolate bars sitting in the kitchen cupboard at work.  You know that each night when everyone else is gone, a thief will select exactly one chocolate bar at random and eat it.  If this was left unaddressed, then in a little under three years you would be all out of chocolate. But, you also know that if you poison some chocolate bars in a way the thief cannot detect overnight, and the thief selects and eats a poisoned bar, he or she will be put off by the bad taste and will permanently stop taking any more chocolate bars.  The catch is that the next morning, any bars you poisoned the day before that the thief didn’t take will have to be thrown out, due to the poison causing them to visibly go bad the next morning.

Once the thief has selected a poisoned bar and is gone, your troubles will be over.  You will know the next morning if your troubles are over and you can cease poisoning some of your chocolate bars, because you know how many you poisoned the day before and how many have gone bad from those that remain.

Your goal is to get rid of the thief, whilst maximising the expected value of the number of bars that remain not poisoned and not stolen once the thief is gone.

How many bars from the original 1000 should you poison on the first day?  How many on subsequent days assuming the thief is still active?  Following this optimal strategy, what is the expected number of bars that survive this ordeal?

For your chance to win a $50 book voucher, send your solutions to ActuariesMag@actuaries.asn.au

Volume 25 Solution

We had four solutions this month: Robert Tan, Siddharth Lyer, Andrew Parker, Kelvin Duong. All submitted a nice write up of the solution, making selection of a winner difficult, but this month it goes to Robert Tan. The solution is below:

A sequence $$\{\alpha_0, \alpha_1, \alpha_2 \dots\}$$ is defined such that $$\alpha_{n+1} = \alpha_n + \frac{1}{\lfloor \alpha_n \rfloor}$$, for all $$n \ge 1$$, where $$\lfloor x \rfloor$$ denotes the greatest integer less than or equal to $$x$$.

1. If $$\alpha_0 = \frac{43}{11}$$, what is the smallest $$k$$ such that $$\alpha_k$$ is an integer? (computers allowed)
2. Show that if $$\alpha_0$$ is rational and $$\alpha_0 > 1$$ then the sequence must contain an integer

Solution

Part B
We start with the proof of Part B, and then generalise Part A

Let $$\alpha_0 = m + \epsilon$$, where $$m\in\mathbb{N}$$ and $$\epsilon \in [0, 1)$$ is rational. The first few terms of the sequence are $$m + \epsilon, m + \epsilon + \frac{1}m, m + \epsilon + \frac{2}m, \dots$$. So eventually we reach $$\alpha_{k_0} = m + 1 + \frac{p}{q}$$ where $$\frac{p}{q} < \frac{1}m$$ (if $$p = 0$$ we have nothing to prove).

Note for later: $$k_0 = \lceil m(1 – \epsilon) \rceil$$

Take $$r$$ such that $$\frac{1}{r} \le \frac{p}{q} < \frac{1}{r-1}$$. The sequence now increases at a rate of $$\frac{1}{m+1}$$, and if $$r > m$$ then eventually we get to $$m + 1 + \frac{p}{q} + \frac{m}{m+1} < m+2$$, and adding $$\frac{1}{m+1}$$ on more time brings us to $$m + 2 + \frac{p}{q}$$ (i.e. with exactly the same fractional part). 

We can continue in this way until we reach $$\alpha_{k’} = r + \frac{p}{q} + \frac{r-1}{r} = r + 1 + \left( \frac{p}{q} – \frac{1}r \right) = r + 1 + \left( \frac{pr – q}{qr} \right)$$

We must have $$0 \le pr – q < p$$ by our choice of $$r$$, so we have a new fractional component $$\frac{p’}{q’}$$ with a strictly smaller numerator. Therefore, this process is guaranteed to eventually reduce the fractional component to zero (i.e. an integer term) and we have completed the proof.

You may notice that there is a connection to Egyptian Fractions.
In fact the index of the first integer is related to the Egyptian Fraction representation of $$\frac{p}{q}$$ when calculated using a greedy algorithm, as we will now use to calculate the general answer to part (a).

Part A (Download .txt code file here)
As noted above we require $$k_0 = \lceil m(1 – \epsilon) \rceil$$ steps to reach $$\alpha_{k_0} = m + 1 + \frac{p}{q}$$ where $$\frac{p}{q} < \frac{1}m$$.

Again select $$r$$ such that $$\frac{1}{r} \le \frac{p}{q} < \frac{1}{r-1}$$. In fact $$r = \lceil \frac{q}{p} \rceil$$. We must now have $$m+1$$ steps of $$\frac{1}{m+1}$$, then $$m+2$$ steps of $$\frac{1}{m+2}$$, until finally we take $$r-1$$ steps of $$\frac{1}{r}$$, at which point we reduce our fractional part from $$\frac{p}{q}$$ to $$\frac{pr-q}{qr}$$. We repeat this process until the fraction is zero.

Below is a Python function that returns the first index of the integer in the sequence. We see that when $$\alpha_0 = \frac{43}{11}$$, then $$\alpha_k$$ is first an integer for $$k = 871,852$$ (a_k=1321).

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.