Maximus is one of 3 or more prisoners of war who have been lined up before the Roman Emperor. The prisoners are numbered from first in the line to last as 1, 2, 3, 4, ..., N. The Emperor orders the execution of the prisoners in the following manner:
1) The first and last are immediately executed.
2) If there are still 2 or more prisoners remaining, the half of the remaining prisoners with the lowest numbers (rounded up) are executed.
3) If there are still 3 or more prisoners remaining, start again from Step 1.
For example, if there were 5 prisoners to start then prisoners 1 and 5 would be executed in Step 2, and prisoners 2 and 3 would be executed in Step 3, leaving prisoner 4 alive.
Is there a strategy by which Maximus can save himself? What if Maximus also wants to save his friend Romulus?
(In reply to
re: Solution by Charlie)
This is a correction to my earlier post. My main algorithm was simply wrong; but now corrected.
The first strategy description, however, remains successful in predicting a safe location for Maximus and Romulus with the same variation of whether Romulus should stand immediately in front of or behind Maximus.
Maximus' safe spot is at N - k, where k = int(log(k)) - 1 (log is to the base 2)
The best place for Romulus is adjacent to Maximus:
if N is exactly a power of 2 or slightly more, put Romulus behind Max
if N is a little less than a power of 2, put Romulus just in front of Max.
However, only 1 prisoner is spared for roughly 60% to 75% of the time for random choices for N.
The second strategy to identify either the sole position which is safe, or the larger number of the two safe positions (so that Romulus would always stand in front of Maximus) still exists but with a different table of numbers.
i smallestN(i)
1 3
2 8
3 18
4 38
5 78
6 158
7 318
8 638
9 1278
f(i+1) = 2*f(i)+2
(this is one off of the oeis sequence Charlie noted; he was finding the last block of 2 saved and I was finding the first in the next block of 1 saved)
So if for example N is between 38 and 77, k=4, Maximus stands at N-4, Romulus at N-5.
There is a clear pattern in this table s.t. each entry is the prior entry times 2, then plus 2.
Program output
4 [3] 3 1
5 [4] 4 1
6 [4, 5] 5 1
7 [5, 6] 6 1
8 [6] 6 2
9 [7] 7 2
10 [8] 8 2
11 [9] 9 2
12 [10] 10 2
13 [11] 11 2
14 [11, 12] 12 2
15 [12, 13] 13 2
16 [13, 14] 13 2
17 [14, 15] 14 2
18 [15] 15 3
19 [16] 16 3
20 [17] 17 3
21 [18] 18 3
22 [19] 19 3
23 [20] 20 3
24 [21] 21 3
25 [22] 22 3
26 [23] 23 3
27 [24] 24 3
28 [25] 25 3
29 [26] 26 3
30 [26, 27] 27 3
31 [27, 28] 28 3
32 [28, 29] 28 3
33 [29, 30] 29 3
34 [30, 31] 30 3
35 [31, 32] 31 3
36 [32, 33] 32 3
37 [33, 34] 33 3
38 [34] 34 4
39 [35] 35 4
40 [36] 36 4
41 [37] 37 4
42 [38] 38 4
43 [39] 39 4
44 [40] 40 4
45 [41] 41 4
46 [42] 42 4
47 [43] 43 4
48 [44] 44 4
49 [45] 45 4
50 [46] 46 4
-------- corrected code below -----
def wholives(N):
peeps = [i for i in range(1,N+1)]
executed = []
for round in range(1000):
remain = len(peeps)
if remain >= 3:
executed.append(peeps[0])
executed.append(peeps[-1])
peeps = peeps[1:-1]
remain = len(peeps)
if remain > 1:
leaving = int(remain/2 + (remain%2)/2)
executed += peeps[:leaving]
peeps = peeps[leaving:]
else:
return peeps
remain = len(peeps)
if remain < 3:
return peeps
break
|
|
Posted by Larry
on 2024-04-22 17:14:06 |
re(2): Solution Corrected program
