N men are sitting at a round table.
Starting with the one sitting in seat #2 every other one is removed .
Who is the last one left at the table?
Form a table for N=2, 3, 4, ... 20
FOR n = 2 TO 20
REDIM seat(n)
FOR i = 1 TO n
seat(i) = 1
NEXT
p = 2
FOR i = 1 TO n - 1
seat(p) = 0
ct = 0
DO
p = p + 1
IF p > n THEN p = 1
IF seat(p) = 1 THEN
ct = ct + 1
IF ct = 2 THEN EXIT DO
END IF
LOOP
NEXT i
FOR i = 1 TO n
IF seat(i) THEN
PRINT n, i
END IF
NEXT
NEXT n
n seat# of last man
2 1
3 3
4 1
5 3
6 5
7 7
8 1
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1
17 3
18 5
19 7
20 9
When n is a power of 2, the last man remaining is in seat #1. Otherwise (and also in the power of 2 case) the last man is 2*n' + 1, where n' is n minus the highest power of 2 that's less than or equal to n.
Formalized, that's 2*(n-2^[lb(n)]) + 1, where the square brackets indicate the floor function and lb(n) is the base-2 logarithm of n.
A modified program shows the sequence of removal:
n removal sequence (seat numbers) remains
2 2 1
3 2 1 3
4 2 4 3 1
5 2 4 1 5 3
6 2 4 6 3 1 5
7 2 4 6 1 5 3 7
8 2 4 6 8 3 7 5 1
9 2 4 6 8 1 5 9 7 3
10 2 4 6 8 10 3 7 1 9 5
11 2 4 6 8 10 1 5 9 3 11 7
12 2 4 6 8 10 12 3 7 11 5 1 9
13 2 4 6 8 10 12 1 5 9 13 7 3 11
14 2 4 6 8 10 12 14 3 7 11 1 9 5 13
15 2 4 6 8 10 12 14 1 5 9 13 3 11 7 15
16 2 4 6 8 10 12 14 16 3 7 11 15 5 13 9 1
17 2 4 6 8 10 12 14 16 1 5 9 13 17 7 15 11 3
18 2 4 6 8 10 12 14 16 18 3 7 11 15 1 9 17 13 5
19 2 4 6 8 10 12 14 16 18 1 5 9 13 17 3 11 19 15 7
20 2 4 6 8 10 12 14 16 18 20 3 7 11 15 19 5 13 1 17 9
|
|
Posted by Charlie
on 2011-05-02 15:15:38 |
computer solution
