All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 An old one (Posted on 2011-05-02)
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

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution Comment 1 of 1

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             13             34             15             36             57             78             19             310            511            712            913            1114            1315            1516            117            318            519            720            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)                                     remains2   2                                                                       13   2  1                                                                    34   2  4  3                                                                 15   2  4  1  5                                                              36   2  4  6  3  1                                                           57   2  4  6  1  5  3                                                        78   2  4  6  8  3  7  5                                                     19   2  4  6  8  1  5  9  7                                                  310  2  4  6  8  10  3  7  1  9                                              511  2  4  6  8  10  1  5  9  3  11                                          712  2  4  6  8  10  12  3  7  11  5  1                                      913  2  4  6  8  10  12  1  5  9  13  7  3                                   1114  2  4  6  8  10  12  14  3  7  11  1  9  5                               1315  2  4  6  8  10  12  14  1  5  9  13  3  11  7                           1516  2  4  6  8  10  12  14  16  3  7  11  15  5  13  9                      117  2  4  6  8  10  12  14  16  1  5  9  13  17  7  15  11                  318  2  4  6  8  10  12  14  16  18  3  7  11  15  1  9  17  13              519  2  4  6  8  10  12  14  16  18  1  5  9  13  17  3  11  19  15          720  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

 Search: Search body:
Forums (0)