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 nn and balls bb, the number of urns doesn't matter, as long as n>b 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, 3 months ago

No vote yet
9 votes

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


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

Log in to reply

I guess it can be proven by induction...

Suppose we have nn urns (each with n1n-1 balls), with probability PP of a selection of bb balls all being white as 1b+11 \over b+1.

To get the case with n+1n+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 ww white balls, we have: Pold=(wb)(n1b)P_{old} = \frac{\binom{w}{b}}{\binom{n-1}{b}} Pnew=(wb)(nb)P_{new} = \frac{\binom{w}{b}}{\binom{n}{b}} and PnewPoldP_{new} \over P_{old} works out to be nbnn-b \over n

There are nn out of n+1n+1 urns with the above probability ratio change, and 11 urn where the probability is 11. So the new combined probability is P=nn+1(1b+1nbn)+1n+1(1)P = \frac{n}{n+1} (\frac{1}{b+1} \frac{n-b}{n}) + \frac{1}{n+1} (1) which simplifies down to 1b+11 \over b+1.

Matt McNabb - 6 years, 3 months ago

Log in to reply

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

The fact that PnewPold \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 - 6 years, 3 months 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 - 6 years, 3 months ago

Log in to reply

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

Log in to reply

For Urn ii, let it have i1i-1 white balls labelled from 1 to i1i-1, and 2013i2013 - i black balls labelled from i+1i+1 to 20142014.

How does this relate to a urn with 2014 balls?

Calvin Lin Staff - 6 years, 2 months ago

Log in to reply

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

Anas Elidrissi - 5 years, 6 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...