Author |
Topic: Quiz Contest Scheduling (Read 553 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Quiz Contest Scheduling
« on: May 27th, 2008, 1:52am » |
 Quote  Modify
|
You are partaking in a quiz contest, in which you will be given a list of N questions, and can answer these questions in any order you like.
You can answer Question i correctly with probability pi. A correct answer will result in a reward Ri.
At the first incorrect answer, the quiz terminates. You are allowed to keep your rewards up to this point.
How should you choose the ordering of questions in order to maximize your expected rewards?
Note 1: If you find it strange to say that "Question i can be answered correctly with a certain probability", one might imagine that we are only told a priori what category of trivia/knowledge that each Question belongs to.
Note 2: There's a nice, elegant answer.
|
| « Last Edit: May 27th, 2008, 2:26am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Quiz Contest Scheduling
« Reply #1 on: May 27th, 2008, 2:23am » |
Quote Modify
|
Seems like something I'd want to solve with a computer. The best I can say is play questions with pi=1 first (whatever order) and pi=0 last. But since most questions are unlikely to be either of those cases it says nothing much.
Somehow we need to maximize  i=1..N [ ( j=1..i po(j)) Ro(i) ] where o(i) gives the permutation order of the questions.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Quiz Contest Scheduling
« Reply #2 on: May 27th, 2008, 2:41am » |
Quote Modify
|
Hmm, maybe we can use
o(i) < o(j) iff piRi - pjRj > pipj (Ri - Rj)
It work for N=2, and it seems like local optimization would lead to global optimization.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Quiz Contest Scheduling
« Reply #3 on: May 27th, 2008, 4:38am » |
Quote Modify
|
on May 27th, 2008, 2:41am, towr wrote:Hmm, maybe we can use
o(i) < o(j) iff piRi - pjRj > pipj (Ri - Rj) |
|
Which is a linear ordering because we sort by R p/(1-p)
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Quiz Contest Scheduling
« Reply #4 on: May 28th, 2008, 12:36pm » |
Quote Modify
|
Here is hand wavy argument, which can probably be converted into a proper proof.
Assume all pi are strictly between 0 and 1.
Suppose the reward Ri you get is money. Suppose another person has a side bet on your exam going on.
For question i, if you get it wrong, that person gets Si. If you get a question right, that person gets nothing.
In order to make it fair to both of you, the exam+money giver sets Si such that Si(1- pi) = Ripi.
The expected amount you will make is same as the expected amount the side bettor will make.
Thus you have to order the questions in such a way that the side better will tend to get the maximum expected amount. Since the side bettor just gets Si in a given trial, looks like arranging by decreasing order of Sis should work.
|
| « Last Edit: May 28th, 2008, 12:37pm by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print