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?
clearvars,clc
for n=1:350
remain=n;
prisoners=1:remain;
while remain>=3
n2=remain;
prisoners(1)=[];
prisoners(end)=[];
remain=length(prisoners);
if remain>=2
idx=1:ceil(remain/2);
prisoners(idx)=[];
end
remain=length(prisoners);
end
disp([n remain prisoners])
end
at the end
N number remaining
remaining prisoners
identifications
1 1 1
2 2 1 2
3 1 2
4 1 3
5 1 4
6 2 4 5
7 2 5 6
8 1 6
9 1 7
10 1 8
11 1 9
12 1 10
13 1 11
14 2 11 12
15 2 12 13
16 2 13 14
17 2 14 15
18 1 15
19 1 16
20 1 17
21 1 18
22 1 19
23 1 20
24 1 21
25 1 22
26 1 23
27 1 24
28 1 25
29 1 26
30 2 26 27
31 2 27 28
32 2 28 29
33 2 29 30
34 2 30 31
35 2 31 32
36 2 32 33
37 2 33 34
38 1 34
39 1 35
40 1 36
41 1 37
42 1 38
43 1 39
44 1 40
45 1 41
46 1 42
47 1 43
48 1 44
49 1 45
50 1 46
51 1 47
52 1 48
53 1 49
54 1 50
55 1 51
56 1 52
57 1 53
58 1 54
59 1 55
60 1 56
61 1 57
62 2 57 58
63 2 58 59
64 2 59 60
65 2 60 61
66 2 61 62
67 2 62 63
68 2 63 64
69 2 64 65
70 2 65 66
71 2 66 67
72 2 67 68
73 2 68 69
74 2 69 70
75 2 70 71
76 2 71 72
77 2 72 73
78 1 73
79 1 74
80 1 75
81 1 76
82 1 77
83 1 78
84 1 79
85 1 80
86 1 81
87 1 82
88 1 83
89 1 84
90 1 85
91 1 86
92 1 87
93 1 88
94 1 89
95 1 90
96 1 91
97 1 92
98 1 93
99 1 94
100 1 95
101 1 96
102 1 97
103 1 98
104 1 99
105 1 100
106 1 101
107 1 102
108 1 103
109 1 104
110 1 105
111 1 106
112 1 107
113 1 108
114 1 109
115 1 110
116 1 111
117 1 112
118 1 113
119 1 114
120 1 115
121 1 116
122 1 117
123 1 118
124 1 119
125 1 120
126 2 120 121
127 2 121 122
128 2 122 123
129 2 123 124
130 2 124 125
131 2 125 126
132 2 126 127
133 2 127 128
134 2 128 129
135 2 129 130
136 2 130 131
137 2 131 132
138 2 132 133
139 2 133 134
140 2 134 135
141 2 135 136
142 2 136 137
143 2 137 138
144 2 138 139
145 2 139 140
146 2 140 141
147 2 141 142
148 2 142 143
149 2 143 144
150 2 144 145
151 2 145 146
152 2 146 147
153 2 147 148
154 2 148 149
155 2 149 150
156 2 150 151
157 2 151 152
158 1 152
159 1 153
160 1 154
161 1 155
162 1 156
163 1 157
164 1 158
165 1 159
166 1 160
167 1 161
168 1 162
169 1 163
170 1 164
171 1 165
172 1 166
173 1 167
174 1 168
175 1 169
176 1 170
177 1 171
178 1 172
179 1 173
180 1 174
181 1 175
182 1 176
183 1 177
184 1 178
185 1 179
186 1 180
187 1 181
188 1 182
189 1 183
190 1 184
191 1 185
192 1 186
193 1 187
194 1 188
195 1 189
196 1 190
197 1 191
198 1 192
199 1 193
200 1 194
201 1 195
202 1 196
203 1 197
204 1 198
205 1 199
206 1 200
207 1 201
208 1 202
209 1 203
210 1 204
211 1 205
212 1 206
213 1 207
214 1 208
215 1 209
216 1 210
217 1 211
218 1 212
219 1 213
220 1 214
221 1 215
222 1 216
223 1 217
224 1 218
225 1 219
226 1 220
227 1 221
228 1 222
229 1 223
230 1 224
231 1 225
232 1 226
233 1 227
234 1 228
235 1 229
236 1 230
237 1 231
238 1 232
239 1 233
240 1 234
241 1 235
242 1 236
243 1 237
244 1 238
245 1 239
246 1 240
247 1 241
248 1 242
249 1 243
250 1 244
251 1 245
252 1 246
253 1 247
254 2 247 248
255 2 248 249
256 2 249 250
257 2 250 251
258 2 251 252
259 2 252 253
260 2 253 254
261 2 254 255
262 2 255 256
263 2 256 257
264 2 257 258
265 2 258 259
266 2 259 260
267 2 260 261
268 2 261 262
269 2 262 263
270 2 263 264
271 2 264 265
272 2 265 266
273 2 266 267
274 2 267 268
275 2 268 269
276 2 269 270
277 2 270 271
278 2 271 272
279 2 272 273
280 2 273 274
281 2 274 275
282 2 275 276
283 2 276 277
284 2 277 278
285 2 278 279
286 2 279 280
287 2 280 281
288 2 281 282
289 2 282 283
290 2 283 284
291 2 284 285
292 2 285 286
293 2 286 287
294 2 287 288
295 2 288 289
296 2 289 290
297 2 290 291
298 2 291 292
299 2 292 293
300 2 293 294
301 2 294 295
302 2 295 296
303 2 296 297
304 2 297 298
305 2 298 299
306 2 299 300
307 2 300 301
308 2 301 302
309 2 302 303
310 2 303 304
311 2 304 305
312 2 305 306
313 2 306 307
314 2 307 308
315 2 308 309
316 2 309 310
317 2 310 311
318 1 311
319 1 312
320 1 313
321 1 314
322 1 315
323 1 316
324 1 317
325 1 318
326 1 319
327 1 320
328 1 321
329 1 322
330 1 323
331 1 324
332 1 325
333 1 326
334 1 327
335 1 328
336 1 329
337 1 330
338 1 331
339 1 332
340 1 333
341 1 334
342 1 335
343 1 336
344 1 337
345 1 338
346 1 339
347 1 340
348 1 341
349 1 342
350 1 343
Some values of N have two survivors, others only one.
The blocks of N that have 2 survivors seem to end in N matching OEIS's A154117, Expansion of (1 - x + 3*x^2)/((1-x)*(1-2*x)), and those blocks increase in size by a factor of 2 each occurrence.
At the end of each block, the primary safe place moves farther back from the end by one. The secondary safe space is always just before the primary one, allowing Romulus to survive also.
|
|
Posted by Charlie
on 2024-04-20 11:06:56 |
computer solution
