## The 16 Game

### October 29, 2013

A local store has a promotional game in which scratch-off cards have sixteen spaces that cover a random permutation of the numbers 1 through 16. Customers scratch off the spaces at random. If the scratch-off reveals the number 3, the card loses. If the scratch-offs reveal the numbers 1 and 2, in either order, the card wins. Winning cards receive a discount on store merchandise.

Your task is to write a program that determines the average winning percentage. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

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.

Solution in Racket.

Oops! The winning-% function had a bug in the second for*/sum clause.

Trying Nimrod:

A slightly different approach, which recursively calculate the probability. It is “generalized” to take any N >= 3, but that doesn’t matter :-)

module TheSixteenGame(

solve

) where

solve :: Int -> Double

solve n

| n <= 2 = error "Input integer should be >= 3"

| otherwise = twoLeft n

twoLeft :: Int -> Double

twoLeft n

| n == 2 = 1.0

| otherwise = pickOne * oneLeft (n – 1) + pickNone * twoLeft (n – 1)

where

pickOne = 2.0 / fromIntegral n

pickNone = fromIntegral (n – 3) / fromIntegral n

oneLeft :: Int -> Double

oneLeft n

| n == 1 = 1.0

| otherwise = pickOne + pickNone * oneLeft (n – 1)

where

pickOne = 1.0 / fromIntegral n

pickNone = fromIntegral (n – 2) / fromIntegral n