0
$\begingroup$

$n$ knights sit around a round table, which magically adjusts its size to fit the number of knights sitting around it.

The knights cannot get up out of their seats and their swords are only long enough to impale their two immediate neighbours.

Unfortunately due to an argument about Guinevere's honour, they have an enormous falling out and start impaling their immediate neighbours. Any impaling is immediately fatal and obviously a dead knight cannot impale either of his neighbours. Once a knight is dead, his seat vanishes and the table shrinks.

At the end of the fight the table has shrunk to a single seat and all the knights but one are dead.

Obviously there are $n$ possible outcomes, but how many different ways (in terms of who killed whom, and in what order) are there of arriving at any given outcome in which some given knight remains?

$\endgroup$
  • 1
    $\begingroup$ A macabre question! Do the killings happen simultaneoulsy or do we have only one fight at any time ? $\endgroup$ – Peter May 23 '17 at 16:36
  • $\begingroup$ If its one at a time, then when you have $k$ knights, there are $k-1$ possibilities for the next dead one, and 2 possibilities for the murderer. Seems quite simple. Am I missing somethig? $\endgroup$ – thedude May 23 '17 at 16:38
  • 2
    $\begingroup$ This sounds related to the Josephus problem youtube.com/watch?v=uCsD3ZGzMgE oeis.org/… $\endgroup$ – Benedict W. J. Irwin May 23 '17 at 16:38
  • $\begingroup$ @Peter no two killings occur simultaneously. But a great question! I hadn't thought of that. $\endgroup$ – user334732 May 23 '17 at 16:41
  • $\begingroup$ @thedude when you have $k$ knights, are there not $k$ possibilities for the next dead? $\endgroup$ – user334732 May 23 '17 at 16:57
2
$\begingroup$

Suppose we fix one knight as the survivor from the outset.

When there are $k$ knights, with $k>2$, there are $k-1$ possibilites for the next dead, and 2 possibilities for his murderer. So there are $2(k-1)$ possible outcomes.

Total number of outcomes is actually the product $$\prod_{k=3}^n 2(k-1)=2^{n-2}(n-1)!$$

$\endgroup$
  • $\begingroup$ Only you can change the j to a k as it's only 1 char change. $\endgroup$ – user334732 May 24 '17 at 0:32
0
$\begingroup$

Let the total number of ways this can happen at an $n$ person table be $K(n)$.

Now, for the first death, we can choose $n$ different knights to be killed, and each knight can be killed in 2 different ways (left or right neighbor since this is a circle. Therefore, there are $2n$ ways to kill a knight at stage $n$.

The exception to this is the case of 2 knights, in which case only 2 outcomes are possible.

Then clearly, since $n$ is arbitrary, we can write

$$K(n) = 2 + \sum\limits_{k=3}^n 2k = 2 + 2 \sum\limits_{k=3}^n k = 2 + 2 * (n(n+1)/2 - 3) = n(n+1)-4$$

which is a valid equation for all $n \geq 2$. I did this pretty quickly so I might have made a mistake but I think that should do it. This could also be done using a linear recurrence, but I don't really have the time to work it out that way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.