Four Paths to the Benjamin
by Larry Snyder
About a year ago, I started writing weekly puzzles for Opexers (Opex Analytics employees) to solve for fun in their free time. The idea was to pose puzzles that used math, logic, operations research (OR), computer programming, data science, or other quantitative tools in a fun, non-work-related setting. One of the best parts of this endeavor has been seeing the great diversity of ways in which Opexers have solved the puzzles. It’s not uncommon for some solutions to use math, others logic, and others OR, all for the same puzzle. I want to give you one example in this post.
The Puzzle
Let’s play a game I call “chasing the Benjamin.” Each of us will take turns putting anywhere between $1 and $10 on the table. Whoever makes the stack equal exactly $100 (that is, a Benjamin) wins the stack.
You go first. How much should you put on the table, and why?
The Answer…….
Maybe you want to try to figure it out yourself? Scroll down when you’re ready for the answer.
The answer is that you should put down $1. After that, you should always play $11 minus the amount that I put down.
So how do you come up with this answer? The solutions submitted by Opexers used several different approaches.
Approach #1: Logic
This was the approach I used, and it’s probably the most straightforward. The logic goes like this:
First, if you get to $89 (meaning, you put down money that brings the stack to $89), then you are guaranteed to win. This is because I will have to bring the stack to some value between $90 and $99, and then you can play the right amount to bring the stack to $100 — namely, $11 minus however much I play. So, if you can get to $89, then you are guaranteed to get to $100.
Similarly, if you can get to $78, then by the same logic, you can guarantee that you’ll get to $89.
And if you can get to $67, then you can get to $78.
And so on: $56, then $45, then $34, then $23, then $12, and finally:
$1.
Approach #2: Computing
Rohit, a Data Scientist at Opex, took a computing-centric approach. He coded up the game in Python, with the computer playing the role of you, i.e., the first player to move. The user then enters a number to add to the stack, and the computer plays according to the rule above: always add $11 minus the opponent’s last value. The computer starts by playing $1. And it always wins.
Of course, this is not a proof of the correctness of this strategy, but it’s a compelling demonstration. Play it as many times as you like, and the computer always wins.
Approach #3: Operations Research
This puzzle can be formulated as a dynamic programming (DP) problem: Let Vₚ(s) be the value of the game to player 1 (you), assume that at the beginning of player p’s turn (p = 1, 2), the stack has $s in it, and that both players play optimally. In other words, if it’s player p’s turn and there is $s in the stack, then Vₚ(s) tells us whether optimal play by both players from that point forward will result in player 1 winning (Vₚ(s) = 1) or losing (Vₚ(s) = 0).
The function Vₚ(s) can be calculated recursively. First, let V₁(s) = 1 and V₂(s) = 0 for all s ≥ 100. Then, for s < 100, we have:
You (player 1) want to choose the value of x (the number of dollars to add to the stack) that maximizes the value of the game, accounting for the fact that on the next turn, the stack will have $(s+x) in it and it will be my (player 2’s) turn.
On the other hand, I (player 2) want to choose the value of x that minimizes the value of the game (since the value is defined from your point of view), accounting for the fact that on the next turn, the stack will have $(s+x) in it and it will be your (player 1’s) turn.
If you code this recursion and solve it, you’ll find that V1(0) = 1, and the winning value of x is 1. In other words, if there is $0 in the stack and it’s your turn, you’re guaranteed a win if you play $1 (and we both play optimally after that). Moreover, you’ll see that for s > 0, the winning value of x for player 1 is always 12 — s, or 23 — s, or 34 — s, or …
(Opex OR Scientist Austin B. took this approach.)
Approach #4: Game Theory
Finally, Jamie, another Data Scientist at Opex, explained the player’s optimal strategy, but then also looked at the game from the point of view of the player’s opponent. He asked, if I (your opponent) know I will lose (because you know the winning strategy), what strategy should I take in order to minimize my losses? Of course, the optimal approach is to play $1 every time — I still lose, but I only lose $9. The $100 stack that you walk away with contains $91 of your own money. Jamie proved that you have no better strategy: No matter what, if you and I both play optimally (and you go first), you will win $9.
Final Thoughts
One simple puzzle. Four very different ways of solving, explaining, coding, and analyzing it. For me, this example encapsulates what’s fun about working with Opexers, and why they’ve been so successful in helping clients solve their own puzzles. Most problems can be solved with multiple tools, each with its own advantages and disadvantages. Working with people whose expertise spans the whole toolbox makes for a rewarding job. And not just when it comes to puzzles.
Source: I saw this puzzle at https://www.futilitycloset.com/2018/06/28/escalation/, though in that version, the players add numbers rather than stacking dollars. There are lots of other puzzles like it, including the famous game of Nim.
___________________________________________________________________
If you liked this blog post, check out more of our work, follow us on social media or join us for our free monthly Academy webinars.
