Consider this brainteaser: You are given a deck of 2000 cards. You are told to take the top card and discard it, while moving the next card to the bottom of the deck. You are supposed to repeat this operation until only 1 card is left – what is the card?

The brute force solution would be to go through the whole algorithm step by step until you find the card you are looking for, which in this case would be card 1952, if we mark our first card as 1 and our last card as 2000. We can check this with a simple computer program:

1
2
3
4
5
6
7
8
9

varcards:[Int]=Array(1...2000)while(cards.count!=1){cards.remove(at:0)cards.append(cards[0])cards.remove(at:0)}print("Last card of deck size 2000: \(cards)");

However, there is a better, completely general solution which can be written as a simple formula which can be done on a standard scientific calculator.

Let’s see what happens when we run our algorithm on deck sizes 1-32:

Last card of deck size 1: 1
Last card of deck size 2: 2
Last card of deck size 3: 2
Last card of deck size 4: 4
Last card of deck size 5: 2
Last card of deck size 6: 4
Last card of deck size 7: 6
Last card of deck size 8: 8
Last card of deck size 9: 2
Last card of deck size 10: 4
Last card of deck size 11: 6
Last card of deck size 12: 8
Last card of deck size 13: 10
Last card of deck size 14: 12
Last card of deck size 15: 14
Last card of deck size 16: 16

It does not take a Phd to figure out a simple pattern: when the deck size \(x\) can be written as a power of two, the last card of the deck of size \(x\) will be \(x\). We also can see that if \(x\) is a power of two, the last card of deck size \(x+1\) is two, the last card of deck size \(x+2\) is four, etc., until \(x+i\) is another power of two. Then the last card of \(x+i\), given that \(x+i\) is not a power of two, \(2i\). Thus, we can say that for a given \(n\) that is not a power of two, the last card of the deck will be \(2(n-floor(log_2(n)))\), where \(floor(log_2(n))\) is the last occuring power of two.