Knights of the Round TableDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/