You have twin children, and their birthday is approaching. You go to the toy shop to buy them presents and see 10 different toy options on the shelves. Each has a whole dollar price between $1 and $100. The toys are unique, and the store carries no duplicates. You want to buy each child a different set of toys, but to avoid favoritism, you wish to spend exactly the same amount of money on them. For example, you’d be willing to buy one child a single toy worth $90 and the other child two toys worth $3 and $87. Amazingly, no matter what prices you encounter at the store, it will always be possible to buy your children different gifts for the same total price. Why is that the case?
Consider the total number of different toy collections you can buy (in other words, how many distinct subsets you can make from 10 items). Compare this with the number of different dollar values that each subset of toys can be worth. What’s the minimum total value a subset of toys can have? What’s the maximum?
There are 1,023 different collections of toys that you can buy. (The next paragraph explains why, so if you already know why, then feel free to skip it.)
In general, the number of distinct subsets of some number of items n is 2n. To understand this, notice that you can make four subsets out of two items that we’ll call A and B: A alone, B alone, both A and B or neither A nor B. Adding a third item, C, doubles the possibilities because we can make all of the previous subsets of A and B either include C or not include C. (We could have A with or without C, B with or without C, A and B with or without C, or neither A nor B with or without C, for eight total subsets). A fourth item doubles the possibilities again, and so on. For 10 items, this yields 210 = 1,024 subsets, but we subtract one for our purposes because we don’t want to count the case in which you buy no toys at all.
The minimum dollar value for a collection of toys is $1 (a single toy worth $1) and the maximum is $1,000 (all 10 toys, if each of them was worth $100). So we have 1,023 possible collections of toys and only 1,000 different price values that they can take on. This means there must be at least two distinct subsets of toys with the same total dollar value. If those two subsets have any toys in common, then we can remove the common toys from both sets, and their prices will still be equal. This results in two completely different sets of toys worth the same total dollar amount.
Notes from Readers
In our recent puzzle “The Wanderer’s Return,” I wrote an intuition-based solution to avoid hairy algebraic calculations. Retired software consultant Michael A. Gottlieb, editor of The Feynman Lectures on Physics, New Millennium edition, submitted a slick rigorous argument that I think other readers will enjoy.
Instead of focusing on the probabilities of ending in each village, we’ll look at the total number of paths ending at each village. Each path of any given length has the same likelihood, so if there are more paths of length 100 that end in Avalon than in Belthar, we are justified in concluding that the wanderer has a higher probability of ending in Avalon.
Define A(n) to be the number of distinct paths of length n that end in Avalon, and define B(n) and C(n) similarly for Belthar and Cresthaven. Because of the symmetry between Belthar and Cresthaven in the problem, we observe that B(n) = C(n) for all n. Michael writes:
A(n + 1) = C(n) + B(n) = 2 × B(n),
and
B(n + 1) = A(n) + C(n) = A(n) + B(n),
thus
A(n + 1) – B(n + 1) = 2 × B(n) – (A(n) + B(n)) = B(n) – A(n).
From this it can be seen directly that when the number of hops n increases by 1, the difference in the number of paths returning to Avalon and the number going to Belthar, A(n) – B(n), changes only in sign. And since A(0) – B(0) = 1 – 0 = 1, one can immediately conclude that A(n) – B(n) = 1 for n even, and –1 for n odd.
The first equality, A(n + 1) = C(n) + B(n), comes from the fact that all paths ending at Avalon must have ended at either Cresthaven or Belthar on the previous day. The number of ways to reach Avalon in exactly n + 1 days, therefore, equals the number of ways to reach Cresthaven in n days plus the number of ways to reach Belthar in n days. The second equality, C(n) + B(n) = 2 × B(n), stems from B(n) = C(n).
This argument shows not only that the wanderer is more likely to end at Avalon after even days and Belthar after odd days but also that the total number of paths ending at Avalon versus Belthar only ever differs by 1. Thanks, Michael, for the neat argument.
We’d love to hear from you! E-mail us at games@sciam.com to share your experience.