Problem of the Week 1223

The Evil Warden

Solution

This was one of those very rare PoWs that no one solved. In fact, I cannot think of another case.

Well, it was a bit of a trap. About 10 of you submitted the basic approach, which gives a probability of 47%. I was shocked when I found that there is a method that works with probability 48%, which is the best possible. All of this (and extensions of an early PoW in the same vein) leads to many research questions, and I have been working very hard on this with Carter and Rickert over the past few weeks. There are some fascinating problems here. More info on request.

I have prepared solution notes as this PDF. Briefly, the basic solution can be summarized as (12345); and it is helpful to think of the cards as being behind doors numbered 1, 2, 3, 4, or 5.

In short: on hearing target T, Bob opens door T. But (11345) is better: On hearing target T, Bob opens door T unless T is 2, in which case he opens door #1.

The PDF contains lots of detail, including a by-hand computation of the 48%. And there are several open questions at the end that some of you might enjoy thinking about.

This POW caused me to spend a month or more trying to find formulas for the integer that arises from the partial sum of the Maclaurin series for e(a/b), where a and b are integers. I succeeded when a is ±1, ±2. The cases of ±1 were apparently known, but not the ±2 case.

The integer in question is

n! bn Sum[(a/b)k/k! , {k, 0, n}]

The formula for a = ±1 is very simple: Round[ n! bn e(a/b) ]

For a = ±2, it is still essentially a one-liner, thus:

r = n! bn E(a/b) − a(n + 1)/(b(n + 1))
s = Sign[a]n
r − s Mod[r s,2Ceiling[n − Log2[n + 1]]]

The case of a ≥ 3 can be studied, but is much harder.

An interesting step is finding an analytic lower bound for the number of times a prime p occurs in n!. The formulas yield the exact integer in an eyeblink even when n is 10000 or 100000. This has application to the exact symbolic computation of the incomplete Gamma function and certain exponential integrals.

My notes on this, with complete proofs, are available on request.

[Back to Problem 1223]

© Copyright 2016 Stan Wagon. Reproduced with permission.

March 2016