Who wants to be a Millionaire?

We will be solving the problem using an interchange argument . Consider any sequence of answering the questions $\mathcal{S}$ . Let $X_{(i)}$ denote the reward obtained from the $i$ th question in the sequence $\mathcal{S}$ . Hence, the total expected reward $\mathbb{E}R$ obtained by answering the questions in the order of $\mathcal{S}$ is given by : $\mathbb{E}R=\mathbb{E}\sum_{i=1}^{N}X_{(i)}=\sum_{i=1}^{N}\mathbb{E}X_{(i)}$ Where we have used Linearity of Expectations in the last equality. Since we obtain a reward associated with the question $(i)$ iff we answer all first $i$ questions correctly, it follows that $\mathbb{E}X_{(i)}=(\prod_{j=1}^{i}p_{(j)} )v_{(i)}$ . Now consider another sequence $\mathcal{S}'$ , which is the same as $\mathcal{S}$ , except that we interchange the order of answering $i$ th and $i+1$ th questions, for some given $i$ . Hence, from the above equation, it follows that the total expected reward $\mathbb{E}R'$ for answering the questions in the order of $\mathcal{S}'$ is given by $\mathbb{E}R'=\mathbb{E}R +\big( \prod_{j=1}^{i-1}p_j\big)\big(p_{(i+1)}v_{(i+1)}+p_{(i)}p_{(i+1)}v_{(i)}-p_{(i)}v_{(i)}-p_{(i)}p_{(i+1)}v_{(i+1)}\big)$ If $\mathcal{S}$ is the optimal sequence, we must have $\mathbb{E}R\geq \mathbb{E}R'$ . This implies $p_{(i)}v_{(i)}+p_{(i)}p_{(i+1)}v_{(i+1)}\geq p_{(i+1)}v_{(i+1)}+p_{(i)}p_{(i+1)}v_{(i)}$ Rearranging, $p_{(i)}\big(1-p_{(i+1)}\big)v_{(i)}\geq p_{(i+1)}\big(1-p_{(i)}\big)v_{(i+1)}$ i.e., $\frac{p_{(i)}}{1-p_{(i)}}v_{(i)} \geq \frac{p_{(i+1)}}{1-p_{(i+1)}}v_{(i+1)}$ This implies that the optimal sequence is obtained by sorting the questions in the list $\mathcal{L}$ (in decreasing order) according to their scores $s_i=\frac{p_iv_i}{1-p_i}$ . Once we perform this sorting in the given data, we find that the $2015$ th position in the optimal list is occupied by the $3132$ nd question.

Based on the same observation as Abhishek Sinha , this is a program in python 3.5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

f = open('data')
txtlst = f.readlines()
f.close()
data = []
for k in range(len(txtlst)):
    [a, b] = [eval(x) for x in txtlst[k].split()]
    data.append([k + 1, a, b , a*b/(1 - a)])

sdata = sorted(data, key=lambda x: x[3], reverse=True)
print(sdata[2014][0])