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

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

Chess Domination

Domination is a state achieved in chess when all unoccupied squares are threatened by a piece. Its a combinatorics problem that match people like to think about — more can be read about it here

I ended up just brute forcing the problem which is like wrong but it ended up being kinda cool to see just how many iterations it takes. I ended up just having it run on a second monitor for a day or so to see how close to the optimal solution it could get.

Continue reading

a puzzle about domestic boundaries

Another week, another riddler. The problem is:

    Consider four square-shaped ranches, arranged in a two-by-two pattern, as if part of a larger checkerboard. One family lives on each ranch, and each family builds a small house independently at a random place within the property. Later, as the families in adjacent quadrants become acquainted, they construct straight-line paths between the houses that go across the boundaries between the ranches, four in total. These paths form a quadrilateral circuit path connecting all four houses. This circuit path is also the boundary of the area where the families’ children are allowed to roam.

    What is the probability that the children are able to travel in a straight line from any allowed place to any other allowed place without leaving the boundaries? (In other words, what is the probability that the quadrilateral is convex?)

 

I wish I could say I did something cool. Instead I just brute forced it. After ten million iterations the resulting probability of a convex ranch is 9.09%
github

Continue reading

12 coins, 11 gold

The Problem:


You have 12 gold coins — or so you think! One is fake and is known to have a different weight than the others. It could be heavier or lighter; you only know it’s wrong. Using the same simple balance scale, how do you determine the incorrect coin, and whether it is heavier or lighter, in only three weighings?

400px-The_Coin_full.jpg

Problem from Ollie’s The Riddler

The Logic:


The criteria for the unique coin’s identity to be known is

  • It must be weighed at least once
  • If put on the scale with an equal number of coins on each side it cannot be evenly balanced
  • If put on the scale more than once with an even number of coins on each side it must weight consistently more or consistently less than the other side

This is the framework for finding the solution — just find a weighing scheme that lets you remove 11 of the coins from this criteria with one that satisfies it. There is some branching allowed, depending on the result of the previous weighing you can alter which coins you put on each side of the scale. I call these Scale Configs and there are two per branch:

Untitled Diagram (1).png

For example, putting coins 0,1,2,3 on one side of the scale and 4,5,6,7 on the other is Scale Config 1

The Solution:


My configurations are as follows:

WithConfigsUntitled Diagram (1).png

For example, if coin 8 is made of a heavier material than metal our path would go:

  1. Weigh [0,1,2,3] against [4,5,6,7]. They are evenly balanced (go to Config 3)
  2. Weigh [5,6,7] (known non-unique coins) against [8,9,10]. [8,9,10] is heavier meaning the coin is among those three and heavier
  3. Weigh [8] against [9]. 8 is heavier and therefore the unique coin

Code:


Making this in Python helped me understand the problem and the decisions I actually got to make. I was fairly confident in my Configurations 1,3,6,7 because I could logic though them — but 2, 4 and 5 were all dependent on one another and therefore annoying. It ended up saving time just writing a way to brute force different configurations for those three — yielding the solution above.

The code can be found here 

 

The code creates configurations for both sides of C2, C4, C5 then tests every coin as being both heavier and lighter. If it can deduce each one then it is a pass. It took about 20,000 iterations to get to the working solution, above.

 

The Riddler: an impromptu gambling problem

Here is a solution to the gambling problem posed in this weeks Riddler by Ollie. The problem can be found here in full:


You and I stumble across a 100-sided die in our local game shop. We know we need to have this die — there is no question about it — but we’re not quite sure what to do with it. So we devise a simple game: We keep rolling our new purchase until one roll shows a number smaller than the one before. Suppose I give you a dollar every time you roll. How much money do you expect to win?

Extra credit: What happens to the amount of money as the number of sides increases?


The key, for me, to this problem was thinking about all the branches that occur after the first roll.

Rolling a 99 on the first roll would mean there are 98 branches below that require further exploration — only rolling another 99 or 100 would end the game.

RollMax.png

The branches that come from rolling the highest number in a four sided die case. Determining the average number of points in this case isn’t immediately obvious

However rolling a 1 on the first roll would mean there are 0 branches that require further exploration — no number on the die is smaller than that. Therefore rolling a 1 means you are expected to get 0 more points.

Simplified.png

The branches that come from rolling the lowest number in a four sided die case. Determining that your payout is 2 is evident

Extending this thought rolling a 2 would mean that there is one branch that extends the game — rolling a  one. Therefore we know the expected reward for rolling a two is the chance that the game extends (1/100) times the sum of one (because you get to roll again) and the average of the expected values of all smaller numbers (just the ev(1), which is 0).

CodeCogsEqn (5).gif

Generalizing this we get:

CodeCogsEqn (4).gif

For a one hundred sided die you can see that the point values you can expect to get after the initial roll increase as the number you roll increases

evPerRoll.png

Using this we would get the expected value for all sides on the die and average them — followed by adding two because we get a point for the first roll and the last roll, regardless of their value.

CodeCogsEqn (8).gif

Again this is easy to generalize for variously sized dice, giving us the equation:

CodeCogsEqn (7).gif

Giving us the answers of payout(100) = 2.73and as s approaches infinity the payout approaches e, Euler’s number

WithLabels.png

Edit 1/20/17: So I guess this answer is wrong. Since this model proved similar to my testing (done by just playing the game using rand()) I suspect something is up with my interpretation of the games rules

 

 

All code written in python 3.5:

import matplotlib.pyplot as plt

#Finding expected payout
results = []
for num_sides in range(10,500): 
  ev = [0]
  for i in range(1,num_sides):
    ev.append((len(ev)/num_sides)*(sum(ev)/len(ev)+1))

  results.append(2+sum(ev)/len(ev))

#Plotting
plt.plot([range(10,500)],[results],'ro')
plt.title('an impromptu gambling problem')
plt.ylabel('Expected Payout')
plt.xlabel('Number of Sides')
plt.show()