There are 100 face-down cards. The first person that passes by flips over every card, the 2nd person that passes by flips over every 2nd card, and so forth – the n-th person that passes by flips over every n-th card. Before you know it, 100 people have passed by.
After all 100 people have passed by, which cards are face-up and which are face-down?
Fun fact, this was an actual brainteaser given to me in the first round interview for a hedge fund internship back in 2011.
Preparing for a brain teaser interview? Check out our ultimate guide to brain teaser interviews.
Solution
You might individually work through the first couple of cards: 1st card will only be flipped by 1st person, 2nd card will be flipped by 1st and 2nd person, 3rd card will be flipped by 1st and 3rd person, 4th card will be flipped by 1st, 2nd, and 4th person, etc. From this, two insights may be gathered:
- The n-th card will be flipped by all the factors of n.
- By definition, each factor of a number must be multiplied by another factor to get to the number, so the factors are paired. This means for every flip by a factor there is a corresponding flip by another factor – with the exception of perfect squares. For perfect squares, one of the factors is the corresponding factor to itself, so there is no corresponding flip.
This means that all cards will be flipped an even number of times and end up face-down, except for perfect squares, which will end up face-up.