HMMT 二月 2003 · 冲刺赛 · 第 44 题
HMMT February 2003 — Guts Round — Problem 44
题目详情
- A partition of a number n is a sequence of positive integers, arranged in nonincreasing order, whose sum is n . For example, n = 4 has 5 partitions: 1 + 1 + 1 + 1 = 2 + 1 + 1 = 2 + 2 = 3 + 1 = 4. Given two different partitions of the same number, n = a + a + · · · + a = b + b + · · · + b , where k ≤ l , the first partition is said to 1 2 k 1 2 l dominate the second if all of the following inequalities hold: a ≥ b ; 1 1 a + a ≥ b + b ; 1 2 1 2 a + a + a ≥ b + b + b ; 1 2 3 1 2 3 . . . a + a + · · · + a ≥ b + b + · · · + b . 1 2 k 1 2 k Find as many partitions of the number n = 20 as possible such that none of the partitions dominates any other. Your score will be the number of partitions you find. If you make a mistake and one of your partitions does dominate another, your score is the largest m such that the first m partitions you list constitute a valid answer.
解析
- A partition of a number n is a sequence of positive integers, arranged in descending order, whose sum is n . For example, n = 4 has 5 partitions: 1 + 1 + 1 + 1 = 2 + 1 + 1 = 2 + 2 = 3 + 1 = 4. Given two different partitions of the same number, n = a + a + · · · + a = b + b + · · · + b , where k ≤ l , the first partition is said to 1 2 k 1 2 l dominate the second if all of the following inequalities hold: a ≥ b ; 1 1 a + a ≥ b + b ; 1 2 1 2 a + a + a ≥ b + b + b ; 1 2 3 1 2 3 . . . a + a + · · · + a ≥ b + b + · · · + b . 1 2 k 1 2 k Find as many partitions of the number n = 20 as possible such that none of the partitions dominates any other. Your score will be the number of partitions you find. If you make a mistake and one of your partitions does dominate another, your score is the largest m such that the first m partitions you list constitute a valid answer. Comments: Computer searches have found that the maximum possible number of partitions is 20, achieved e.g. by the following: 9 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 6 + 3 + 3 + 2 + 2 + 2 + 2 8 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 5 + 5 + 4 + 1 + 1 + 1 + 1 + 1 + 1 7 + 4 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 5 + 5 + 3 + 2 + 2 + 1 + 1 + 1 7 + 3 + 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 5 + 5 + 2 + 2 + 2 + 2 + 2 7 + 3 + 2 + 2 + 2 + 1 + 1 + 1 + 1 5 + 4 + 4 + 3 + 1 + 1 + 1 + 1 7 + 2 + 2 + 2 + 2 + 2 + 2 + 1 5 + 4 + 4 + 2 + 2 + 2 + 1 6 + 5 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 5 + 4 + 3 + 3 + 3 + 1 + 1 6 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 1 5 + 3 + 3 + 3 + 3 + 3 6 + 4 + 2 + 2 + 2 + 2 + 1 + 1 4 + 4 + 4 + 4 + 2 + 1 + 1 6 + 3 + 3 + 3 + 2 + 1 + 1 + 1 4 + 4 + 4 + 3 + 3 + 2 In general, as shown in http://www-math.mit.edu/~ efedula/chains.ps “Chain Lengths in the Dominance Lattice,” by Edward Early, 2002 13 the maximum number of mutually nondominating partitions of n is roughly on the √ π 2 n/ 3 order of e (in fact, the ratio of the total number of partitions to n to the maximum number of nondominating partitions has polynomial order of magnitude), although a proof by explicit construction is not known.