Each of balls is randomly and independently painted either black or white with equal probability. What is the probability that every ball is different in color from more than half of the other balls?
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
Each ball needs at least 3 of the other color among the other 5. That forces exactly 3 black and 3 white: 20 of 64 colorings.
Solution
- What "more than half" means. Each ball has other balls. More than half of means at least . So every ball must have at least balls of the other color.
- Try the possible color splits. Only the number of black balls matters. Go through the splits:
| black, white | a black ball sees this many white | a white ball sees this many black | works? |
|---|---|---|---|
| (no white ball) | no | ||
| no | |||
| no | |||
| yes | |||
| no | |||
| and | same as above with colors swapped | no |
Only the split black, white works. With it, every ball differs from exactly of the other .
3. Count all colorings. Each ball has choices, so there are equally likely colorings.
4. Count the good ones. Pick which of the balls are black: ways.
5. Probability. .
The answer is .
Why this works
A rule that must hold for every ball usually turns into a rule about the totals. The black balls push the number of whites up, and the white balls push the number of blacks up. With only balls, the two pushes meet at exactly and . After that, it is one counting step over .
The trap
Checking the rule for only one color and allowing 4 and 2, or forgetting that each ball has 5 others, so 'more than half' means at least 3.
Concise solution
For any one ball, the "other" balls number , so "more than half" means at least of them have the opposite color.
Suppose balls are black and are white. A black ball (if any) sees white balls among the others, so we need , i.e. . A white ball (if any) sees black balls, so we need . Both colors must be present (if all six were black, each ball would differ from others), so both conditions apply and exactly.
Conversely, with black and white, every ball differs from exactly of the other , which is more than half. So the event is exactly "three of each color."
There are equally likely colorings, of which have three black balls:
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 7: Introduction to Probability
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques
Techniques
Bound the quantity above/below or estimate to pin it down · Set up the equation/formula and compute; no special trick needed