Josephus ProblemDate: 04/18/2003 at 20:39:50 From: Jeremy Subject: Determining an equation from a series There are x people sitting around a table. Every other person at the table is eliminated until there is only one person left. For instance, at a four-person table, the second and fourth person are eliminated; then going around the table once more, the third person is eliminated. In this case number 1 is the survivor. Here is a chart I made showing x and the surviving person's number: x surviving person's number 1 1 2 1 3 3 4 1 5 3 6 5 7 7 8 1 9 3 10 5 11 7 12 9 13 11 14 13 15 15 16 1 The pattern shows that the answer increases by 2 along the odd numbers but 'restarts' at one every time x is a power of 2. From this I obtained the equation 2(x-the closest power of two less than or equal to x)+1 = the winner's number. I would like to know if there is a way to rewrite this equation without using any words. Date: 04/19/2003 at 23:07:37 From: Doctor Carbon Subject: Re: Determining an equation from a series Hi Jeremy, This problem is also known as the Josephus problem. A quick search on www.google.com for "Josephus problem" yields hundreds of links describing the original problem along with its history. You will also find relevant entries in the Dr. Math archives: Knights of the Round Table http://mathforum.org/library/drmath/view/55862.html A Circular Massacre http://mathforum.org/library/drmath/view/55876.html Your solution description using words is perfect. The real problem, as you have said, is in turning it into a single precise equation (or expression) for writing the part about "the closest power of two less than or equal to x." Within a longer description like this, I would look for the part that I can write most easily. In this case, "a power of 2" is fairly straightforward, and would look like n 2 or 2^n Our goal, therefore, is to make sure that n is a whole number, and that the result of this calculation is less than or equal to x. You pointed out that you needed a mathematical notation, operation or function that shows the closest power of an integer less than or equal to another number. I have changed the requirement slightly and now we are looking for something that gives whole numbers less than or equal to a given number. I don't know if you have heard of it, but there is something called the Floor function. It is defined as the largest integer less than or equal to the number you use. The way you use it is this: "Floor of 2.3 is 2," "Floor of 15/2 is 7." It is written using a special kind of enclosing bracket, and I will try to make it using plain text here: | | | 2.3 | = 2 |_ _| This is the same as saying "Floor(2.3) = 2" or "Floor of 2.3 is 2." In your case, 2^n should equal the power of 2 closest to but less than x, so n could be written using the Floor function on its own. At this point, we can use the general idea that exponents and logarithms are opposites of each other. Therefore, to get a power of 2 close to but less than x, I could use logarithms to base 2 in this way: | | | Log (x) | |_ 2 _| 2 ^ I hope this helps. The following link to Eric Weisstein's MathWorld entry on the Josephus problem has some variations and historical solutions that you might find interesting. http://mathworld.wolfram.com/JosephusProblem.html On a more philosophical note, my belief is that all mathematical notations must have evolved from long-winded natural language descriptions. Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Carbon, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/