返回题库

HMMT 二月 2018 · 冲刺赛 · 第 24 题

HMMT February 2018 — Guts Round — Problem 24

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

题目详情

  1. [ 12 ] Find the largest positive integer n for which there exist n finite sets X , X , . . . , X with the
    1 2 nproperty that for every 1 ≤ a < b < c ≤ n , the equation
    ⌈ ⌉
    √
    | X ∪ X ∪ X | = abca b cholds.
    HMMT February 2018, February 10, 2018 — GUTS ROUND
    Organization Team Team ID#

英文原题

[ 12 ] Find the largest positive integer n for which there exist n finite sets X 1 , X 2 , . . . , X n with the
property that for every 1 ≤ a < b < c ≤ n , the equation
| X a ∪ X b ∪ X c | =
⌈ √ abc
⌉
holds.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HMMT February 2018, February 10, 2018 — GUTS ROUND
Organization Team Team ID#

解析

英文解析

  1. [ 12 ] Find the largest positive integer n for which there exist n finite sets X , X , . . . , X with the
    1 2 nproperty that for every 1 ≤ a < b < c ≤ n , the equation
    ⌈ ⌉
    √
    | X ∪ X ∪ X | = abca b cholds.
    Proposed by: Pakawut Jiradilok
    Answer: 4
    First, we construct an example for N = 4. Let X , X , X , X be pairwise disjoint sets such that
    1 2 3 4
    X = ∅ , | X | = 1, | X | = 2, and | X | = 2. It is straightforward to verify the condition.
    1 2 3 4
    ⌈ ⌉
    √
    We claim that there are no five sets X , X , . . . , X for which #( X ∪ X ∪ X ) = abc , for 1 ≤ a <
    1 2 5 a b cb < c ≤ 5. Note that showing the non-existence of five such sets implies that there are no n sets with the desired property for n ≥ 5 as well.
    Suppose, for sake of contradiction, that there are such X , . . . , X . Then, note that | X ∪ X ∪ X | = 3,
    1 5 1 2 4
    | X ∪ X ∪ X | = 4, and | X ∪ X ∪ X | = 7. Note that
    1 2 5 2 4 5
    | X ∪ X ∪ X | + | X ∪ X ∪ X | = | X ∪ X ∪ X | .
    1 2 4 1 2 5 2 4 5
    For any sets A, B, C, D , we have the following two inequalities:
    | A ∪ B ∪ C | + | A ∪ B ∪ D | ≥ | A ∪ B ∪ C ∪ D | ≥ | B ∪ C ∪ D | .
    For A = X , B = X , C = X , and D = X in the situation above, we conclude that the equalities
    1 2 4 5
    must both hold in both inequalities. The first equality shows that X ∪ X = ∅ , and therefore both
    1 2
    X and X are empty.
    1 2
    Now observe that | X ∪ X ∪ X | = 5 6 = 7 = | X ∪ X ∪ X | . This gives a contradiction.
    1 4 5 2 4 5