The 16 Game

October 29, 2013

This is a trick question. There is no need to write a program; the solution is easy to work out just by reasoning. The numbers 4 through 16 don’t contribute to the solution, and can be ignored. There are 3! = 6 permutations of the numbers 1 through 3; two of them, (1 2 3) and (2 1 3), are winners, and the other four are losers. Thus, the average winning percentage is one-third. But if you really want to write a program, here it is:

(define (play xs)
  (let loop ((xs xs) (one #f) (two #f))
    (cond ((= (car xs) 1) (if two #t (loop (cdr xs) #t #f)))
          ((= (car xs) 2) (if one #t (loop (cdr xs) #f #t)))
          ((= (car xs) 3) #f)
          (else (loop (cdr xs) one two))))))

(define (plays n)
  (let loop ((n n) (wins 0))
    (if (zero? n) wins
      (if (play (shuffle (range 1 17)))
          (loop (- n 1) (+ wins 1))
          (loop (- n 1) wins)))))

Play plays a single card; plays plays n cards. The return value of (plays n) ought to be about one-third of n:

> (plays 3000)
> (plays 3000)
> (plays 3000)

It looks like our random number generator is properly uniform. We used range, randint and shuffle from the Standard Prelude. You can run the program at

About these ads

Pages: 1 2

4 Responses to “The 16 Game”

  1. Jussi Piitulainen said

    The only thing that matters is the relative order of 1, 2, and 3 in a permutation. Since 1/3 of the permutations have 1 and 2 before 3, the classical probability of winning is 1/3 and the expected percentage of winning cards in a pack is a little above 33. I didn’t write a program.

  2. Solution in Racket.

    #lang racket
    (define (shuffle! v)
      (define len (vector-length v))
      (for ([i (in-range len)])
        (define j (+ i (random (- len i))))
        (define tmp (vector-ref v i))
        (vector-set! v i (vector-ref v j))
        (vector-set! v j tmp))
    (define slots-per-card 16)
    (define (scratch-card card)
      (for*/fold ([x 0]) ([i (shuffle (range slots-per-card))]
                          [c (in-value (vector-ref card i))]
                          #:break (or (= c 3) (= x 2))
                          #:when (or (= c 1) (= c 2)))
        (add1 x)))
    (define (winning-% [tries 10000])
      (define card (build-vector slots-per-card add1))
      (define n
        (for*/sum ([_ (in-range tries)]
                   [_ (shuffle! card)]
                   [x (in-value (scratch-card card))]
                  #:when (= 2 x))
      (exact->inexact (/ n tries)))
  3. Oops! The winning-% function had a bug in the second for*/sum clause.

    (define (winning-% [tries 10000])
      (define card (build-vector slots-per-card add1))
      (define n
        (for*/sum ([_ (in-range tries)]
                   [_ (in-value (shuffle! card))] ;; <==
                   [x (in-value (scratch-card card))]
                  #:when (= 2 x))
      (exact->inexact (/ n tries)))
  4. Mark said

    Trying Nimrod:

    import math
      numTrials = 1000000
      j, tmp: int
      a = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
      tot = 0
    for n in 1..numTrials:
      for i in countdown(15,1):
        j = random(i+1)
        tmp = a[i]
        a[i] = a[j]
        a[j] = tmp
      if a.find(3) > a.find(2) and a.find(3) > a.find(1):
        tot += 1
    echo(tot / numTrials)

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: