返回题库

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

HMMT February 2003 — Guts Round — Problem 44

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. A partition of a number n is a sequence of positive integers, arranged in nonincreasingorder, 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 ldominate 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 thepartitions 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 isthe largest m such that the first m partitions you list constitute a valid answer.
解析

英文解析

  1. A partition of a number n is a sequence of positive integers, arranged in descendingorder, 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 ldominate 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 thepartitions 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 isthe largest m such that the first m partitions you list constitute a valid answer.
    Comments: Computer searches have found that the maximum possible number ofpartitions 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 inhttp://www-math.mit.edu/~ efedula/chains.ps
    “Chain Lengths in the Dominance Lattice,” by Edward Early, 2002
    the maximum number of mutually nondominating partitions of n is roughly on the 13
    √
    π 2 n/ 3
    order of e (in fact, the ratio of the total number of partitions to n to the maximumnumber of nondominating partitions has polynomial order of magnitude), although aproof by explicit construction is not known.