POW ("Around Kind Arthur's Table") help.

[tippytippy]

Hey, I was wondering if anyone could help me find a way to determine the solution for this POW. I have been struggling with it for a while, so any help would be greatly appreciated.

The problem:
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, "Your out." He'll say to the second knight, "Your in," and says to the third one "your out," and so on around the table. He continues doing this around the table, skipping the knights he as already deemed "out." Obviously, the winner will be sitting in an even number chair.

Thus far I have found:
# of knights: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Winner: 2 2 4 2 4 6 8 2 4 6 8 10 12 14 16 2 4


I'm having trouble finding patterns.. at least I think I am, as I keep second guessing myself and what not. If anyone could offer help regarding finding a solution in which I would ultimately be able to determine where to sit if there were 99 knights present, or just any type of clues towards such solution. Also, I really need help finding specific patterns in this problem, so any help/clues would be so appreciated!!

 

[daon]

If I were to guess just from the data It should be immediately "obvious" that for 2^n knights, the (2^n)th night wins.
But looking at the correspondence 15->14, 14->12 an adjustment must be made for the general case. I will give you a candidate and let you prove it.

For any positive integer x>1 where x is not a power of 2, write x=2^n+k where n is a positive integer and 0<k<2^n. Then f(x) = f(2^n+k)=2k if x is not a power of 2, or f(x)=x otherwise.

To build intuition, here is how it works:

f(18) = f(2^4+2) = 2*2=4
f(14) = f(2^3+6) = 2*6=12
f(8) = f(2^3)=8

edit:

Alternatively, but this is equivilent (with perhaps less thinking needed to get your answer),

f(x) = 2(x-2^Floor(lg(x))), where lg=log_2

 

[tippytippy]

Thank you so much!

I just have a couple of further questions...

I understand how this is working, but I'm having trouble understanding where you are coming up with values for n and k... I know this sounds stupid, but in the case of 18=4, how would I know that it would be 2^4+2. I see that it will be 2^n, as it will be a power of two, but without knowing that 4 is the winner, how would figure that out, and further, how would I realize that k=2.

I know this is very simple, I just want to make sure I know where we are getting everything from.

 

[tippytippy]

One other question... in the equation: f(x) = 2(x-2^Floor(lg(x))), where lg=log_2 what does Floor mean?

 

[daon]

n is the largest exponent such that 2^n less than x. k is the remainder after division by 2^n (or simply x-2^n). Floor is the greatest integer function. Google it.