# 2013C13 needs a better solution

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
6 years, 5 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

The first time I tried this problem I thought it said "with replacement" ... which would be a substantially more difficult problem :)

- 6 years, 5 months ago

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$.

- 6 years, 5 months ago

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.

Staff - 6 years, 5 months ago

Here's another hint - Consider a urn with 2014 balls (yes, just 1 urn). How do we make this into the above problem?

Staff - 6 years, 5 months ago

I got nothing... next hint? :)

I did think of another angle that works but isn't any simpler than the given proofs so far

- 6 years, 5 months ago

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?

Staff - 6 years, 5 months ago

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

- 5 years, 8 months ago