Gizmodo Monday Puzzle: This Counterintuitive Card Puzzle Will Make You Flip

Announcement: The Gizmodo Monday Puzzle is going on a summer hiatus. Look out for us again in the fall! Follow me on Twitter to stay up to date about the series and for more puzzles, math, and other curiosities.

Apple’s Bigger-Screen 15-inch MacBook Air | Gizmodo Review

There is a famous problem in math called The Secretary Problem. You are hiring for a job at your company, and you will interview n people, one at a time. Through the interviews, you are able to rank each candidate in order relative to the other candidates you’ve seen so far (meaning if you’ve already met with five people, then you know which one was the best of the five, which was second best, and so on). The trouble is, after each interview, you must decide on the spot whether you want to hire that candidate or to reject them and continue the process, risking never meeting someone that qualified again. What is the optimal strategy to maximize your chance of hiring the best applicant?

The problem is famous for at least two reasons. One is that the optimal strategy gives you impressively good chances of finding the best candidate. The other is that mathematicians’ favorite little constant makes a surprise appearance in the solution: e.

Euler’s number, e, is about 2.7182 and is renowned for cropping up everywhere in seemingly disparate areas of math. You might have encountered e in calculus class, or if you’ve enjoyed compound interest on your investments, or ever looked at a bell curve, or suffered bacteria growth, or had shock absorbers on your bike/car, or let your coffee cool. As mathematical constants go, pi enjoys celebrity status, with its own holiday and contests for memorizing its digits. Meanwhile, e is the modest workhorse of the physical world, dutifully holding everything together in the background, too dignified for limelight.

Here’s the solution to The Secretary Problem: Always reject the first 1/e fraction of candidates out of hand (the first ~37% of applicants). After that, hire the first candidate you meet who is better than every other one you’ve met so far (if you never meet such a candidate, tough luck). Amazingly, this simple strategy gives you a roughly 37% (again, 1/e) chance of finding the best candidate, regardless of how many applicants there are. Even with millions of applicants, you have a better than one in three chance of finding the top one among them! Psychological research suggests that when people are faced with real-life secretary problems, they tend to curtail their search prematurely, leading to suboptimal outcomes. So next time you’re hunting for the cheapest gas on the highway or deciding whether to apply for an apartment vs. continuing your search, consider applying the secretary problem approach and seeking for a little longer than you might normally be inclined.

There is a whole rich theory focused solely on stopping rules, i.e., when to stop a process to achieve a desired goal. This week’s Gizmodo Monday Puzzle doesn’t involve Euler’s number or advanced math of any kind, but it does ask you when to stop.

Did you miss last week’s puzzle? Check it out here, and find its solution at the bottom of today’s article. Be careful not to read too far ahead if you haven’t solved last week’s yet!

Puzzle #16: Turning Red

You shuffle a normal deck of cards face down and then begin to flip over cards from the top of the deck, one at a time, placing them face up on a table. At any time (but only once), you can choose to stop, and if the next card is red, then you win. If you never stop, then by default you’re forced to choose the last card (again, you win if it’s red). Is there a strategy that maximizes your chance of winning this game? If so, what is it? If not, why not? You must shuffle the cards thoroughly and are not allowed to cheat in any way (like by marking cards). You may only observe the cards that you flip and choose when to stop.

Scroll down for the solution.

Solution to Puzzle #15: Spell It Out

Last week, I gave you a novel way to look at numbers. Let’s take them one by one.

Solution to Puzzle #16: Turning Red

Many people have a strong intuition that they can achieve an edge in this game. A common idea is to stop as soon as there are more red cards remaining in the deck than black cards. The surprising twist is that there is no strategy that gives you better than a 50/50 chance of stopping on a red card. In fact, no strategy gives you a worse than 50/50 chance either. Cook up any wacky scheme you like, and it will have no effect.

A slick way to see this is to consider the following admittedly pointless game. We’ll have the same setup: a shuffled deck, flipping over one card at a time, and stopping whenever you please, except this time when you stop, you look at the bottom card of the deck instead of the top. If it’s red, you win. The bottom card never changes and is fixed as either red or black from the start, so clearly any strategy to beat a 50/50 chance in this game is doomed. The key observation is that the probabilities in our original game are identical at every step to the probabilities in this silly variant game. Stop flipping at any point—is it any more likely that the top card in the deck is red than the bottom card? Maybe at certain times there is a greater than 50% chance that the top card is red, but at such times there is also an equivalent chance that the bottom card is red, or any of the remaining cards for that matter. So regardless of when you stop, you can’t do any better than a game where you merely shuffle the cards and then peek at the bottom one, which will only be red half of the time.