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

Home > Just Math
An old one (Posted on 2011-05-02) Difficulty: 3 of 5
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.)
Solution 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             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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information