HMMT 二月 2003 · 冲刺赛 · 第 36 题

英文解析

36. A teacher must divide 221 apples evenly among 403 students. What is the minimalnumber of pieces into which she must cut the apples? (A whole uncut apple counts asone piece.)
    Solution: 611
    Consider a bipartite graph, with 221 vertices representing the apples and 403 verticesrepresenting the students; each student is connected to each apple that she gets apiece of. The number of pieces then equals the number of edges in the graph. Each 9
    student gets a total of 221 / 403 = 17 / 31 apple, but each component of the graphrepresents a complete distribution of an integer number of apples to an integer numberof students and therefore uses at least 17 apple vertices and 31 student vertices. Thenwe have at most 221 / 17 = 403 / 31 = 13 components in the graph, so there are atleast 221 + 403 − 13 = 611 edges. On the other hand, if we simply distribute in thestraightforward manner — proceeding through the students, cutting up a new applewhenever necessary but never returning to a previous apple or student — we can createa graph without cycles, and each component does involve 17 apples and 31 students.
    Thus, we get 13 trees, and 611 edges is attainable.