Hello everyone. Well, I was reading this math puzzle question, and I came across this really annoying puzzle. The book doesn''t give the answers. It goes something like this: King Arthur had a beautiful daughter (he didn''t really, but thats ok). Arthur said that he would call in his knights in to sit. Then he would pick every other knight and have him killed. He would keep on doing this until there would only be one knight left. This is assuming that there would be a different number of knights every day. How could one know exactly where to sit if he didn''t know in advance how many knights there would be? I know this isn''t really game related, but if it really bothers you so much, I''ll write a little game for it, OK? So it would kind of look like this ( if there were 12 knights present): 9 1 8 2 7 3 6 4 5 Then 2, 4, 6, 8 would die on the first iteration. Then 1, 3, 5, 7 would die, and 9 nine would be the last one alive. Can anyone help me come up with a formula for where to sit? Thanks...

quote: Original post by Sheep

So it would kind of look like this ( if there were 12 knights present):

9 1
8 2
7 3
6 4
5

Then 2, 4, 6, 8 would die on the first iteration. Then 1, 3, 5, 7 would die, and 9 nine would be the last one alive. Can anyone help me come up with a formula for where to sit? Thanks...

Let's ignore the obvious point that there are only 9 Knights in your example! ;-)

I also suspect you have misinterpreted the puzzle. After the first day, then there would be Knights seated at positions 1,3,5,...,n1-1, where n1 is the number of Knights present on day one (if n1 is even) or at positions 1,3,5,...,n1 if there is an odd number of Knights on the first day.

Now, on that second day King Arthur once again kills off every second Knight. That would be Knights 3,7,11,...,n2-1 (if n2 is even) or 3,7,11,...,n2 if n2 is odd.

On the third day, Knights 7,13,17,...,n3-1 die out for even n3 (or 7,13,17,...,n3 if n3 is odd).

So, the picture we are seeing looks like this... at the beginning of each day we have the following arrangement of Knights:

Day 1: 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18..
Day 2: 1....3....5....7....9......11......13......15......17.....
Day 3: 1..........5..........9...............13..................17....
Day 4: 1.....................9...................................17.....
Day 5: 1.......................................................17.....

It is quite clear that if every second Knight is executed then the Knight in position 1 will always be overlooked and will be the winner. This of course relies on several assumptions:

1) That King Arthur always starts counting from the same place every day;
2) That Knights must always take up the same seat they sat in on day 1;
3) That 'killing every second knight' means 'killing every Knight seated in every second seat counted from seat number 1'.

Since King Arthur sat at the 'number 1 spot' of the round table (since he was King) then every other Knight dies and his daughter remains virtuous! ;-)

Cheers,

Timkin

Edited by - Timkin on September 17, 2001 10:56:47 PM

Sorry...I didn''t really make myself clear... the killing of the knights all happens on one day...lets say tomorrow... the problem is that the knight who doesnt want to get killed must know where to sit even when he doesnt know how many knights would be present. Also, I am assuming king arthur isn''t sitting down, and that he always starts counting from place "1" which is "set in stone". So if there are 9 knights "tomorrow", then the knight sitting in place 9 would live. On the other hand, if there were just so happened to be 4 knights, then number one would stay alive. If you want to, you can email me at: slimy8704@hotmail.com

Okay, I have figured out the puzzle and I have an answer!

To make sure I have the puzzle straight:

All Knights walk in and sit down around the table. Starting at position 1 King Arthur kills every second Knight. This would mean, if there were say 11 Knights, that he would kill them in the following order: 2,4,6,8,10,1,5,9,3,11 so the Knight in position 7 lives. That is, he has kept going around the table and killing every second Knight he comes to.

The winner is given in the following table. Counting from the first element gives the number of knights who sat down at the start of the exectution!


1
1 3
1 3 5 7
1 3 5 7 9 11 13 15
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
1 3...

Each row of the table is double the length of the previous row.

To find out where to sit..... the Knight who wants to win must observe how many seats there are (and quickly!). (If he does not know how many knights are entering the room, then he is stuffed and cannot solve the problem exactly). Then, find the largest number m such that 2m < n, where n is the number of seats at the table (assumed there are as many Knights as seats).

Then, compute p = n - (2m-1).

The Knight should then sit in the 'p'th odd position. So, if there are 12 chairs at the table, then m = 3 (because 23 < 12 < 24. Hence, p = 12 - (23 - 1) = 5. Thus, the 5th odd position is position seat number 9.


On the consideration that the Knight has no information with which to solve the puzzle (ie he has no idea how many knights are in the puzzle and how many seats ... but there are at least as many seats as Knights, then to maximise his probability of survival, he must sit in seat number 1. This is because this seat wins more than any other seat.

Hope this is what you are after.

Cheers,

Timkin

Edited by - Timkin on September 17, 2001 11:42:40 PM

Yes!!! Thats it! Now I can burn the damn book! Thanks alot
Just one last question...I don't really get how you came up with that formula...could you maybe explain to me how you came up with it(Yes, I'm stupid )? Thanks again...

Edited by - Sheep on September 18, 2001 11:43:36 AM

Mmm, how did I solve it and come up with the equation? Well, in part because I am a mathematician by training, so I have some knowledge of this sort of thing. But, basically I did the following:

First, I analysed several trials to see if there was a pattern. I started to see a pattern so then I expanded on sufficient trials to flesh out exactly what the pattern was. Once I thought I knew what the pattern was, I tested it and found that it was correct.

Since there was a pattern then there must by definition be an algorithm for computing a value in the pattern, given its position in the pattern.

To find the algorithm, I layed out the table which showed the winning seat number for a given number of knights. Given that there is a pattern, there is a way of organising the table to reflect this pattern, which is the table that I put in my post.
I was then able to better visualise the pattern and look at relationships among the different rows and columns. In this case, one important relationship was that every row contained twice as many elements as the previous row and there was 1 element in the first row. This was the crucial factor in determining a formula for working out the winning seat number given the number of knights.

I''m now going to refer to a game as an instance of the puzzle with a certain number of knights in it. So, game 10 would be the puzzle with 10 knights participating. The winning value of such a game is the seat number of the winner.

What I needed to know was how far from the start of a row was a particular game so I could then work out which value in the sequence of odd numbers was the winning value related to a particular game.

It turned out that the first element in each row followed the sequence 0,2,4,8,16,32,... = 20,21,22,23,24,25,...
This can be deduced from the requirement that the first row has 1 element and all subsequent rows have double the number of elements of the previous row. Or by counting.

So, the first element in a row had the game number of 2m, where m turns out to be the number of rows before the current one. This means that there were 2m-1 elements in all previous rows. Subtracting those from the current game number gave the offset from the start of the current row. This offset p then means that the p''th element of the set of odd numbers is the winning value.

I hope this helps...

It''s not overly clear, but I can try and elaborate a little better if you so desire.

Cheers,

Timkin