Who Steals The Most In A Town Full Of Thieves?

Riddler Express

You’re driving a car down a two-mile track. For the first mile, you drive 30 miles per hour. How fast do you have to go for the second mile in order to average 60 miles per hour for the whole track?

Solution

We have the following equation:

From the above it is obvious that achieving an average speed of 60 miles per hour is not possible.

Riddler Classic

A town of \$1,000 households has a strange law intended to prevent wealth-hoarding. On January $1$ of every year, each household robs one other household, selected at random, moving all of that house’s money into their own house. The order in which the robberies take place is also random and is determined by a lottery. (Note that if House $A$ robs House $B$ first, and then $C$ robs $A$, the houses of $A$ and $B$ would each be empty and $C$ would have acquired the resources of both $A$ and $B$.)

Two questions about this fateful day:

What is the probability that a house is not robbed over the course of the day?

Suppose that every house has the same amount of cash to begin with — say \$100. Which position in the lottery has the most expected cash at the end of the day, and what is that amount?

Solution

from random import sample

runs = 10000
num_houses = 1000
final_amts = [0] * num_houses
total_num_safe = 0

rob_choices = {i:(set(range(num_houses))-set([i])) 
                for i in range(num_houses)}
lottery = list(range(num_houses))
rob = [None] * num_houses
amts = [None] * num_houses
for _ in range(runs):
    for i in range(num_houses):
        amts[i] = 100
        rob[i] = sample(rob_choices[i], 1)[0]
    total_num_safe += (num_houses - len(set(rob)))
    shuffle(lottery)
    for h in lottery:
        amts[h] += amts[rob[h]]
        amts[rob[h]] = 0
    for i,j in enumerate(lottery):
        final_amts[i] += amts[j]

print(total_num_safe/(runs*num_houses))
amt, pos = max(zip(final_amts, range(num_houses)))
print(amt/runs, pos)

The percent of houses that are not robbed on average is $37$. The position in the lottery with the most expected cash is the last position and the maximum expected cash amount is \$137.