HMMT 二月 2018 · 冲刺赛 · 第 24 题
HMMT February 2018 — Guts Round — Problem 24
题目详情
- [ 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#
解析
英文解析
- [ 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