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.