[color=red]!! IMP III : POW 10 Around King Arthurs Table!!!

Memily

New member
Joined
Jun 3, 2005
Messages
2
There is a game that King Arthur plays with his knights at his round table to decide who wins a prize. Arthur sets up however many chairs that their are knights at the table (sometimes there are a lot of knights sometimes only a handful). Starting at chair one the king alternately says to the knights "You're in" , "You're out." who ever is out leaves the table and the king continues. If there is an empty chair he passes around it and continues in this pattern until there is only one knight left at the table. The question is: If you knew how many knights were going to be at the table, how could you quickly determine which chair to sit in to win? Develop a formula...
PLEASE HELP ME!! :(
 
You have to do some work on it. What have you learned about the N knights?
One hint if you know about binary numbers:
Write N in binary.
Move the first 1 to the end.
That is the winning number.
6 knights = 110
101 = 5 is the winner.
 
Different approaches I found:

Approach#1:
=========
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

Approach#2:
=========
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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (# knights)
1 1 3 1 3 5 7 1 3 05 07 09 11 13 15 01 (winner)

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 <= n:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (# knights)
0 0 1 0 1 2 3 0 1 02 03 04 05 06 07 00 (# knights - 2^k)
1 1 3 1 3 5 7 1 3 05 07 09 11 13 15 01 (winner)

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)

Approach#3:
=========
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.

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

So you would choose seat number 2 x 3 + 1 = 7
 
Thank you so much.. I looked on the internet about binary numbers and with the help you provided me I should be able to complete the POW on my own... YOU GUYS ARE SAINTS!!! :)
 
Memily said:
... YOU GUYS ARE SAINTS!!! :)

"SAINTS" should be singular...me only !
All other tutors here are future guests of Lucifer :)
Code:
                                 TUTORS DON'T CHANGE
                                 ===================
LE BYE BYE CRUEL WORLD
-------------------------------
I kick the bucket, knock over the pail, shed flesh and bones, and that invisible part of me that keeps living takes off, up a long narrow tunnel, and I emerge at the other end to land smack in the middle of a big bunch of male angels. A third of them are playing cards smoking "Heavena" cigars, another third are practicing take-offs and landings, while the last third are just kinda winging it.

LES TWO BIG CARRIER ANGELS
-------------------------------------
I sit in what appears to be a waiting area, pick up a Playangel magazine. But something is bugging me...like, why didn't I land somewhere close to the Pearly Gates, where St-Peter works. Suddenly, two burly angels wearing  carrier tags appear next to me. They tell me to get ready, that they'll be flying me to meet St-Peter. During the flight, they warn me to be careful, that St-Peter is in a real grouchy mood. They've given him a new computer, one that works off social security numbers. But they didn't send anyone to train him...and he has to learn it all by himself...from a huge computer handbook.

LE **** STOP
----------------
Suddenly, I feel real hot. We're entering **** territory, I'm told. My two carriers slow down, stop for a chat with Lucifer. Lucifer is quite pleased with his conversion from oil to natural gas. We're ahead of schedule, he proudly announces, puffing on a huge cigar. Then he takes off his sneakers and wiggles his toes at us. He's got five! Had a transplant, he informs us. At the left of Lucifer's desk, I notice a heat control panel, along with a list of residents by job categories.
The control button under "Teachers" is turned right up to "maximum". An extra notch marked "extra hot" has been added to the button under Lawyers. An extra extra notch marked "super hot" has been added to the button under Preachers.
My two carrier angels accept a double hot gin, one-gulp it down, see you later Lucifer, and we're flying again.

LE MEETING OF ST-PETER
------------------------------
I cough politely. St-Peter painfully looks up from his computer manual, and tells me "not again" with his eyes. I feel guilty for getting there at such a bad time. I offer him a Player's Light. He shakes his head sadly, points to a no-smoking sign. Then he turns on his computer, keys in his password, gets a "down for 5 minutes" message.
He bangs his desk with his left fist. Then he decides to step out the Pearly Gates for a smoke. If my phone rings, he tells me, pick it up and tell 'em I'm in the washroom.
As he's lighting his second Export Plain, I notice the computer screen coming to life. Trying to be helpful, I wave at him and point positively to the screen.
He throws down his cigarette, crushes it with his foot, and comes back. On his face is written "why don't you mind your own business, you bastard".
Pheeeew...at least he didn't tell me to go to ****...yet.


LE ENTRY INTO HEAVEN
----------------------------
After entering my social insurance number, confirming I'm Denis Borris from Canada, Earth, St-Peter hits a few more keys, bangs his desk, tries again, breathes hard, tries again, gives up holding his head in despair Here we go again...this stupid computer...can't get to your list of sins... and they won't send me any help...got to learn it all by myself...you know, I wish they'd give this job to St-Paul, that lazy bum!
He takes a few seconds to cool down, then looks at me; he decides that I look honest...because he starts to question me.
SP: Did you commit many sins?
ME: Well, a few, you know...but not that many.
SP: Gimme an example.
ME: I used the office photocopier to copy some personal stuff.
SP: Bad boy. Gimme another example.
ME: I pretended I was going to meet a customer but it was really to go outside and have a smoke.
SP: Nothing wrong with that...d'you think you suffered enough to deserve heaven?
ME: Yes...I think so.
SP: Gimme an example.
ME: Well, during a business trip to Toronto, I shared a room with the General Manager.
SP: That's sure rough...anything else?
ME: One day I went to the washroom and sat in the booth next to the Collections Manager.
SP: Stop! That's enough! You poor fella. You certainly deserve heaven. Follow me...we'll find you a place to stay.

LE HEAVENLY CORRIDOR
-----------------------------
He leads me down a long corridor, doors on each side. I see one marked "Teachers". I peek inside: it's empty. Didn't get one yet, explains St-Peter...they're all in ****.
A bit further down, I see one marked "Senior Managers' Secretaries". I peek inside: it's full, like I mean, real full. They all make it here automatically, explains St-Peter...they suffered enough.
A bit further down, I see a door marked "Catholics", followed by one marked "Protestants".
ME: Gee, Mr. Peter, I always thought that Protestants didn't go to heaven.
SP: Well, that's true, but only until recently; you see, we just signed a "Free Trade Agreement" with Lucifer.

LES TUTORS
---------------
Then I see one with a big question mark painted on it.
ME: Mr. Peter, who's in there?
SP: We're not sure...they pretend they're too busy to talk to us.
ME: Gee...what do they do?
SP: They seem to spend every day attending their own meetings. Some of them think they know everything. There's even a couple of them that applied for the Big Boss' job.
ME: Wow! Are you serious? And you don't know who they are?
SP: No idea...except they call themselves "Tutors".
ME: That right? I used to deal with a few of them: they sure don't change!
 
I think you're being a little hard on the teachers. :wink:
 
Top