The bottom line answer for the expected value of the maximum number in the array is, for N=5, 937669227/67108864 (which is approximately 13.97).
Kudus to Christopher Marks who was the first to solve this month's challenge without using programming at all, but rather by merely doing a careful examination of cases.
Among others, we also received the following solutions:
A one-line Mathematica solution from Todd Will:
A small Haskel program from John Tromp:
avg :: [Integer] -> Ratio Integer
avg ps | length ps >= 5 = maximum ps % 1
avg ps = (avg' (2:ps) + avg' (4:ps)) / 2
avg' :: [Integer] -> Ratio Integer
avg' = avg . reduce
reduce :: [Integer] -> [Integer]
reduce (a:b:ps) | a == b = reduce (a+b : ps)
reduce ps = ps
main = print $ avg 
And a PARI-GP program from Claus Andersen and David Brink.
John Snyder sent us a very detailed analysis of the problem. We chose to share his nice graphic representation of the Markov process here:
Oleg Vlasii computed the answer for N=1,2,...,10 and noted the pattern
A(n) = (F(n)*2^(f(n)-1)+3^f(n))/2^(2^N-N-1)
where f(n) = 2^(n-1)-1
and F(n) are integers; but a closed form formula still eludes us.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: firstname.lastname@example.org