Problem 17 of Monte Carlo solutions to Fifty Challenging Problems...

(This is another part of the Fifty Problems series, a set of example applications of Monte Carlo methods. In each post, I present source code which answers a probabilistic question using simulated models of the underlying system.)

Problem 17: In a jousting tournament, there are two twins: Balan and Balin. If there are 8 knights total, all equally matched, and the initial ladder is randomly assigned, what's the probability of the twins jousting against each other?
#!/usr/bin/env ruby


# Array of Knighs: BalIn and BalAn, and some schmucks.

# The knights are equally matched, so we need to randomize
# the selection of who wins each round.  Otherwise, this is
# very similar to problem16.rb.

# We're going to abuse the weak typing of ruby here.  Don't 
# do this for real.  
# Returns an array if we just continue on, returns nil if the
# brothers meet.
def round(seedings)
  next_round = []

  # Walk the seedings pairwise, looking for "A" and "I"
  # Note that order doesn't matter.

  i = 0
  while (i < seedings.length())
    return nil if (["A","I"] & seedings[i..i+1]).length == 2 # rubylicious.
    next_round.push( seedings[i + rand(2)] )
    i += 2
  return next_round

def tourney()
  first_round = KNIGHTS.shuffle
  quarters = round(first_round)
  return true if !quarters

  semi = round(quarters)
  return true if !semi

  final = round(semi)
  return true if !final

  return false # tourney over

srand() # Our first call to shuffle is before our
        # first call to rand()...

TRIALS.times do
  n_match += 1 if tourney()

puts "In #{TRIALS} trials, the brothers met #{n_match} times."
puts "P=#{n_match/TRIALS.to_f}"

I've been coding my way through Fifty Challenging Problems in Statistics with Solutions. This post is a part of the Fifty Challenging Problems series.

This was brought to you by Josh Myer. He has other fun things at his homepage.