1994 USAMO Problems/Problem 5
Let and denote the number of elements, the sum, and the product, respectively, of a finite set of positive integers. (If is the empty set, .) Let be a finite set of positive integers. As usual, let denote . Prove that for all integers .
Let, for , be a collection of sets such that . We'll try to find such a collection to prove , since we can use the Principle of Inclusion Exclusion to show that .
Let be the set of binary sequences with size , which we'll divide into blocks, in particular, with , the first block has size , the next has size and so on, until we reach , the last few we shall consider as an extra block with size .
Now we perceive that the function has the property, that, for , , so, .
Let be the number of binary sequences with exactly times , but no appearances of in the -th block. It is easy to see that is all of the binary sequences with exactly times , but no appearances of in any of the -th blocks, for . So, we can simply eliminate those blocks, with is equivalent to eliminating from , so we are left with places to put the 's times. This is , and we saw that is is equal to . So, we've found a collection that fits the description.
The number of ways to pick 's times from places is . But we don't want for the 's to fill every block, since this is not in the union. We have ways to put the 's times, where each is in exacty one block ( places places and so on). So, we find that . Which implies, by the Principle of Inclusion Exclusion,
|1994 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|