Alex distributes some cookies into several boxes and records the number of cookies in each box. If the same number appears more than once, it is recorded only once. Serge takes one cookie from each box and puts them on the first plate. Then he takes one cookie from each box that is still non-empty and puts the cookies on the second plate. He continues until all the boxes are empty. Then Serge records the number of cookies on each plate. Again, if the same number appears more than once, it is recorded only once. Prove that Alex's record contains the same number of numbers as Serge's record.
Problem 1655
Official solution
1. Initial Setup and Definitions:
- Let be the boxes with cookies.
- Let be the number of cookies in box .
- Alex records the distinct values of in a set .
2. Serge's Process:
- Serge takes one cookie from each non-empty box and places them on the first plate.
- He repeats this process, placing cookies on subsequent plates until all boxes are empty.
- Let be the plates used by Serge.
3. Recording the Number of Cookies on Each Plate:
- Let be the number of cookies on plate .
- Serge records the distinct values of in a set .
4. Visual Representation:
- Consider each box as a column in a vertical histogram where the height of the column represents the number of cookies.
- Draw horizontal lines at each integer height from 1 to the maximum number of cookies in any box.
5. Analysis of Serge's Process:
- Each horizontal line at height intersects the columns at points where the boxes have at least cookies.
- The number of intersections at height corresponds to the number of cookies on the -th plate.
6. Distinct Heights and Plate Counts:
- If two boxes have the same height (same number of cookies), they contribute the same number of cookies to each plate until they are empty.
- Therefore, we can consider each distinct height as a unique contribution to the plates.
7. Equivalence of Records:
- The number of distinct heights in the histogram is equal to the number of distinct values in Alex's record .
- The number of distinct plate counts is equal to the number of distinct values in Serge's record .
8. Conclusion:
- Since each distinct height corresponds to a unique number of cookies on a plate, the number of distinct values in is equal to the number of distinct values in .