Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Combination / Cost / Probability
1 / 870 /.62
2 / 600 / .65
3 / 540 / .72
4 / 500 / .8
5 / 400 / .82
6 / 320 / .82
7 / 300 / .83
8 / 230 / .86
9 / 200 / .86
10/ 170 / .92

Each item from 1 to 10 is an event with a probability of occurrence associated with it. Probabilities of each item are independent of each other.

Find a subset of these items such that the combined cost (sum of individual costs) is minimized under the constraint that the probability of all the events of this subset occuring (obtained by multiplying their individual probabilities) is less than 0.25.

Please state the subset selected, the probability and the total cost.


share|cite|improve this question
I think you're going to have to make more of an effort to explain this. In its present form it seems trivially impossible, since all $10$ combinations listed have probabilities greater than $0.25$. The problem may or may not be related to the inconsistency between the plural noun "combinations" and the singular verbs "gives" and "has". – joriki Nov 26 '12 at 11:08
My guess is that one is meant to choose a subset of $1,2,\dots,10$, compute its cost by addition, and its probability by multiplication. I hope OP will edit a clarification into the body of the question. – Gerry Myerson Nov 26 '12 at 11:41

To turn this into the classic knapsack problem, recognize that multiplying the probabilities is the same as adding their logarithms. Working with base $2$ logs, you are trying to buy $\log \frac 14 =-2$ in $\log p$. The first item gives you $\log .62 \approx -0.68966$ at a cost of $870$. If you work out the return of the others, you should be able to find which are cheapest.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.