Can You Ace the Technical Interview?

If you can, then I have an even trickier question for you to work on. (Come to think of it, that’s kind of how technical interviews go.)

Welcome to Fiddler on the Proof! The Fiddler is the spiritual successor to FiveThirtyEight’s The Riddler column, which ran for eight years under the stewardship of myself and Ollie Roeder.

Each week, I present mathematical puzzles intended to both challenge and delight you. Beyond these, I also hope to share occasional writings about the broader mathematical and puzzle communities.

Puzzles come out Friday mornings (8 a.m. Eastern time). Most can be solved with careful thought, pencil and paper, and the aid of a calculator. Many include “extra credit,” where the analysis gets particularly hairy or where you might turn to a computer for assistance.

I’ll also give a shoutout to 🎻 one lucky winner 🎻 of the previous week’s puzzle, chosen randomly from among those who submit their solution before 11:59 p.m. the Monday after that puzzle was released. I’ll do my best to read through all the submissions and give additional shoutouts to creative approaches or awesome visualizations, the latter of which could receive 🎬 Best Picture Awards 🎬.

This Week’s Fiddler

Here’s a puzzle I once heard from a colleague, who was in turn asked it at a job interview:

Starting with a line segment of length 1, randomly split it somewhere along its length into two parts. Compute the product of these two lengths. Then take each of the two resulting segments and repeat the process. That is, for each one, randomly split it somewhere along its length into two parts and compute the product. Then do this for all four resulting segments, then the eight after that, and the 16 after that, and so on.

After doing this (forever), you add up all the products you computed throughout. On average, what value would you expect this sum to approach?

This Week’s Extra Credit

After originally hearing (and solving) this week’s Fiddler oh so many years ago, I had an Extra Credit for it in mind that took me a while to sort out. I think I’ve finally got it nailed down, so here goes nothing:

Another way to describe this week’s Fiddler is with a recursive function f, defined by f(L) = ab + f(a) + f(b). Here, a and b are random values between 0 and L, such that a + b = L. The question asked above is this: On average, what value does f(1) approach?

For Extra Credit, we’ll be splitting segments into three parts rather than two. So let’s define a new function g(L). But wait! We don’t have g(L) = abc + g(a) + g(b) + g(c), like you might have expected.

Instead, I’d like to introduce a slightly messier recursive definition: g(L) = abc + g(a+b) + g(a+c) + g(b+c) − g(a) − g(b) − g(c). Here, a, b, and c are random values between 0 and L such that a + b + c = L.

On average, what value does g(1) approach?

Making the Rounds

There’s so much more puzzling goodness out there, I’d be remiss if I didn’t share some of it here. This week, I’m sharing a mysterious fact I recently encountered: If you sum the first 500,000 terms of the Leibniz formula for 𝜋, i.e., 4(1/1 − 1/3 + 1/5 − 1/7 + … − 1/999,999), is equal to 3.141590653589793240462643383269502884197…

Sure, this approximates 𝜋 to five places after the decimal point, but that’s not what’s interesting here. After the first incorrect decimal (the “0” in the sixth decimal place), the next 10 decimals are correct! And while the next two decimals after that are incorrect, the next 10 decimals are again correct! And while the next decimal after that are incorrect, the next 10 decimals are—you guessed it—correct! All in all, that’s 36 correct decimals among the first 40.

To learn more about this incredible “coincidence,” check out this 1989 article from The American Mathematical Monthly.

Want to Submit a Puzzle Idea?

Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email. I love it when ideas also come with solutions, but that’s not a requirement.

Last Week’s Fiddler

Congratulations to the (randomly selected) winner from last week: 🎻 Jordan Rader 🎻 from Hampstead, North Carolina. I received 61 timely submissions, of which 44 were correct—good for a 72 percent solve rate.

Last week, you were playing a modified version of blackjack, where the deck consisted of exactly 10 cards numbered 1 through 10. Unlike traditional blackjack, in which the ace could count as 1 or 11, the 1 here always had a value of 1.

You shuffled the deck so the order of the cards was completely random, after which you drew one card at a time. You kept drawing until the sum of your drawn cards was at least 21. If the sum was exactly 21, you won! But if the sum was greater than 21, you “busted,” or lost. 

What were your chances of winning, that is, of drawing a sum that is exactly 21?

First off, how many different ways were there to order the 10 cards? There were 10 possible values for the first card, 9 remaining values for the second card, 8 for the third card, and so on. Altogether, that meant there were 10·9·8·7·6·5·4·3·2·1 (commonly written as 10!), or 3,628,800 orderings.

As an aside, the number of ways to order a 52-card deck is 52!, a number so large that if you randomly shuffle a deck, you’d be the only person in human history to encounter that specific ordering. If a deck had 60 unique cards instead of 52, the number of possible orderings (60!) would exceed the number of protons in the observable universe.

Anyway, of these 10! orderings, how many resulted in a sum of 21? Solvers like Dennis Okon found all such ways. First off, 21 was equal to the sum of the smallest six cards, which meant you needed at most six cards. Here were those six cards:

• 1, 2, 3, 4, 5, 6

You could win the game by having these six cards come first in the deck (in one of 6! possible orderings), followed by the remaining four cards (in one of 4! possible orderings). This accounted for 6!·4!, or 17,280 orderings of the deck that resulted in victory.

Dennis also found nine ways to make 21 using five cards:

• 1, 2, 3, 5, 10

• 1, 2, 3, 6, 9

• 1, 2, 3, 7, 8

• 1, 2, 4, 5, 9

• 1, 2, 4, 6, 8

• 1, 2, 5, 6, 7

• 1, 3, 4, 5, 8

• 1, 3, 4, 6, 7

• 2, 3, 4, 5, 7

You could win the game by having these five cards come first in the deck (in one of 5! possible orderings), followed by the remaining five cards (in one of 5! possible orderings). These nine cases collectively accounted for 9·5!·5!, or 129,600 victorious orderings.

Next, Dennis found 16 ways to make 21 using four cards:

• 1, 2, 8, 10

• 1, 3, 7, 10

• 1, 3, 8, 9

• 1, 4, 6, 10

• 1, 4, 7, 9

• 1, 5, 6, 9

• 1, 5, 7, 8

• 2, 3, 6, 10

• 2, 3, 7, 9

• 2, 4, 5, 10

• 2, 4, 6, 9

• 2, 4, 7, 8

• 2, 5, 6, 8

• 3, 4, 5, 9

• 3, 4, 6, 8

• 3, 5, 6, 7

You could win the game by having these four cards come first in the deck (in one of 4! possible orderings), followed by the remaining six cards (in one of 6! possible orderings). These 16 cases collectively accounted for 16·4!·6!, or 276,480 victorious orderings.

Finally Dennis found seven ways to make 21 using three cards:

• 2, 9, 10

• 3, 8, 10

• 4, 7, 10

• 4, 8, 9

• 5, 6, 10

• 5, 6, 9

• 6, 7, 8

You could win the game by having these three cards come first in the deck (in one of 3! possible orderings), followed by the remaining seven cards (in one of 7! possible orderings). These seven cases collectively accounted for 7·3!·7!, or 211,680 victorious orderings.

Since the highest card was 10, you needed at least three cards to make 21, which meant the 33 above ways to make 21 were all the ways to make 21.

Altogether, you had 17,280 + 129,600 + 276,480 + 211,680 winning orderings of the deck, for a grand total of 635,040 orderings. Your chances of winning were this total divided by 10!, a value that simplified to the rather concise fraction 7/40, or 17.5 percent.

One wondering I had was how a target sum of 21 stacked up against other possible target sums in this game. For example, were you more likely to win with a target sum of 21, as opposed to 20 or 22? What about other target values?

The following bar graph shows your chances of winning for each target value from 1 to 54 (i.e., one less than the sum of all 10 cards). The extremes weren’t too tricky to work out. To hit a target score of 1, you needed the first card to be a 1, which happened 10 percent of the time. Meanwhile, to hit a target score of 54, you needed the last card to be a 1, which again happened 10 percent of the time. Between these extremes, the bar graph exhibited a rather cool pattern that kind of looked like … dare I say it … Batman’s cowl?

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Peter Norvig 🎻 from Palo Alto, California. I received 51 timely submissions, of which 37 were correct—good for a 73 percent solve rate.

Playing for 21 or bust was a risky strategy. As we just found, you only won 17.5 percent of the time. And so, from this moment on, you decided to be risk averse.

You were playing the same modified version of blackjack again, but this time, whenever there was even the slightest chance you could bust on the next card, you quit the round and started over. On average, how many rounds should you have expected to start until you finally won?