Picking A PAinting

greater chances of success than just random selection. conditional probability is also explored as a way to evaluate the ... mula for conditional prob...
16 downloads 619 Views 3MB Size
Download PDF
Love PNG Images
Picking A PAinting

Benjamin Dickman Brookline, MA

teacher’s guide – getting Started

Purpose in this two-day lesson, students are asked to choose the best possible painting from a group provided to them. certain restrictions prevent students from going back to previously viewed paintings, so choosing the best is not as straightforward as just looking at all of them and deciding. the objective of this lesson is to use ordering and logical thinking to create probabilistic strategies that have greater chances of success than just random selection. conditional probability is also explored as a way to evaluate the strategies further. Prerequisites knowledge of factorials is helpful but not necessary. Materials Required: none. Suggested: none. Optional: Playing cards to represent paintings of greater and lesser value. Worksheet 1 guide the first three pages of the lesson constitute the first day’s work. Students are introduced to the problem of choosing a painting for an art gallery. Shrinking the problem down to a situation in which there are only two or three paintings helps students to create a strategy for picking the best painting possible. the idea of conditional probability is introduced near the end of the first day. Worksheet 2 guide the fourth page of the lesson constitutes the second day’s work. Students are urged to create a general formula for conditional probability and then expand their process of picking a painting to larger selections of paintings. ccSSM Addressed S-cP.1: Describe events as subsets of a sample space (the set of outcomes) using characteristics (or categories) of the outcomes, or as unions, intersections, or complements of other events (“or,” “and,” “not”). S-cP.3: Understand the conditional probability of A given B as P(A and B)/P(B), and interpret independence of A and B as saying that the conditional probability of A given B is the same as the probability of A, and the conditional probability of B given A is the same as the probability of B.

225

Picking A PAinting Student name:_____________________________________________ Date:_____________________ An anonymous donor has decided to give her art collection to various museums. Each museum is allowed to choose one painting, and, because you have a discerning eye for brushwork, the national gallery of Art has requested that you choose on their behalf. Furthermore, because the paintings all are different, you are confident that no two of them are “equally good.”

Adolph von Menzel [Public domain], via Wikimedia commons

time constraints and other museums vying for the paintings force you to follow a few rules: 1. 2. 3. 4. 5. 6. 7.

You cannot view any painting before it is shown officially; Paintings will be shown one at a time, in a random order; For each painting, you must either choose it or reject it; if you choose a painting, you must leave with it; if you reject a painting, you cannot return to it later; the total number of paintings is known ahead of time; and You know the relative rankings of paintings that were shown and have no external knowledge.

Leading Question How will you decide which painting to choose if your goal is to pick the best painting possible?

226

Picking A PAinting Student name:_____________________________________________ Date:_____________________ 1. is it a good idea always to pick the first painting shown? What about the last one? What other strategies could you use?

2. Suppose there are only two paintings. What is the chance that the first painting shown is the best one? What is the chance that the last painting shown is the best?

3. What if there are three paintings? What is the chance that the first painting shown is the best? What is the chance the second one shown is best? What is the chance the third one shown is best?

4. For three paintings, there will be the best painting (A), the second best painting (B), and the worst painting (c). What are the different orderings in which the three paintings could be shown? How many of these orderings are there in all?

227

the set of all possible outcomes is known as the sample space.

Picking A PAinting Student name:_____________________________________________ Date:_____________________ 5. A friend has a suggestion. Whatever painting is shown first, reject it! then, as soon as you see a painting better than the first one, select it! When will this friend’s suggested strategy be successful in obtaining the best painting? When will it fail? What is the probability that the best painting out of the entire set will be selected if this strategy is followed?

6. in the cases where c is shown first, what is the probability of choosing the best painting out of the entire set using the strategy from question 5? What about the cases where B and A are shown first?

7. What if there are four paintings? in how many orders can they be arranged? create your own strategy to pick a painting. What is the probability that your strategy will be successful in selecting the best painting?

8. in the case where the worst painting is shown first (out of four), what is the probability of choosing the best painting out of the entire set using the strategy from question 5? What about the cases when other paintings are shown first?

228

Picking A PAinting Student name:_____________________________________________ Date:_____________________ 9. How many orderings are possible for five paintings? Six? create and evaluate strategies for when there are many paintings. What difficulties might emerge?

10. create a general formula for calculating the probability if you know the quality of the first painting shown.

11. What if there were 100 paintings? create a strategy that will help you pick the best painting at least 1/4 of the time

try first dividing the paintings into two equal sets, one of the first 50 paintings shown, and the other containing the last 50 paintings shown.

12. How might you generalize the question of choosing the best painting? What are some related questions you can ask?

229

Picking A PAinting teacher’s guide — Possible Solutions the solutions shown represent only some possible solution methods. Please evaluate students’ solution methods on the basis of mathematical validity. 1. Always picking the first or last painting will result in the same probability of picking the best painting. With n paintings, there will be probability 1/n of picking the best. 2. Using the same idea as question 1 where n = 2, P(first shown is the best) = P(last shown is the best) = 1/2. 3. Similar to the last two, P(first shown is the best) = P(second shown is the best) = P(last shown is the best) = 1/3. 4. Six orderings create the sample space: (A, B, c), (A, c, B), (B, A, c), (B, c, A), (c, A, B), and (c, B, A). 5. the strategy suggested by a friend is successful for the subset of the sample space (c, A, B), (B, A, c), and (B, c, A), and fails for the rest. Since it is successful for 3 of the 6 orderings, the probability of the strategy being successful is P(strategy is successful) = 3/6 = 1/2. 6. When B is shown first, the best, A, is chosen 2/2 times. When A is shown first, the best is chosen 0/2 times, and when c is shown first the best is chosen 1/2 times. 7. For four paintings, there are 4! = 24 orderings possible. the same strategy as before (reject the first painting, and pick the next one shown that is better than the first) will be successful with probability 11/24. Another option is to choose to reject the first two paintings, then choose the next one shown that is better than both of the first two. this will be successful with probability 10/24 = 5/12. 8. if the paintings are ordered A, B, c, and D as in question 4, then if D is shown first, the best, A, is chosen 2/6 times. When c is shown first the best is chosen 3/6 times. When B is shown first the best is chosen 6/6 times and when A is shown first the best is chosen 0/6 times. this total aligns with the answer to question 7, 11/24. 9. For n paintings, there are n! possible orderings. thus, for 5 paintings, there are 5! = 120 orderings and for 6 there are 6! = 720 orderings. Using similar strategies as with the previous problems, students may choose to view some number, k, of paintings before deciding when to stop viewing and choose a painting that is better than any of the ones already viewed. As n grows, computations may become very tedious very quickly. 10. the formula should bear some resemblance to conditional probability (i.e., given two events, X and Y, then the probability of X occurring given that Y has occurred is P(X given Y) = P(X and Y)/P(Y). 11. Reject any painting shown in the first half, and choose the next painting shown that is better than any of those shown in first half. this strategy will succeed at least when the second best painting is in the first half, and the best painting is in the second half. the probability of this is (50/100)(50/99) > 1/4. (in fact, there are other cases for which this strategy will work that will only increase the probability that it is successful.) 12. choosing the best painting is not always possible no matter what strategy is used. the best thing do is to increase the probability of choosing one of the best paintings (if not the best). Some possible questions are “For a total of n paintings, how many should you pass on?”, “Are there other kinds of strategies one could use?”, and “What are the advantages and disadvantages of using a computer program to evaluate probabilities of success for different strategies?”

230

Picking A PAinting teacher’s guide — Extending the Model the first extension is to define the optimal strategy for n paintings, and to do most of the proof that it is correct. First, a definition we will need: A candidate is a painting which you rank higher than any you have seen previously. We begin from the fact that the best painting among the n paintings is somewhere in the order in which the collection is shown. the strategy we will consider, which generalizes one in the lesson, is to examine and to rank relatively the first p –1 of the paintings shown. What is p? We will show how to find the best p as a function of n. then the strategy is to accept the first painting which is a candidate shown after the initial p –1 paintings. this means the first painting you see starting at p that is better than all of the first p –1 paintings is the one you choose. You are in a sense using the first p –1 paintings to “get the lay of the land”. What will this strategy do? if the very best of all the paintings happens to be among the first p –1 that you looked at, you have missed it and there is nothing you can do about it. in this case, your probability of getting the best painting is 0. this consideration will keep p from getting too large. if the best painting is later than p –1 in the order of presentation, that is, in the interval (p, …, n), you have a chance. if the painting presented as p happens to be the overall best, which happens with probability 1/n, you will get it. Of course, 1/n is the probability of the best painting being at any particular position in the order. Suppose the overall best painting is at position k, where k p. Will you get that painting? if and only if the best painting among the first k –1 paintings is in fact among the first p –1 paintings! What’s the probability of that? the probability is just (p –1)/(k –1). thus (p –1)/(k –1) is the probability that you will get the best painting given that it is at position k in the order. But the probability of that condition, as we have seen, is just 1/n. Hence the probability that you will get the best painting when it is at position k is (p –1)/(n(k –1)). Hence the probability that you get the best overall painting is the sum of these expressions from k = p to k = n. We write it out: the probability of success for this strategy is

it remains to find the best p as a function of n. For n = 3 and 4, this was done in the lesson, and it is worth checking that the above formula gives the best answer. When you vary p with fixed n, the expression begins small when p = 2, is again small when p = n, and has a maximum in between. You look for the value of p where it stops increasing and starts decreasing. Let’s also look at this for large n. About how big is that sum we just defined? For large n and p, it is approximately (p/n)(lnn – lnp). if we set x = n/p, this is (lnx)/x. this has a maximum at x = e. So the best strategy, if n is at all large, is to pick p/n as close as we can to 1/e. We said at the beginning that we will do “most of the proof” that this is correct. We have omitted the argument that the optimal strategy is, in fact, to look at some number p –1 of paintings and then pick the best thereafter. this is eminently reasonable, but that’s not a proof. the full story can be found, for example, in Fred Mosteller’s Fifty challenging Problems in Probability with Solutions. And now, a second extension: An interesting modeling problem in a very similar spirit is what is sometimes called the “theater problem”. it concerns finding a parking space when you want to go to the theater. imagine an infinite road with parking spaces at the integers, most of which are filled as you approach the theater, which is at a known integer location. the model is actually most workable if you assume an infinite road.

231

Picking A PAinting teacher’s guide — Extending the Model You want a space as close to the theater as possible. When you consider a candidate, that is, a space that is available, you cannot tell what other closer spaces might be available. if you don’t take this candidate, the space will no longer be there if you later decide you should have taken it. if you don’t take a space by the time you pass the theater, you will have to take one a long way beyond the theater, and you will be unhappy. Assuming you know the location of the theater, and the probability that any space will be available, what is your best strategy? Once you understand this one, you can consider including in the model a (possibly high) cost of making an illegal U-turn and trying again!

Reference Mosteller, F. (1987). Fifty challenging problems in probability with solutions. new York: Dover.

232