The Critical Line: Volume 8

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.

At this point, a quick analysis might suggest that if not changing gives you $$$X$$, then changing would give you 50%*($$\frac{X}{2}$$) + 50%*($$2X$$) = $X*($$\frac{5}{4}$$), and you would choose to change. However this same line of thinking seems to apply again once you have the second envelope in your hand (before you open it), or indeed if you had chosen the second envelope to begin with. This looks like a paradox.

The ‘problem’ in the title is not to decide if you should switch. The task of the Two Envelope Problem is to explain the paradox! I’m not going to get into it here, but give it some thought if it takes your interest and then read some of the not-insignificantly-small portion of the internet devoted to discussing this problem…

The Pancake Problem

This is a problem that I am informed was first posed in 1975 under the pseudonym Harry Dweighter (harried waiter). Essentially, it asks:

A chef prepares a stack of circular pancakes that come out all with different radii, stacked one on top of another. I like to rearrange them into an ordered stack with the smallest at the top down to the largest at the bottom. I can only do this by grabbing several from the top of the whole stack, flipping over the stack I grabbed, and placing them back on top of any ungrabbed pancakes.
If there are n pancakes, what is the maximum number of flips (as a function of n) that I will ever have to use to rearrange them? Call this number the Pancake Number Pn.

For example, if $$n=3$$, the worst-case starting arrangement (which would be a stack ordered from top to bottom as radii 1-3-2) will require 3 flips to order. So $$P3 = 3$$.
The problem is to find a way to express $$Pn$$ as a function of n. I am informed that this is unsolved, and that many serious mathematical papers have been published on the topic, including one in 1979 co-authored by William H. Gates of Microsoft fame proving an upper bound of Pn to be $$\frac{(5n+5)}{3}$$.

The Critical Line challenge

Now for the actual problem to be solved. First, let’s discuss a small example to illustrate the problem.
You are given a 6*6 square, and subdivide the entire square into rectangles with integer side lengths. You can divide the square into rectangles (including smaller squares) any way you like, subject to one condition: You cannot use two rectangles of the same dimensions. This includes rotations, so you cannot use both a 2*1 and a 1*2 rectangle. Your ‘score’ from your subdivision is equal to the area of the largest rectangle used minus the area of the smallest rectangle used. Your task is to perform the subdivision in a way that minimises the score.

For a 6*6 square, the smallest possible score is 5 as far as I know. This involves dividing the square into 7 rectangles, the largest of which has an area of 8 and the smallest an area of 3.

Your challenge is to find a sub-division for a 17 * 17 square with a lower score than anybody else.

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.