Problem of the Week – Problem 2 Solution – October 30, 2017

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 2^k is no more than n but n is less than 2^k+1. This number k is the greatest integer less than or equal to log₂ n, denoted by floor(log₂ n). Thus n – 2^{floor(log₂ 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 – 2^{floor(log₂ n)} ) + 1.