The Critical Line – Volume 27

As per the example solution below, the larger grid must be completed to ensure that the number in every black box refers to the total length of lines originating from and reaching across the grid.

Bonus points for those solutions who recognise the themed (but not picture perfect) image created by highlighting all the lines of length one. E.g. the two middle lines in the example puzzle.

Happy puzzling!

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

Volume 26 Solution – Death by Chocolate

By Dan Mayoh

There were 8 correct answers submitted to this puzzle.  Congratulations to Oliver Chambers, Jackie Lok, Andrew Parker, Johnny Wong, Etjon Basha, Min Chen, Sun Yu and William Ong.  The winner of the book voucher is Jackie Lok.

Solution:

For population N, if X is the optimal number of people to poison, and E(N) is the expected number of survivors at the end of the entire process with a current population of N when following the optimal strategy, then by definition of the problem we have the relationship:

E(N) = (X/N) * (N-X) + (N-X)/(N) * E(N-X-1)

This is relatively straightforward to program recursively, starting with N = 2 and finding the optimal value X for our current N by looking at the expected value of survivors for all possible choices of X.  We then increase N by 1 and repeat, using past results to help us along the way.  By the time we get to N = 1000, we find that the optimal number of bars to poison on the first night is 31.  At most we will have 58 nights where we poison bars, and the amount poisoned each night will be

[31, 31, 30, 30, 29, 28, 28, 27, 27, 26, 26, 25, 25, 24, 24, 23, 23, 22, 22, 21, 21, 20, 20, 19, 19, 18, 18, 17, 17, 16, 16, 15, 15, 14, 14, 13, 12, 12, 11, 11, 10, 10, 9, 9, 8, 8, 7, 7, 6, 5, 5, 4, 4, 3, 3, 2, 1, 1]

Following this strategy the expected number of bars remaining will be 479.496.

One aspect of this solution that no one identified in their original submission is that the optimal value X for a given N is closely related to the square root of N.  More specifically, in every case for N = 2 to N = 1000, the optimal value X is either the square root of N rounded down, or 1 less than the square root of N rounded down.  Why might this be, or how might we have identified this behaviour analytically, or solved this problem in the continuous case?

Recall we have the relationship

E(N) = (X/N) * (N-X) + (N-X)/(N) * E(N-X-1)  (equation 1)

If we assume for large N that the ratio of E(N)/N is constant (which it approximately is, around 0.479496 for N=1000), then we can assume that

E(N)/N = E(N-X-1)/(N-X-1)  (equation 2).

Re-arranging (2) and substituting that into (1), and then rearranging that we arrive at

E(N) = (N*X^2 – N^2*X) / (X^2 + (1-2N)*X – N)  (equation 3).

We want to find the value of X that maximises E(N) for a given N.

If we differentiate (3) with respect to X and solve for when the derivative is zero, we arrive at E(N) is maximised when

X = SQRT(N) – (N-SQRT(N))/(N-1).

The second term is always between 0 and 1 (for N>=2) and therefore the optimal number to poison in the continuous case, assuming the constant ratio of E(N)/N, is always between SQRT(N) and SQRT(N)-1.  So that gives some insight into what is going on.

In the discrete case, the optimal number is always either SQRT(N) rounded down or SQRT(N)-1 rounded down for as far as I’ve programmed.

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