A Game of Thrones

12 Jan 2018

Suppose you’re the ruler of a vast empire, composed of $k$ kingdoms. As emperor, you’ve decided that who sits on each throne is too important to be left up to random things like birth order; you’d like to manage the succession to each throne personally. You don’t want to be bothered each time a king or queen dies, however. You are emperor, after all.

Instead, you decide that you will handpick the line of succession for each of the $k$ thrones. These succession orders will be valid until $f$ nobles sitting on or in line to a throne die, at which point you will revisit the succession question and design a new chart. There is one caveat, however: you do not want any of the kingdoms to be consolidated. None of your vassals should sit on two thrones simultaneously.

Let $n$ be the number of your vassals you consider worthy of sitting on one of your empire’s thrones. We’d like to answer the following question: how large must $n$ be to support lines of succession for $k$ thrones such that no king or queen will ever sit on two thrones even if $f$ nobles in those succession lines die?

In order to have a suitable succession chart, what you need to come up with is a matrix:

\[%-------------------- % PREAMBLE %-------------------- \require{cancel} \require{color} \renewcommand\CancelColor{\color{blue}} \newcommand{\ullabeld}[3]{ {\scriptstyle #3} \left \{ \vphantom{#1}\smash{\overbrace{#1}^{#2}} \right. \vphantom{\overbrace{#1}^#2} } %-------------------- % END PREAMBLE %-------------------- \ullabeld{\begin{matrix} \nu_{1,1} & \nu_{1,2} & \cdots & \nu_{1,k} \\ \nu_{2,1} & \nu_{2,2} & \cdots & \nu_{2,k} \\ \vdots \\ \nu_{f+1,1} & \nu_{f+1,2} & \cdots & \nu_{f+1,k} \end{matrix}}{k}{f+1}\]

where $\nu_{i,j}$ is the $i$th in line to the $k$th throne (the 1st in line currently sits on the throne). For a given $j$, each of the $\nu_{i, j}$ must be unique. This matrix also needs to have the special property that if up to $f$ of the nobles you appoint die, none of your vassals occupies two thrones simultaneously.

For instance, a succession setup for $k=3$, $f=3$ of the following form is not admissible under the previous condition.

\[\begin{matrix} a & b & c \\ d & e & f \\ g & d & h \\ i & j & k \\ \end{matrix}\]

If the following 3 nobles died, then $d$ would sit on two thrones at the same time.

\[\begin{matrix} \xcancel{a} & \xcancel{b} & c \\ d & \xcancel{e} & f \\ g & d & h \\ i & j & k \\ \end{matrix}\]

With the groundwork laid, we’re ready to start tackling the problem of how large $n$ must be to support an admissible succession plan for any given $k$ and $f$. The first thing to notice is that none of your vassals currently sitting on a throne can be in the line of succession for any other throne; otherwise, if the $f$ nobles ahead of them in the other line of succession died, they’d sit on two thrones simultaneously.

\[\begin{matrix} v_1 & \xcancel{\cdot} \\ \cdot & \xcancel{\cdot} \\ \cdot & \xcancel{\cdot} \\ \vdots \\ \cdot & v_1 \\ \end{matrix}\]

So, the picture we have so far looks like this:

\[\begin{matrix} v_1 & v_2 & v_3 & \cdots & v_k \\ \cdot & \cdot & \cdot & \cdots & \cdot \\ \cdot & \cdot & \cdot & \cdots & \cdot \\ \vdots \\ \cdot & \cdot & \cdot & \cdots & \cdot \\ \cdot & \cdot & \cdot & \cdots & \cdot \\ \end{matrix}\]

The next thing to notice is that any second-in-line noble can occupy any of the last-in-line positions to any other throne but no higher position.

\[\begin{matrix} v_1 & v_2 & v_3 & \cdots & v_k \\ v_{k+1} & \cdot & \cdot & \cdots & \cdot \\ \cdot & \cdot & \cdot & \cdots & \cdot \\ \vdots \\ \cdot & \cdot & \cdot & \cdots & \cdot \\ \cdot & v_{k+1} & \cdot & \cdots & \cdot \\ \end{matrix}\]

In fact, a second-in-line noble can occupy all of the other last-in-line positions.

But, we need at least $k$ second-in-line nobles, so we might as well distribute the other positions equally.

\[\begin{matrix} v_1 & v_2 & v_3 & \cdots & v_k \\ v_{k+1} & v_{k+2} & v_{k+3} & \cdots & v_{2k} \\ \cdot & \cdot & \cdot & \cdots & \cdot \\ \vdots \\ \cdot & \cdot & \cdot & \cdots & \cdot \\ v_{2k} & v_{k+1} & v_{k+2} & \cdots & v_{2k -1} \\ \end{matrix}\]

Similarly, a third-in-line noble can be second-to-last in another line of succession but no higher.

\[\begin{matrix} v_1 & v_2 & v_3 & \cdots & v_k \\ v_{k+1} & v_{k+2} & v_{k+3} & \cdots & v_{2k} \\ v_{2k+1} & v_{2k+2} & v_{2k+3} & \cdots & v_{3k} \\ \vdots \\ v_{3k} & v_{2k+1} & v_{2k+2} & \cdots & v_{3k -1} \\ v_{2k} & v_{k+1} & v_{k+2} & \cdots & v_{2k -1} \\ \end{matrix}\]

This trend continues until we get to the “middle” row (the $\left \lceil \frac{f}{2} \right \rceil + 1$ row). If $f$ is even, then this is the exact same situation as the above. Nobles in these positions in the lines of successions can also occupy the position directly below this one in another line of succession but cannot simultaneously occupy any positions on the same row or higher. However, if $f$ is odd, a single noble can simultaneously occupy all positions in this row, since $2 \left \lceil \frac{f}{2} \right \rceil > f$.

This brings us finally to a lower bound on a value of $n$, as well as a plan for what the lines of succession could look like when the bound is tight.

\[n \ge \begin{cases} k\left (\frac{f}{2} + 1 \right ) & \text{$f$ even} \\ k \left (\left \lfloor \frac{f}{2} \right \rfloor + 1 \right ) + 1 & \text{$f$ odd} \end{cases}\]