Does Crime Pay in the Den of Thieves?
Puzzle for week of 2/2/25
Inspired by the Fiddler on the Proof (formerly The Riddler), X’s Puzzle Corner aims to produce a weekly puzzle for readers that enjoy math, probability, and algorithms. Please submit your solution! Solutions will be accepted until 11 pm the following Sunday after the puzzle is posted (in this case 2/9/25). While it isn’t required, I encourage you to opt to have your solution shared so that we all get the chance to see how others thought about and attempted the problem!
The answers of all those that volunteered their solutions will be posted around Wednesday at 10 am.
In many cases, I expect the readers will be better puzzlers than me so I make no guarantees the solutions are correct. I also make no promises about having worked out the solutions to the puzzles ahead of time so it may be the case that they’re very challenging. Part of the fun is finding out!
In our next series of puzzles we will explore a game I’ve been calling Den of Thieves. In this game we have n thieves that each have $1. The game proceeds in rounds where every thief simultaneously and anonymously selects a target. If a player has been selected by at least one thief, they lose the money they had at the start of the round (but they will still gain the money for their theft for the round). Each thief will gain the amount money of their victim unless other thieves also selected this target. In this case, all the thieves split the money evenly (in this game world, there is some honor among thieves). To clarify, all of the monetary losses occur before collecting your ill-gotten gains so even if you are stolen from, you will still end the round with whatever amount you stole from your victim.
Our first question is, what is the distribution of money a thief has after round 1 if there are 10 thieves and each starts with a dollar? How about if n is very large?
Please submit your thoughts, progress, or answers here.
To be clear, are you asking for the expected value of the ordered histogram, i.e., the value of the first bin is the expected amount of money held by the thief who has the most, rather than for thief number 1? I'm pretty sure that the average distribution by index is just a constant $1.
Figuring out the distribution after the first round would be very difficult, requiring us to determine what strategy they are using. It gets very complicated if you start considering future moves (do I play badly in the early rounds in the hope that I will be ignored until I make an epic play in the last round?).