{- | Simulation of a game with the following rules: Players A and B alternatingly take numbers from a set of 2*n numbers. Player A can choose freely from the remaining numbers, whereas player B always chooses the maximum remaining number. How many possibly outcomes of the games exist? The order in which the numbers are taken is not respected. E-Mail by Daniel Beer from 2011-10-24. -} module Combinatorics.MaxNim where import qualified Data.Set as Set {- | We only track the number taken by player A because player B will automatically have the complement set. -} gameRound :: (Set.Set Int, Set.Set Int) -> [(Set.Set Int, Set.Set Int)] gameRound (takenByA, remaining) = do a <- Set.toList remaining return (Set.insert a takenByA, Set.deleteMax \$ Set.delete a remaining) possibilities :: Int -> Set.Set (Set.Set Int) possibilities n = Set.fromList \$ map fst \$ foldl (>>=) [(Set.empty, Set.fromList [1 .. 2*n])] \$ replicate n gameRound {- This turns out to be the sequence of Catalan numbers. -} numberOfPossibilities :: [Int] numberOfPossibilities = map (Set.size . possibilities) [0..]