# Who wants to be a Millionaire?

Consider the following version of the who wants to be a millionaire game: You are given a list $$\mathcal{L}$$, consisting of $$N$$ questions. You can answer the questions in any order you like. The probability that you answer the $$i$$th question in $$\mathcal{L}$$ correctly is $$p_i$$ and you win $$v_i$$ dollars for answering it correctly , $$i=1,2,\ldots, N$$. However, if you give a wrong answer to a question, the game ends immediately and you leave the game with the money you have already won (if any). Naturally, your objective is to answer the questions in an optimal order $$\mathcal{S}$$ so as to maximize your expected winning. To be clear, $$\mathcal{S}$$ is a permutation of natural numbers from $$1$$ to $$N$$ which corresponds to your order of answering questions from the list $$\mathcal{L}$$, e.g., if $$\mathcal{S}(1)=1000$$, it means that you answer the $$1000$$ th question first from $$\mathcal{L}$$ and so on.

Here is the data for $$N=10000$$ questions, where the row numbers (on the left) correspond to question numbers in the list $$\mathcal{L}$$, the first column corresponds to the probabilities $$p_i$$'s and the second column corresponds to the prizes $$v_i$$'s.

Find $$\mathcal{S}(2015)$$ in the optimal sequence.

×