Critical Line – Volume 7

The theme of this month’s column of The Critical Line is efficiency. Everyone likes a bit of efficiency; also I have left this column to the last minute and efficiency is on my mind. I would like to share some small instances of efficiency that the reader may find useful in their day to day life.

Intelligent Design Sort
While perusing the web for the most efficient sorting algorithm to implement in VBA, I came across a remarkably efficient constant time sorting algorithm – the intelligent design sort.

Overview: Intelligent design sort is a sorting algorithm based on the theory of intelligent design.

Algorithm: The probability of the original input list being in the exact order it’s in is $$\frac{1}{n!}$$. There is such a small likelihood of this that it’s clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it’s safe to assume that it’s already optimally sorted in some way that transcends our naïve mortal understanding of “ascending order”. Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.

One drawback of using this algorithm is that fundamental discussions with the model validation team can arise and it sometimes leads to model inquisitions that no one was expecting. For further analysis and corollaries of this algorithm please refer to the webpage of its designer.

Rock Paper Scissor Lizzard Spock
The next example is an improvement to the age-old game of rock paper scissors. The main inefficiency in the game of rock paper scissors is that two people will draw $$\frac{1}{3}$$ of the time, which clearly too high. The easiest way to reduce the expected number of draws is to introduce some new characters: say hello to ‘lizzard’ and ‘spock’. The diagram below illustrates how each move interacts with every other move in this extension of the game:

The primary drawback of this extension is that everybody always chooses spock. This increases the expected number of draws dramaticall and undermines the only motivation for the new characters. Nonetheless credit to the original author here.

Warming Up

Following on from Rock-Paper-Scissors-Lizard-Spock, a natural question arises: for which numbers, $$n$$, can you create a ‘fair’ extension of Rock-Paper-Scissors with $$n$$ possible moves? (Let’s define ‘fair’ to mean that if two players make different moves then the game will be decisive and that each possible move has an equal change to win)

[reveal heading=”

%image% Click to reveal solution

” id=”id1″]SOLUTION: 

The answer is you can create a fair gam of Rock-Paper-Scissors if an only if there are an odd number of moves $$n \ge 3$$. To demonstrate this we prove that it is impossible to have a fair game with an even number of moves, and provide a construction where $$n$$ is odd.

Case 1: $$n$$ is even. For any move there are $$n-1$$ alternative moves for which the game is decisive, because $$n-1$$ is odd the move will not win and lose to an equal number of other moves. Therefore the game is not fair.

Case 2: $$n$$ is odd. Similar to the diagram above, let each move be represented by a point (vertex) and the draw an arrow (directed edge) between two points whenever one move dominates the other. Then we have a directed complete graph.

If we could decompose the edges of the graph into disjoint cycles that go through each vertex once (a Hamiltonian cycle) then we could have a fair game of generalised rock paper scissors. For instance, in the graph below on 5 vertices I have highlighted two directed cycles that define a fair game of rock-paper-scissors.

The question is now, for any odd $$n$$, can we decompose a complete graph on $$n$$ vertices into $$\frac{n-1}{2}$$ disjoint Hamiltonian cycles. This question is specific enough to plug into google (remember this week it’s all about efficiency). The first result gives us our desired construction.[reveal]

An Efficient Birthday

An actuary is hosting a birthday party and he has invited all of his friends and family. He knows that either $$p$$ or $$q$$ people will attend the party, where $$p$$ and $$q$$ are two relatively prime integers (i.e. they share no common divisor). He also strives for efficiency in all aspects of his life and decides to pre-cut the birthday cake. He would like to cut the cake into several pieces such that the cake could by divided into either p or q groups of equal quantity (without further division). What is the minimum number of pieces that the actuary should divide the cake into to meet this requirement?

Critical Line Volume 6 Solution!

We received three answers to this Puzzle and the first to submit – Dan Mayoh – was our chosen winner for the $50 book voucher! Each answer pointed out a flaw in the puzzle design and we want to apologise to everyone who scratched their head over this! There was a lack of clarity on the definition of countries at the Olympics – many nations compete under different titles to their official name e.g. Chinese Taiwan competed under Taiwan and the Independent Olympic Athletes (IOA) is definitely not a country but is a competing state. When designing the puzzle we used the official entrant list on the IOC website, however, it appears answers could have been derived from other sources also.

See final Solution here. Apologies again, happy puzzling!

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