December is upon us, and with that Dan Mayoh has brought us an instalment of the Critical Line that has nothing in particular to do with Christmas. Christmas is for friends and family, but puzzles are for everyone year-round!

Before we get to the challenge, I would like to share two other interesting puzzles I have come across in books recently.

### The Two Envelopes Problem

This has some elements in common to the well known Monty Hall Problem. In the Two Envelopes Problem, you are presented with two sealed envelopes, and you know that one contains twice the money of the other (but you do not know which has the larger amount). You are allowed to pick an envelope and open it to see how much money it contains. You are then given a choice to keep that envelope, or swap it with the other envelope and keep its contents instead, with the objective of maximising your return.

### The Critical Line volume 7 solution

By Oliver Chambers (ochambers@deloitte.com.au)

There were no winners to this month’s puzzle. Honourable mention to Paul Swinhoe who submitted the correct answer without proof.

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?

Solution

The minimum number of pieces that the actuary should cut his cake into is $$p + q$$ – $$1$$.

First we show that this is attainable. Consider a rectangular cake, and make cuts at $$\frac{1}p, \frac{2}p, \dots, \frac{p-1}p$$ and $$\frac{1}q, \frac{2}q, \dots, \frac{q-1}q$$. This will divide the cake into $$p+q-1$$ pieces (no cuts will coincide because $$p$$ and $$q$$ are relatively prime). It can also clearly be grouped into equal quantities of cake for $$p$$ or $$q$$ guests. (Note that if the cake isn’t rectangular you just need to cut the cake into pieces with those volumes of cake). Below is an illustration for $$(p,q) = (4,9)$$

Next we need to demonstrate that you cannot do better than $$p+q-1$$. To do so we will utilise some graph theory. There are three steps:

1. Define a graph with $$p+q$$ vertices such that each partition of the cake represents a vertex and each piece of cake is mapped to an edge of the graph.
2. Show the graph is connected
3. Show that every connected graph on $$n$$ vertices has at least $$n-1$$ edges, and therefore at least $$p+q-1$$ pieces of cake.

Assume we have a partition of cake into $$k$$ pieces with volumes $$\omega_1, \omega_2, \dots, \omega_k$$, such that $$\sum_j \omega_j = pq$$. Further assume we have a desired partition these pieces into disjoint subsets $$P_1 \cup P_2 \cup \dots \cup P_q$$ and $$Q_1 \cup Q_2 \cup \dots \cup Q_p$$ where the pieces in group $$P_i = \{\omega_{i_1}, \dots , \omega_{i_n}\}$$ sum to $$p$$ and those in $$Q_j$$ sum to $$q$$.

Define a graph with a vertex for each set $$P_i$$ and $$Q_j$$ and draw an edge between each pair $$P_i$$ and $$Q_j$$ if they both contain the same piece $$\omega_{\ell}$$, that is $$P_i \cap Q_j \neq \emptyset$$. Then we draw at most as many edges as there are distinct pieces $$\omega_{\ell}$$. This is illustrated in the diagram below.

We will show that this graph is connected. That is, any two vertices are connected by a series of edges (a path). To do so, consider any connected component of this graph. This is a subgroup of connected vertices such that no additional vertices outside the subgroup are connected to vertices inside the subgroup by an edge. Suppose this component has $$s+t$$ vertices $$\{P_{i_1}, P_{i_2}, \dots, P_{i_s}, Q_{j_1}, Q_{j_2}, \dots, Q_{j_t} \}$$.

Notice that the sum of all the volume of cake in all $$P$$-groups is $$p\cdot s$$ and the sum of the cake volume in all $$Q$$-groups is $$q\cdot t$$. Further, these two quantities are equal because, by definition of the connected component, each quantity $$\omega$$ appears in exactly one $$P_i$$ and one $$Q_j$$. Therefore $$ps = qt$$. However, because $$p$$ and $$q$$ are relatively prime, this means that $$q$$ divides $$s$$ and $$p$$ divides $$t$$. Therefore $$s+t \ge p+q$$ so our component is actually the entire graph, which must be connected.

Finally we demonstrate that any connected graph, $$G$$, on $$n$$ vertices has at least $$n-1$$ edges. Prove this by induction: any graph with $$n$$ vertices and $$e$$ edges has at least $$n-e$$ connected components. When $$e=0$$ the claim is trivial. If $$e > 0$$ then remove one edge, $$uv$$, from the graph. This increases the number of components by at most $$1$$ (i.e. if $$u$$ and $$v$$ are no longer in the same component). So by the inductive hypothesis there are at least $$n$$ – $$(e-1) -1 = n-e$$ connected components.

Because there are at most as many edges as there are pieces of cake there must be at least $$p+q-1$$ pieces of cake $$\square$$

If we extend this argument slightly then you can also prove the more general statement for any $$p$$ and $$q$$: that you need $$p + q – \gcd(p,q)$$ pieces of cake.

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

Previous

Next