Golden Ticket

[mmiguel]

Mr. Wonka produced 100,000 Wonka bars this year, 5 of which have golden tickets inside of them.

To appease his spoiled daughter, Veruca, Mr. Salt is willing to buy enough Wonka bars to ensure with probability >= 75% that he will have purchased at least one of those tickets.

How many does he need to buy?

[kbrdsk]

27,726?

[phil1882]

15,000

Edited September 3, 2012 by phil1882

[kbrdsk]

15,000

How?

I figured you have a 5/100000 chance of getting the ticket with each candy bar, so after buying x candy bars the probability you won't get a ticket is .99995^x.

[plasmid]

How?

I figured you have a 5/100000 chance of getting the ticket with each candy bar, so after buying x candy bars the probability you won't get a ticket is .99995^x.

This problem calls for a different approach. The reason is:

Suppose Mr. Salt bought all 100,000 candy bars.

0.99995 raised to the 100,000 power is 0.007, implying there's almost a 1% chance he still won't have any of the five tickets.

[superprismatic]

24,214

[plainglazed]

...as superprismatic - i get 24213 and guessing the difference is just an issue of rounding.

.25=(99995-x)(99996-x)(99997-x)(99998-x)(99999-x)

(100000)(99999)(99998)(99997)(99996)

x = 24212.7

[phil1882]

1 in every 20,000 candy bars has a golden ticket.

which means for every 20,000 candy bars you buy, you should have 1 golden ticket.

since 15,000 is 75% of 20,000, 15,000 should be the amount you need for the desired probability.

could you guys explain your method, and why mine is wrong?

[mmiguel]

24,214

nice work!

there are 100000 candy bars,

5 of those have golden tickets

x of those are the ones Mr. Salt picks.

since there is no reason for Mr. Wonka to distinguish between any candy bar, when placing golden tickets, and no reason for Mr. Salt to prefer to buy any candy bar over any other, we may assume equal probabilities for all outcomes involving the ways the tickets may be distributed and the selection of candy bars by Mr. Salt.

Since all outcomes have equal probabilities, the probability of interest becomes the ratio of outcomes satisfying the event of interest (i.e. Mr. Salt buying at least one of the golden tickets), divided by the total number of outcomes.

To see this, consider the following. All outcomes are by definition mutually exclusive, so the union of any outcomes corresponds to the sum of probabilities for those outcomes. All outcomes have equal probability, and let's call that probability p.

The answer, P is the sum of all probabilities where Mr. Salt has at least one golden ticket: P = (# outcomes where he has at least one ticket)*p.

But the sum of the probabilities of all outcomes in the sample space must be 1, and this is only true if p = 1/(# of all possible outcomes).

Therefore P = (# outcomes where he has at least one ticket) / (# of all possible outcomes)

The denominator here is simply the number of ways of distributing 5 golden tickets in 100,000 candy bars times the number of ways of selecting x candy bars of 100,000.

This is (100000 choose 5) * (100000 choose x).

The numerator can be calculated in multiple ways.

Essentially it corresponds to outcomes in which the intersection of the two sets of candy bars(those with golden tickets, and those that were selected by Mr. Salt intersect) is not empty.

Way 1: Multinomial method - Identify 4 mutually exclusive groups of candy bars:

A - Those that have golden tickets and that were selected

B - Those that have golden tickets and were not selected

C - Those that don't have golden tickets and were selected

D - Those that don't have golden tickets and were not selected

It is easiest to calculate the probability for the case where Mr. Salt does not get any golden tickets, and then take one minus this result.

In that case, the size of A is zero.

The size of B is 5.

The size of C is x.

The size of D is 100000 - 5 - x

The multinomial probability formula says the number of ways of splitting up the candy bars into these 4 groups are:

100000!/(0!*5!*x!*(100000-5-x)!)

i.e. the total number of things getting split up is in the numerator (with factorial), while the sizes of each of the groups that are being filled is in the denominator (with factorials).

When this is taken over (100000 choose 5) * (100000 choose x), there is some simplification leading to:

(N-5)!*(N-x)!/((N-5-x)!*N!)

where N = 100000 (to save typing)

This turns out to also be equivalent to (N-5 choose x) / (N choose x) and also (N-x choose 5) / (N choose 5)

Intuitively these can be interpreted as (# of ways to choose x non-golden ticket bars divided by # of ways to choose bars)

and (# of ways to choose 5 non-selected bars divided by # of ways to choose 5 bars).

The actual probability is 1 minus these.

P = 1 - (N-5)!*(N-x)!/((N-5-x)!*N!)

or P = 1 - (N-x)*(N-x-1)*(N-x-2)*(N-x-3)*(N-x-4)/(N*(N-1)*(N-2)*(N-3)*(N-4))

Using some calculation aid, it can be seen that when x <= 24,213, P < 0.75 and when x>=24,124, P > 0.75

this gives prob 0.7500051562780645.

cannot be less than this since 24,213 gives prob 0.7499886619361548

Edited September 3, 2012 by mmiguel

[~andy~]

He needs to buy 15,001