The Critical Line – Volume 26

Dan Mayoh delivers this months puzzle challenge – Death by chocolate.

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.

Comments

Image of Phil Stott
Phil Stott says

December 7 2018

IN your proof of Part B: "...so we have a new fractional component p/q with a strictly smaller numerator. Therefore, this process is guaranteed to eventually reduce the fractional component to zero …" How does this follow? It is possible to have a monotonic decreasing series of fractions that never reaches zero (eg 1/n). I reached this point in my effort to prove the result, but could get no further ...

Image of Oliver Chambers
Oliver Chambers says

December 12 2018

Hi Phil, note that it is the numerator, p, that is strictly smaller - which must be an integer.
Regards,
Oliver


Comment on the article (Be kind)

You must be logged in to post a comment.

Sign In To Comment

Most Popular