Infinite analogue of the pigeonhole principle

170 Views Asked by At

An urn contains countably many bags and each bag contains countably many balls. We have countably many bins and each bin has the capacity to hold at most countably many balls. We also know that not one particular bag can be entirely emptied into one bin. Our goal is to allocate balls to bins so that every bag is eventually empty and no bin is empty. Is it possible for any bin to be finite? Is it possible for all the bins to be finite? I have yes to both questions since the countable union of finitely many sets is a countable set?

1

There are 1 best solutions below

0
On BEST ANSWER

Since every bag contains only countably many balls and no bin can store all balls of a given bag, we know that every bin has a finite capacity for balls (or that there is some information missing from your question).

Now, there are countably many bags and each of them has countably many balls. Thus (assuming countable choice), there are only countably many balls. Enumerate them as $\{b_1, b_2, \ldots \}$ and enumerate the countably many bins as $\{c_1, c_2, \ldots \}$. Assuming that every bin (well, at least countably many of them) can store at least one ball, we may put the $n$-th ball into the $n$-th bin. This empties every bag, no bin remains empty (unless its capacity is $0$) and every bin contains exactly (at most) $1$ ball.