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?

#Combinatorics #MathProblem #Math

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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

Matt McNabb - 7 years, 7 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$ .

Matt McNabb - 7 years, 7 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.

Calvin Lin Staff - 7 years, 7 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?

Calvin Lin Staff - 7 years, 7 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

Matt McNabb - 7 years, 7 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?

Calvin Lin Staff - 7 years, 7 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

Anas Elidrissi - 6 years, 10 months ago

Math	Appears 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}$