Solution to Cards of the Round Table
Correct solutions were submitted by: Rui Bi
First consider the case when the number of cards is a power of two. For example, if n is 8, then the first time around the table you remove 2, 4, 6, and 8. At this time you are at card number 1, and the rest of the problem can be considered as an original problem but with n = 4. We deduce that, in general, if the number of cards is a power of two, then the final remaining card is number 1.
For the general problem, go around the table removing cards until the first time the number of cards remaining is a power of two. From the preceding analysis, we know that the card where we are standing will be the final remaining card.
To actually find the card number, we first find the integer k such that 2k is no more than n but n is less than 2k+1. This number k is the greatest integer less than or equal to log2 n, denoted by floor(log2 n). Thus n – 2floor(log2 n)is the number of cards that have been removed. We have removed cards with even numbers, so we are at the card with the odd number
2(n – 2floor(log2 n) ) + 1.