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.

Thinking about this, in some sense n must be the largest value that 
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
(3) add 1

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/