From a box containing n banknotes, at least one banknote is…
From a box containing $n$ banknotes, at least one banknote is drawn. Determine the probability that an even number of banknotes will be drawn, if drawing any set of banknotes from the given ones is equally likely.
Explanation of Method
An outcome is a non-empty set of banknotes, and all such sets are equally likely. There are $2^n-1$ of them. Using the binomial theorem we show that exactly half of all $2^n$ subsets (including the empty one) have an even number of elements. Removing the empty set gives $2^{n-1}-1$ favourable outcomes.
Step 1: All outcomes
Each banknote is either drawn or not: $2^n$ subsets in total. The empty set is excluded (at least one banknote is drawn), so
\[ \text{number of outcomes} = 2^n - 1. \]
Step 2: Even and odd subsets are equally many
The number of subsets with exactly $k$ elements is $\binom nk$. By the binomial theorem,
\[ (1-1)^n = \sum_{k=0}^{n}\binom nk(-1)^k = \big(\tbinom n0+\tbinom n2+\tbinom n4+\cdots\big) - \big(\tbinom n1+\tbinom n3+\cdots\big) = 0 \quad (n\ge1). \]
So the number of even-size subsets equals the number of odd-size subsets, and each is half of $2^n$:
\[ \binom n0+\binom n2+\binom n4+\cdots = 2^{n-1}. \]
Intuitive reason: fix one banknote. Adding it to or removing it from a set changes the size by one, pairing every even set with an odd set.
Step 3: Favourable outcomes
The $2^{n-1}$ even-size subsets include the empty set (size $0$), which is not allowed:
\[ \text{favourable} = 2^{n-1} - 1. \]
Step 4: The probability
\[ \boxed{P = \frac{2^{n-1}-1}{2^n-1}.} \]
It is slightly less than $\tfrac12$, and tends to $\tfrac12$ as $n$ grows.
Step 5: Examples
| $n$ | Non-empty sets $2^n-1$ | Even sets $2^{n-1}-1$ | $P$ |
|---|---|---|---|
| $1$ | $1$ | $0$ | $0/1\approx0.000 |
| $2$ | $3$ | $1$ | $1/3\approx0.333 |
| $3$ | $7$ | $3$ | $3/7\approx0.429 |
| $4$ | $15$ | $7$ | $7/15\approx0.467 |
| $5$ | $31$ | $15$ | $15/31\approx0.484 |
| $6$ | $63$ | $31$ | $31/63\approx0.492 |
For $n=3$ (banknotes $a,b,c$): the non-empty sets are $\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}$; the even ones are the three pairs, so $P=3/7$. ✓
Step 6: Another reading of the condition
If instead the number of banknotes drawn is chosen uniformly from $1,2,\dots,n$, then the even numbers among them are $\lfloor n/2\rfloor$, and $P=\lfloor n/2\rfloor/n$. The formula above corresponds to the usual assumption that every set of banknotes (every combination) is equally likely.
Result
| Answer | |
|---|---|
| Outcomes | non-empty sets of banknotes: $2^n-1$ |
| Favourable | even non-empty sets: $2^{n-1}-1$ |
| Probability | $P=\dfrac{2^{n-1}-1}{2^n-1}$ |