|
|
|
|
|
|
|
|
|
Josephus Flavius ProblemFollowing is an excerpt from In the general case n men are arranged in a circle which is closed up as individuals are picked out. Beginning anywhere, we continually go round, picking out each mth man until only r are left. Let one of these be the man who originally occupied the pth place. Then had we begun with n + 1 men, he would have originally occupied the (p + m)th place when p + m is not greater than n + 1, and the (p + m - n - 1)th place when p + m is greater than n + 1. Thus, provided there are to be r men left, their original positions are each shifted forwards along the circle m places for each addition of a single man to the original group. Now suppose that with n men the last survivor (r = 1) occupied originally the pth place, and that with n + x men the last survivor occupied the yth place. Then, if we confine ourselves to the lowest value of x which makes y less than m, we have y = (p + mx) - (n + x). Based on this theorem we can, for any specified value of n, calculate rapidly the position occupied by the last survivor of the company. In effect, Tait found the values of n for which a man occupying a given position p, which is less than m, would be the last survivor, and then, by repeated applications of the proposition, obtained the position of the survivor for intermediate values of n. For instance, take the Josephus problem in which m=3. Then we know that the final survivor of 41 men occupied originally the 31st place. Suppose that when there had been (41+x) men, the survivor occupied originally the yth place. Then, if we consider only the lowest value of x which makes y less than m, we have y = (31 + 3x) - (41 + x) = 2x - 10. Now, we have to take a value of x which makes y positive and less than m, that is, in this case equal to 1 or 2. This is x = 6, which makes y = 2. Hence, had there been 47 men, the man last chosen would have originally occupied the second place. Similarly had there been 47+x men, the man would have occupied originally the yth place, where, subject to the same conditions as before, we have y=(2+3x)-(47+x)=2x-45. If x = 23, y = 1. Hence, with 70 men the man last chosen would have occupied originally the first place. Continuing the process, it is easily found that if n does not exceed 2000000 the last man to be taken occupies the first place when n = 4, 6, 9, 31, 70, 105, 355, 799, 1798, 2697, 9103, 20482, 30723, 69127, 155536, 233304, 349956, 524934, or 787401 ; and the second place when n = 2, 3, 14, 21, 47, 158, 237, 533, 1199, 4046, 6069, 13655, 46085, 103691, 1181102, or 1771653. From these results, by repeated applications of the proposition, we find, for any intermediate values of n, the position originally occupied by the man last taken. Thus with 1000 men, the 604th place; with 100000 men, the 92620th place; and with 1000000 men, the 637798th place are those which would be selected by a prudent mathematician in a company subjected to trimation. Similarly if a set of 100 men were subjected to decimation, the last to be taken would be the man originally in the 26th place. Hence, with 227 men the last to be taken would be the man originally in the first place. Modifications of the original problem have been suggested. For instance, let 5 Christians and 5 Turks be arranged round a circle thus, TCTCCTCTCT Suppose that if beginning at the ath man, every hth man is selected, all the Turks will be picked out for punishment; but if beginning at the bth man, every kth man is selected, all the Christians will be picked out for punishment. The problem is to find a, b, h, and k. A solution is a=l, h=11, b=9, k=29. Reference
|
| 28710138 |  |
|