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?
[edit: This post is incorrect, I had a flaw in the main algorithm. Thanks to Charlie for pointing out the error. See new post above for corrected algorithm and results. Curiously, despite the error, "Strategy 1" remains intact]
------------ Incorrect Below Here ----------------
I found that the algorithm spares either 1, 2, or 3 prisoners depending on the starting number, N. When more than one is spared, they are always adjacent to each other. Romulus can be spared about 2/3 of the time.
I found two winning strategies.
Strategy 1:
To save one person, when there are N prisoners: be in position
N - (int(log(n) - 1) (where log is to base 2)
When N results in 1 life spared, Maximus is saved. When 3 are saved, Maximus is in the middle of the 3. When 2 are saved, Max is sometimes the larger number and sometimes the smaller.
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.
Strategy 2:
The largest number position of those spared is N-k, where k is a complicated function of N. First use the following formula to find the smallest N such that the largest position of those spared is N-k: 2^(k+2) - 2^k - 2.
i smallestN(i)
1 4
2 10
3 22
4 46
5 94
6 190
Maximus then compares N to this table, for example if N=50, he sees that 50 is larger than 46 but smaller than 94, so k=4. So Maximus would go to position 46 and Romulus just in front of him at position 45.
Program output:
N [saved] Strgy1 k
4 [3] 3 1
5 [4] 4 1
6 [4, 5] 5 1
7 [5, 6] 6 1
8 [5, 6, 7] 6 1
9 [6, 7, 8] 7 1
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 [14, 15, 16] 15 2
19 [15, 16, 17] 16 2
20 [16, 17, 18] 17 2
21 [17, 18, 19] 18 2
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 [33, 34, 35] 34 3
39 [34, 35, 36] 35 3
40 [35, 36, 37] 36 3
41 [36, 37, 38] 37 3
42 [37, 38, 39] 38 3
43 [38, 39, 40] 39 3
44 [39, 40, 41] 40 3
45 [40, 41, 42] 41 3
46 [42] 42 4
47 [43] 43 4
48 [44] 44 4
49 [45] 45 4
50 [46] 46 4
----------------------
import math
def calculateK(n):
return int(math.log(n,2)) - 1
def smallestN(k):
return 2**(k+2) - 2**k - 2
def wholives(N):
peeps = [i for i in range(1,N+1)]
executed = []
for round in range(1000):
remain = len(peeps)
if remain > 3:
leaving = int(remain/2 + (remain%2)/2)
executed += peeps[:leaving]
peeps = peeps[leaving:]
executed.append(peeps.pop(-1))
else:
return peeps
remain = len(peeps)
if remain < 3:
return peeps
break
for n in range(4,51):
who = wholives(n)
print(n, who, n - calculateK(n), n - who[-1])
Edited on April 22, 2024, 5:17 pm
|
|
Posted by Larry
on 2024-04-20 10:26:04 |
Solution
