Green Eyes

 

Problem:  In a group of twenty-seven people, eleven have blue eyes, thirteen have brown eyes, and three have green eyes.  If three people are randomly selected from the group, what is the probability that exactly one of them will have green eyes?

Closed-form solution:  There are 27C3 ways to choose three people from a group of twenty-seven.  Of those, 24C2 will have one person with green eyes (that is, choose two of the twenty-four people who don't have green eyes).  Since any of the three can have green eyes, the result must be multiplied by three:

(define (fac n)
  (if (<= n 1)
      1
      (* n (fac (- n 1)))))

(define (choose n r)
   (/ (fac n) (* (fac r) (fac (- n r)))))

(* (/ (choose 24 2) (choose 27 3)) 3)


This evaluates to 828/2925, which reduces to 92/325, or 28.3%.

Simulation solution:  We make a vector eyes with the required population, a procedure shuffle! to mix them up, and a predicate green? to check if exactly one of the first three elements of the vector is green.

(define (rept x n)
  (if (zero? n)
      '()
      (cons x (rept x (- n 1)))))

(define eyes
  (list->vector (append
    (rept 'blue 11) (rept 'brown 13) (rept 'green 3))))

(define (randint l r)
  (inexact->exact (+ l (floor (* (random) (+ (- r l) 1))))))

(define (shuffle! v)
  (let ((n (- (vector-length v) 1)))
    (do ((i 0 (+ i 1))) ((< n i) v)
      (let* ((r (randint i n))
             (t (vector-ref v r)))
        (vector-set! v r (vector-ref v i))
        (vector-set! v i t)))))

(define (green? v)
  (= 1
     (apply +
            (map (lambda (s)
                   (if (eq? (vector-ref v s) 'green)
                       1
                       0))
                 '(0 1 2)))))


Then we write a function to simulate the test:

(define (sim n)
  (let loop ((n n) (eyes (shuffle! eyes)) (count 0))
    (if (zero? n)
        count
        (loop (- n 1) (shuffle! eyes) (+ count (if (green? eyes) 1 0))))))


Repeated calls of (sim 292500) all find about 82,800 selections that have one person with green eyes, which agrees to the closed-form solution.

Enumeration solution: There are 27C3 = 2925 ways to choose three items from a set of twenty-seven, so it is reasonable to make a list of all the possibilities and count those that have one person with green eyes.  We write a function upto that returns an ordered list, the list-of comprehension, an eyes-list of three-choices from the group, and a predicate green-list? to count the number of people with green eyes, then count the number of selections that have one person with green eyes:

(define (upto a b)
  (if (< b a)
      '()
      (cons a (upto (+ a 1) b))))

(define-syntax list-of
  (syntax-rules (in is)
    ((_ 'aux expr base) (cons expr base))
    ((_ 'aux expr base (x in xs) clauses ...)
      (let loop ((z xs))
        (if (null? z)
            base
            (let ((x (car z)))
              (list-of 'aux expr (loop (cdr z)) clauses ...)))))
    ((_ 'aux expr base (x is y) clauses ...)
      (let ((x y))
        (list-of 'aux expr base clauses ...)))
    ((_ 'aux expr base pred? clauses ...)
      (if pred?
          (list-of 'aux expr base clauses ...)
          base))
    ((_ expr clauses ...)
      (list-of 'aux expr '() clauses ...))))

(define eyes-list
  (list-of (list a b c)
    (a in (upto 0 26))
    (b in (upto (+ a 1) 26))
    (c in (upto (+ b 1) 26))))

(define (green-list? xs)
  (= 1
     (apply +
            (map (lambda (x)
                   (if (eq? (vector-ref eyes x) 'green)
                       1
                       0))
                 xs))))

(apply + (map (lambda (xs) (if (green-list? xs) 1 0)) eyes-list))


This evaluates to 828, which agrees to the 24C2 * 3 computed by the closed-form solution.