Associated Topics || Dr. Math Home || Search Dr. Math

### Knights of the Round Table

```
Date: 07/01/98 at 19:41:59
From: Nan Lou
Subject: Algebra puzzle

Dr. Math,

The problem is called the Knights of the Round Table. Say King Arthur
has a daughter and wants to marry her off to one of his knights. The
way he chooses is to have them all sit down at the round table and
he'll say to the first knight, "You live." He'll say to the second
knight, "You die" and kills him, and lets the third one live and
fourth one die and so forth around and around the round table until
there's only one left. The thing we have to do is figure an equation
that if you know how many knights there's going to be, what position
should you sit in to marry the daughter. So the variables should be
n = number of students and p = the position you should sit in or
something like that. I have figured out a pattern:

number of knight     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
position of survivor 1 1 3 1 3 5 7 1 3  5  7  9 11 13 15  1  3  5  7

So that at every power of two, it starts over at one again. For
example, 2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16 ...
But I just don't know how to put that into an equation.
Thanks for helping me at this problem.

Nan Lou
```

```
Date: 07/02/98 at 20:28:16
From: Doctor Pete
Subject: Re: Algebra puzzle

Hi,

You've basically solved the problem - all you need to do now is to
find the formula. But first, I'll talk a bit about why the pattern is
the way it is. Clearly, if there are 2^n knights, for some positive
integer n, then each time Arthur goes around the table, the first
knight is never killed. So he must be the survivor. When there are
2^n + 1 knights, then after Arthur eliminates knight 2, there are 2^n
knights, and the situation is the same as before, except that the
position has "changed," so that knight 3 is never killed. In general,
if you have 2^n + k knights, where k < 2^n, once you eliminate k
knights, there are only 2^n knights remaining and knight 2k+1 is never
killed.

So to put this into a formula, for x knights, we have to find a
positive integer n and a nonnegative integer k such that x = 2^n + k,
with k < 2^n. Then the knight which is not killed is 2k + 1.

satisfies 2^n <= x; that is, 2^n is less than or equal to x. To find
this value, we can use logarithms. We have n = Floor[Log[2,x]] - that
is, n is the greatest integer less than or equal to the base 2
logarithm of x. Then:

k = x - 2^n = x - 2^Floor[Log[2,x]]

So we have:

2k + 1 = 2(x - 2^Floor[Log[2,x]]) + 1

I know this probably isn't your idea of a nice formula, and if you're
not familiar with the Floor or Log functions, this could be a bit
strange.

- Doctor Pete, The Math Forum
Check out our web site! http://mathforum.org/dr.math/
```

```
Date: 10/30/2001 at 13:34:58
From: Doctor Greenie
Subject: Re: Knight Follow-Up

Hi -

I know of no neat way to write a formula for determining the winner for
a given number of knights n....  However, there are a couple of simple
algorithms that easily and quickly give you the answer.

The solution has something to do with powers of 2; observe that the
pattern starts over at each power of 2.

Since there seems to be a pattern beginning at each power of 2, let's
"get rid of" that power of 2 by subtracting the largest power of 2 from
each number of knights n and work with the pattern we come up with. We
have

number of knights 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
winner            1 1 3 1 3 5 7 1 3  5  7  9 11 13 15  1

and we add a row in between these two, in which we subtract from the
number of knights n the largest power of 2 which is less than or equal
to n:

number of knights 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# knights - 2^k   0 0 1 0 1 2 3 0 1  2  3  4  5  6  7  0
winner            1 1 3 1 3 5 7 1 3  5  7  9 11 13 15  1

The relation between the numbers in the last two rows is simple: double
the number in row 2 and add 1 to get the number in row 3.

So an algorithm for determining the winner for a given number of knights
n is the following:

(1) subtract from n the largest power of 2 less than n
(2) multiply by 2

Example: n = 11

(1) 11-8 = 3
(2) 3*2 = 6
(3) 6+1 = 7

This algorithm has a curious equivalent when the number of knights is
expressed in binary.  Step (1) - subtracting from n the largest power of
2 - is equivalent to removing the leftmost "1" in the binary
representation of a number. Step (2) - multiplying by 2 - is equivalent
to adding a "0" at the right end of the binary representation of a
number. And step (3) - adding 1 - is equivalent to changing the "0" at
the right end of the number (added in step (2)) to a "1".  So the
algorithm for determining the winner for a given number of knights n can
be described as follows:

(1) express n in its binary representation
(2) move the leftmost "1" in the binary representation of n to the
right end

Example: n = 11

(1) 11 (base 10) = 1011 (base 2)
(2) 0111 (base 2) = 111 (base 2) = 7 (base 10)

I'm not sure if this is the kind of response you were looking for; I
will leave your latest message where other doctors can also provide
responses if they so choose.

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 10/30/2001 at 16:23:57
From: Doctor Anthony
Subject: Re: Knight Follow-Up

I will try to explain the method using actual numbers; it is not too
difficult.

Suppose we have x knights, then first express x in the form

2^n + k.

The knight who is left is in seat number  2k + 1.

Example: If we have 13 knights, then we have 13 = 2^3 + 5

The knight who is left is number  2 x 5 + 1 = 11

Therefore you should choose the 11th seat round the table. Draw the
table with 13 seats and work your way round and round and see that
the person in seat number 11 will be the survivor. You must always
skip one 'living' person and 'kill' the next as you go round the
table.

Example 2: If you have 60 knights, then we have  60 = 2^5 + 28

The knight who is left is  2 x 28 + 1 = 57

Therefore you would choose seat number 57 if you want to survive.

One more example should be sufficient to illustrate the method.

Example 3: If you have 35 knights, then  35 = 2^5 + 3

So you would choose seat number  2 x 3 + 1 = 7

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics
High School Number Theory
High School Permutations and Combinations
High School Puzzles
Middle School Puzzles
Middle School Word Problems

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search