Game Show: Bright Lights, Big City

Another week, another Riddler. The question:

You and three of your friends are on a game show. On stage is a sealed room, and in that room are four sealed, numbered boxes. Each box contains one of your names, and each name is in one box. You and your friends take turns entering the room alone and opening up to two boxes, with the aim of finding the box containing your name. Everyone enters exactly once. Your team can confer on a strategy before stepping on stage, but there is no communication allowed during the show — no player knows the outcome of another player’s trip into the room.

Your team wins if it’s ultimately revealed that everyone found the box containing his or her name and loses if any player failed to do so. Obviously, the odds of winning are no better than 50 percent because any single player has a 50 percent chance of finding his or her own name. If each person opens two boxes at random, the chance of winning is (1/2)^4=1/16=6.25(1/2)^4=1/16=6.25 percent. Or to put it in technical terms: The chance of winning is not so great. Call this the naive strategy.

Your goal: Concoct a strategy that beats the naive strategy — one that gives the team a better chance of winning than 1/16.

Extra credit: Suppose there are 100 contestants and 100 boxes. Each player may open 50 boxes. The chance of winning by using the naive strategy is 1 in 2^100, or about 1 in 1.2×10301.2×1030. How much can you improve the team’s chances?

The way to beat this game is to look at the problem in a different light. My strategy to winning was to instead look at the chance that the first half of the players have their number in the first half of the boxes. If they are the first half of the players will find their numbers, meaning the second half are guaranteed to find theirs in the second half. The equation for this would look something like this:

\prod_{i=0}^{n/2}\left ( \frac{\frac{n}{2}-i}{n-i} \right )

Where

n =  number of players

This provides the answer of 1/6th for four players and 7.91e-15 for 50 players


		
Advertisements

National Squishyball League Championship

Another week, another Riddler. The question:

Congratulations! The Acme Axegrinders, which you own, are the regular season champions of the National Squishyball League (NSL). Your team will now play a championship series against the Boondocks Barbarians, which had the second-best regular season record. You feel good about Acme’s chances in the series because Acme won exactly 60 percent of the hundreds of games it played against Boondocks this season. (The NSL has an incredibly long regular season.) The NSL has two special rules for the playoffs:

  1. The owner of the top-seeded team (i.e., you) gets to select the length of the championship series in advance of the first game, so you could decide to play a single game, a best two out of three series, a three out of five series, etc., all the way up to a 50 out of 99 series.
  2. The owner of the winning team gets $1 million minus $10,000 for each of the victories required to win the series, regardless of how many games the series lasts in total. Thus, if the top-seeded team’s owner selects a single-game championship, the winning owner will collect $990,000. If he or she selects a 4 out of 7 series, the winning team’s owner will collect $960,000. The owner of the losing team gets nothing.

Since Acme has a 60 percent chance of winning any individual game against Boondocks, Rule 1 encourages you to opt for a very long series to improve Acme’s chances of winning the series. But Rule 2 means that a long series will mean less winnings for you if Acme does take the series.

How long a series should you select in order to maximize your expected winnings? And how much money do you expect to win?

To find this you have to find the expected value for each number of games. This ended up being:

\sum_{n=0}^{f_{t}-1}\left(p^{f_{t}+n}\right)\left(\left(1-p\right)^{f_{t}-1-n}\right)\left(\frac{\left( 2f_{t}-1\right)!}{\left(f_{t}+n\right)!\left(f_{t}-1-n\right)!}\right)

Where

n =  number of games won

f_{t} =  series is first to _

p =  probability Axegrinders win

 

What the heck is this? Oh man good question. Okay so first we assume that in each case we are playing the full number of games. So if it is a first to 3 (commonly referred to as a best of 5) then we are going to play five games, even if we win the first 3. This can lead to “extra” wins, but helps keep the math concise. So again in the first to 3 case:

Axegrinders Wins Barbarians wins Ways this can occur
First to 3 3 2 10
4 1 5
5 0 1

So the equation would take n=0 (no extra wins) to make the top row. The probability this happens is

\left ( 0.6 \right )^{3}\left ( 0.4 \right )^{2}\cdot 1

summed with the next two rows:

\left ( 0.6 \right )^{4}\left ( 0.4 \right )\cdot 5

\left ( 0.6 \right )^{5}\cdot 10

this sum, equal to 0.68, is the chance that the Axegrinders win the series. This is multiplied by the payout to get the expected value (662,000).

This gives us this wonky looking graph:

OverlayedGraphs.png

The result of this is the optimal payout is when the Axegrinders choose to play a first to 13, or best of 25. Doing so will give them an expected return of $736,222.

The code:

import math
import matplotlib.pyplot as plt

#Chances of winning
def c_o_w(prob,first_to):
    chance_of_winning = 0
    for i in range(0,first_to):
    games = 2*first_to-1
    a_wins = first_to+i
    b_wins = games-a_wins
    individ_prob = prob**(a_wins)*(1-prob)**(b_wins)*math.factorial(games)/(math.factorial(a_wins)*math.factorial(b_wins))
    chance_of_winning += individ_prob
    return(chance_of_winning)

#Calculated chances of winning, payout and ev for each series length
chances = []
payout = []
ev = []
x = []
for series_length in range(1,86):
   chances.append(c_o_w(0.6,series_length))
   payout.append(100-series_length)
   ev.append(chances[series_length-1]*payout[series_length-1])
   x.append(series_length)

#Oh man I gotta graph this
fig, ax = plt.subplots(sharey=False)
pev, = ax.plot(x,ev, color = 'b', label = 'Expected Value')
ax.set_ylabel("Dollars, in Thousands", color = 'b')
ppay, = ax.plot(x,payout,color = 'g', label = 'Payout')
ax.tick_params('y',colors = 'b')
ax.set_xlabel("Best of _ Series")

ax2 = ax.twinx()
pchance, = ax2.plot(x,chances, color = 'm', label = 'Probability to win series')
ax2.set_ylabel("Chances Axegrinders Win Series", color = 'm')
ax2.tick_params('y',colors = 'm')
fig.tight_layout()
plt.title('Axegrinders Series Length Selection')
fig.legend([pev,ppay,pchance],['Expected Value', 'Payout', 'Chances Axegrinders Win Series'],loc='lower right', borderaxespad=8.)
plt.show()

The Purge Riddler

Another week, another Riddler. This weeks:

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:

  1. What is the probability that a house is not robbed over the course of the day
  2. 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?

This one revolves around lots of conditional probability which I really enjoy.

Question One:

This one is the basis for main problem. Each player has a \frac{1}{999} chance in robbing an individual. Therefore the chance to NOT get robbed is the probability that each player fails to rob you, or \left ( \frac{998}{999} \right )^{999}. This is approximately 0.3677.

Question Two:

This is the real problem here. For each player you need to know the chance that they get robbed before its their turn, then the amount that you are likely to steal from others and finally all multiplied by the chances your stuff gets stolen. This looks like this:

ev(n) = \left (100\cdot \left ( \frac{998}{999} \right )^{n}+100+100 \cdot \left ( 1-\left ( \frac{998}{999} \right )^{n} \right ) \right )^{999-n}

Expected Cash Returns in Relation to Position, n with 1000 players and 100$ starting sum

This, plotted, leaves you with the following graph:

Theoretical.png

To check the answer I plotted this against a simulated version of the game which was run a million times:

vsEachother.pngdelta.png


import random
import matplotlib.pyplot as plt

#Run a house robbing simulation
def house_rob(players):
  holdings = players*[1]
  for i in range(0,players):
    unselected = True
    to_take_from = 0
    while to_take_from == i or unselected:
      to_take_from = random.randint(0,players-1)
      unselected = False
    holdings[i] += holdings[to_take_from]
    holdings[to_take_from] = 0
    #print(holdings)
    unrobbed_people = holdings.count(1)
    return holdings,unrobbed_people

#Iteratively run trials
players = 1000
avg_holdings = players*[0]
num_trials = 300000
for trials in range(0,num_trials):
  results = house_rob(players)
  for i in range(len(results[0])):
    avg_holdings[i] += results[0][i]

#Make data ready to graph
player_titles = []
real = []
plottable_holdings = []
delta = []
for n in range(1,players):
  real.append((1*(998/999)**n+1+1*((1-(998/999)**n)*(1/999)))*(998/999)**(999-n))
  player_titles.append(n)
plottable_holdings.append(avg_holdings[n]/num_trials)
  delta.append(plottable_holdings[n-1]-real[n-1])

#And make those graphs
plt.scatter(player_titles,plottable_holdings)
plt.scatter(player_titles,real, color = "g")
plt.title("Expected Cash Returns in Relation to Position")
plt.xlabel("Player Position")
plt.ylabel("Expected Cash Returns, in hundreds")
plt.show()

Weighing Accurately

The Problem:

What is the smallest set of weights needed in order to weigh every integral number of pounds up to 255 pounds by putting the weights on one side of a balance scale and the object to be weighed on the other side?

If you are allowed to put weights on both sides of the scale, what is the smallest set of weights needed for the above problem?

 

Solution:

To represent the one side case you use the powers of two as weights. This would require the weights 1,2,4,8,16,32,64 and 128. Which weights you use would look a lot like the binary representation for the number.
The second case you get three bits of info per number so you can use powers of threes as weights. This means the weights 1,3,9,27,81 and 243g. For example to weigh something that is 22g you would put the 27, 1 and 3g on the unweighted side and the 9g on the side with the unknown object to identify it. Fun!

A Painting Puzzle

Another week, another Riddler. This problem:

    You play a game with four balls: One ball is red, one is blue, one is green and one is yellow. They are placed in a box. You draw a ball out of the box at random and note its color. Without replacing the first ball, you draw a second ball and then paint it to match the color of the first. Replace both balls, and repeat the process. The game ends when all four balls have become the same color. What is the expected number of turns to finish the game?

This one revolves around finding the expected number of turns required to get from your starting configuration (all different colors) to the ending configuration (all the same). To do this we can set up a system of equations:

The 3 Ball Case:

We will be using the following notation: [\textup{A}_{1},\textup{A}_{2},\textup{A}_{3}, ... , \textup{A}_{n}] where A represents the number of colors with one ball representing them and n represents the quantity of balls. So in the 3 ball case we start with [3,0,0] because each of the three colors have one ball. One ball will be painted the same as another, giving you [1,1,0]. At this point you have a 2/3rds chance to use a whole turn that leaves you in a [1,1,0] (in essence calling itself) and a 1/3rds chance to get to the final [0,0,1]. To find the average number of turns spent in this loop I used:

ev(A) = \frac{2}{3}ev(A)+1
ev(A) = 3

therefore:

ev(\textup{3 Ball Case}) = 1 + ev(A) = 4

because it takes one turn to get the to A case.

The 4 Ball Case:

A similar set of equations can be set up:

S = [4,0,0,0]
A = [2,1,0,0]
B = [0,2,0,0]
C = [1,0,1,0]

ev(S) = ev(A) + 1
ev(A) = \frac{1}{6}ev(B) + \frac{1}{3}ev(C) + \frac{1}{2}ev(A) + 1
ev(B) = \frac{1}{3}ev(B) + \frac{2}{3}ev(C) + 1
ev(C) = \frac{1}{4}ev(B) + \frac{1}{2}ev(C) + 1

solving this gives us ev(S) = ev(\textup{4 Ball Case}) = 9

This can be expanded to show the general equation to be:

ev(n \textup{ Ball Case}) = (n-1)^{2}

Experimentally

This was done in Python as well to show the distribution:

 

4Balls.png

9Balls.png

 

import random
import copy
import matplotlib.pyplot as plt

num_balls = 4
iterations = 1000000

standard_array = []
for _ in range(0,num_balls):
 standard_array.append(_)

def game(array):
 working_array = copy.deepcopy(array)
 turns = 0
 while len(set(working_array))>1:
 rand_1 = 0
 rand_2 = 0
 while rand_1 == rand_2:
 rand_1 = random.randint(0,len(array)-1)
 rand_2 = random.randint(0,len(array)-1)
 working_array[rand_2] = working_array[rand_1]
 turns = turns + 1
 return turns

total_turns = 0
results = []
for i in range(0,iterations):
 val = game(standard_array)
 total_turns = total_turns + val
 results.append(val)
print("Average # of turns: " + str(float(total_turns/iterations)))

num_bins = len(set(results))
n, bins, patches = plt.hist(results, bins=list(set(results)), normed=1, facecolor='green', alpha=0.5)
plt.ylabel("Frequency")
plt.xlabel("Number of Turns")
plt.title("A Painting Puzzle with " + str(num_balls) + " balls\n in " + str(iterations) + " iterations")
plt.show()

Pick A Card, Any Card

This was another Riddle, posed by Ollie. The question was:

    From a shuffled deck of 100 cards that are numbered 1 to 100, you are dealt 10 cards face down. You turn the cards over one by one. After each card, you must decide whether to end the game. If you end the game on the highest card in the hand you were dealt, you win; otherwise, you lose.

    What is the strategy that optimizes your chances of winning? How does the strategy change as the sizes of the deck and the hand are changed?

So up to ten times you pick up a card from the deck and decide to ACCEPT or PASS it. The criteria for selection was:

  1. If it is the last card you must ACCEPT it
  2. If you PASSED a card larger than your current card then you must pass this (unless this violates rule #1)
  3. If there is a fifty percent chance or higher that all the consecutive cards are smaller then ACCEPT the current card (unless this violates rule #2)

The equation for determining if all the consecutive cards are smaller than the current card is:

CodeCogsEqn (9).gif

where i is the index of the card you are evaluating (the first card would be 0, the second would be 1, etc.)

The result for the 10 card hand size, 100 card deck is that you can successfully determine the card 62.2% of the time. This changes with as follows:

Continue reading