An interesting problem sent by a colleague.
King Arthur wishes to marry off his daughter to one of the knights of his land. Being mathematical of mind she set a problem for the knights...
"I invite all the Knights of the land
Place the seats in a circle numbering them from one
Lets the knights choose their seat
Say to the first "You live"
To the second "Off with your head"
To the third "You live"
To the forth "Off with your head"
And so on until one knight remains
This will be the knight I marry"
Which seat would you choose if you were a knight wishing to marry the princess?
I couldn't visualise the answer. So I tried mapping out the solution manually and after a couple of goes knocked up a Perl script to print out the sequences.
#!/usr/bin/perl use strict;my ($rounds) = $ARGV[0] || 17;
foreach my $size (1..$rounds) { my @list = (1..$size); my $knights = $#list+1; my $finis = 0; my $i = 0;
while (!$finis) { push @list, $list[$i] if ($i+1) % 2 != 0; $i++; $finis = 1 if $#list+1 == $i; } print "For $knights knights, choose position " . $list[$#list] . “n”; }
The position for each group of knights up to group size 35 follows:
For 1 knights, choose position 1 For 2 knights, choose position 1 For 3 knights, choose position 3 For 4 knights, choose position 1 For 5 knights, choose position 3 For 6 knights, choose position 5 For 7 knights, choose position 7 For 8 knights, choose position 1 For 9 knights, choose position 3 For 10 knights, choose position 5 For 11 knights, choose position 7 For 12 knights, choose position 9 For 13 knights, choose position 11 For 14 knights, choose position 13 For 15 knights, choose position 15 For 16 knights, choose position 1 For 17 knights, choose position 3 For 18 knights, choose position 5 For 19 knights, choose position 7 For 20 knights, choose position 9 For 21 knights, choose position 11 For 22 knights, choose position 13 For 23 knights, choose position 15 For 24 knights, choose position 17 For 25 knights, choose position 19 For 26 knights, choose position 21 For 27 knights, choose position 23 For 28 knights, choose position 25 For 29 knights, choose position 27 For 30 knights, choose position 29 For 31 knights, choose position 31 For 32 knights, choose position 1 For 33 knights, choose position 3 For 34 knights, choose position 5 For 35 knights, choose position 7
From this output I deduced the following:
given a number n (the number of knights sitting around the table), find the largest number m less than n that is a power of 2. Then find the n-m+1th odd number and that is the position you should be sitting in.
So for 21 knights, the largest power of 2 less than 21 is 16. 21-16+1 = 6. The 6th odd number is 11 (1, 3, 5, 7, 9, 11). So if there are 21 knights choose position 11.