Waste less time on Facebook — follow Brilliant.
×

2013C13 needs a better solution

Main post link -> https://brilliant.org/mathematics-problem/2013c13/?group=YUgoPeVAfUIe

If you look at the written solutions, most of them count the probability as positive outcomes / total outcomes, and use the Hockey stick theorem to interpret the numerator.

Just as the technique of Choosing Correct Variables allows us to simplify the problem, the approach of finding a different perspective can allow us to cut to the heart of the matter. What is a possible different interpretation in this problem? Can you find a one-line solution to this problem? (I'd allow up to 4 short lines.)

Avi has an insight, and states that

By experimentation with smaller numbers of urns \(n\) and balls \(b\), the number of urns doesn't matter, as long as \( n > b \).

How do we prove this insight, without having to calculate the number of outcomes all over again? What is this probability?

Note by Calvin Lin
3 years, 10 months ago

No vote yet
9 votes

Comments

Sort by:

Top Newest

The first time I tried this problem I thought it said "with replacement" ... which would be a substantially more difficult problem :) Matt McNabb · 3 years, 10 months ago

Log in to reply

hello I though about it that way: consider an urn with i balls. ther are \( {2012 \choose 13}\) ways to chose our 13 ball. there are \( {i-1 \choose 13}\) way to chose 13 white balls, and \( {2013-i \choose 13}\) to chose 13 black balls. so the probability must be \( \sum_{i=1}^{2013} \frac{ {2013-i \choose 13} + {i-1 \choose 13}}{2013* {2012 \choose 13}}\) or alternatively \( \sum_{i=1}^{2013} \frac{ {2013-i \choose 13} + {2012-i \choose 13}}{2013* {2012 \choose 13}}\) wich is easy to compute Anas Elidrissi · 3 years, 1 month ago

Log in to reply

Here's another hint - Consider a urn with 2014 balls (yes, just 1 urn). How do we make this into the above problem? Calvin Lin Staff · 3 years, 10 months ago

Log in to reply

@Calvin Lin I got nothing... next hint? :)

I did think of another angle that works but isn't any simpler than the given proofs so far Matt McNabb · 3 years, 10 months ago

Log in to reply

@Matt McNabb For Urn \(i\), let it have \(i-1\) white balls labelled from 1 to \(i-1\), and \(2013 - i \) black balls labelled from \(i+1 \) to \(2014\).

How does this relate to a urn with 2014 balls? Calvin Lin Staff · 3 years, 10 months ago

Log in to reply

I guess it can be proven by induction...

Suppose we have \(n\) urns (each with \(n-1\) balls), with probability \(P\) of a selection of \(b\) balls all being white as \(1 \over b+1\).

To get the case with \(n+1\) urns we add a black ball to every existing urn, and also add a new urn with all white balls.

For a particular pre-existing urn with \(w\) white balls, we have: \[P_{old} = \frac{\binom{w}{b}}{\binom{n-1}{b}}\] \[P_{new} = \frac{\binom{w}{b}}{\binom{n}{b}} \] and \(P_{new} \over P_{old}\) works out to be \(n-b \over n\)

There are \(n\) out of \(n+1\) urns with the above probability ratio change, and \(1\) urn where the probability is \(1\). So the new combined probability is \[P = \frac{n}{n+1} (\frac{1}{b+1} \frac{n-b}{n}) + \frac{1}{n+1} (1)\] which simplifies down to \(1 \over b+1\). Matt McNabb · 3 years, 10 months ago

Log in to reply

@Matt McNabb That's a start, finding another way to work at the problem.

The fact that \( \frac{ P_{new} } {P_{old} } \) is a constant across the urns is interesting, and would seem counter-intuitive to me. I wouldn't have suspected that initially. Calvin Lin Staff · 3 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...