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()
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s