MathDB

In this problem, we explore a variant of the Monty Hall Problem.
There are

n

doors numbered

1, \dots, n

. A single gold coin is placed randomly behind one of the doors, with the probability it is placed behind door

i

equalling

p_i.

There are

r

"rounds" in which we may make at most

k

"turns" each, defined as follows:
During a "turn", you pick two doors and send them to the game host. Then, the host picks one of the two doors in the following manner:
[*]If neither door contains the coin, the host randomly picks one with equal probability. [*] If one of the doors contains the coin, the host picks the door which does not have the coin.
The host reveals that the picked door does not contain the coin, and opens it.
A "round" consists of Alice performing at least 1 and at most

k

turns. After all the turns in round

j

are complete, suppose there are

d_j

doors remaining. Bob will compute the probability of each individual door containing the coin. Let

m_j

be the minimum of these probabilities computed during the

j

th round. Then, Bob awards Alice

d_jm_j

points. Note that Bob will pay Alice

r

times, and Alice's total payout is the sum of the

r

individual payouts. Note that opened doors remain revealed between rounds.
Suppose

S

is some strategy that determines which doors Alice sends to the host. Let

F(S, n,k,r,(p_1, \dots, p_n))

be the minimum possible amount Alice could earn with strategy

S

for parameters

(n,k,r,(p_1, \dots, p_n))

, and let

G(n,k,r,(p_1, \dots, p_n))= \max\limits _S F(S, n,k,r,(p_1, \dots, p_n)).

Find all tuples

(n,k,r,(p_1, \dots, p_n))

for which

G(n,k,r,(p_1, \dots, p_n))=r.

You may find it useful to consider lists where each element of a list is at most double the prior element.
Proposed by Hari Desikan

3

Problems(1)